大数相乘

2个数相乘(1.11 * 2.22 )，步骤如下:

1．             先剔除小数点，再计算2数相乘，(111 * 222 = 24642)

2．             2个运算数的小数点位(倒数)相加 (2 + 2 = 4， 即1.11小数点位置2,  2,22小数点位置为2)

3．             相乘结果(24642) 倒数插入小数点位数之和(4)得到预算结果: 2.4642

整体思路如下:

1．             对输入的数据(字符串)提取 数字 + 符号 + 小数点位数，对应函数:

char *extract_string(char *sour, e_sign_type &sign, unsigned int &ndot)//to be improved

2．             对提取出的 数字相乘，计算出结果；

char *mult_pos_int(char *mult1, char *mult2)

3．             对相乘结果，补上 符号 和 小数点位数

char *recover_string(char *sour, e_sign_type sign, unsigned int ndot))//to be improved

       最后提供计算接口函数是：

char *mult_signed_num(char *mult1, char *mult2)

//代码如下，编译环境Visual c++ 2005，系统： windows Xp

#include "stdafx.h"

#include

#include

using namespace std;

enum e_sign_type

{

       ENUM_POSITIVE,      // 正数  

       ENUM_NEGATIVE,          // 负数

};

/*--------------------------------------------------------------------------------------

Function:   2个字符串相乘

Parameter:  mult1: 乘数，mult2: 乘数

Return:     两数相乘的结果

Condition:  1. 这里假设这个数都是正整数，即不考虑小数点和负号

            2. 返回值的内存在这个函数里动态分配，注意在外部释放内存

------------------------------------------------------------------------------------------*/

char *mult_pos_int(char *mult1, char *mult2)

{

              if  ( (NULL==mult1) && (NULL==mult2)  )

                     return NULL;

              unsigned int nlen1 = strlen(mult1);

              unsigned int nlen2 = strlen(mult2);

              // 本程序局限性：计算结果长度为：^32 = 4294967296，如果计算结果长度超过亿，将会溢出。

              // 不妨将类型修改为长度为bytes类型long long

              // 另外：nlen1+nlen2也可能溢出

              unsigned int nlen_r = nlen1+nlen2;  // 即数相乘的结果长度最大是乘数长度之和

              char *sz_res = new char[nlen_r+1];  // 最后还有一结束符

              if (NULL == sz_res)

              {     

                     cout << "new memory fail" << endl;

                     return NULL;

              }

              memset(sz_res, 0, nlen_r+1);

              char *end1 = mult1+nlen1-1;

              char *end2 = mult2+nlen2-1;

              char *end_r= sz_res+nlen_r-1;

              char *tok = end_r;

             

              int carry = 0;   // 进位

              while(mult1 <= end1)

              {

                     carry = 0;   // 进位

                     while (mult2 <= end2)

                     {

                            int tmp = (*end1-0x30) * (*end2-0x30) + carry + *end_r;

                            *end_r = tmp%10;

                            carry = tmp/10;

                            end_r--;

                            end2--;

                     }     

                    

                     *end_r = carry;       // high attention

                     end1--;

                     end2 = mult2+nlen2-1;

                     tok--;

                     end_r= tok;    // 每次运算完成后end_r后移一位

              }

              if (carry > 0)

              {

                     *sz_res = carry;   // 最高位为carry

                     char *pcur = sz_res;

                     for (unsigned int i=0; i   // high attention

                     {

                            *pcur += 0x30;

                            pcur++;

                     }

                     return sz_res;

              }

              else   // 最高位为，需要移位

              {

                     // 考虑到如果计算结果特别长，比如是sizeof(unsigned int),依次移位特别慢，

                     // 是否可以另外申请一块内存，用memcpy复制过去，代码如下：

                     char *sz_new = new char[nlen_r];  // 长度为nlen_r即可

                     memcpy(sz_new, sz_res+1, nlen_r);

                     delete []sz_res;

                     sz_res = NULL;

                     char *pcur = sz_new;

                     for (unsigned int i=0; i  // high attention: i

                     {

                            *pcur += 0x30;

                            pcur++;

                     }

                     return sz_new;

              }

}

/*--------------------------------------------------------------------------------------

Function:   判断输入的字符串是否是浮点数

Parameter:  sz: input, s输入的字符串

Return:     0: 不是浮点数

                     其它值: 浮点数小数点所在字串的位置

Condition:  sz不为空

------------------------------------------------------------------------------------------*/

int check_floating(char *sz)

{

       int npos = 0;

       char *end = sz + strlen(sz) - 1;

       while(sz < end)

       {

              if ('.' == *end)

                     return npos;

              else

                     end--;

              npos++;

       }

       return 0;

}

/*--------------------------------------------------------------------------------------

Function:   从输入的字符串中提取数字信息，即剔除'-'和'.'

Parameter:  sour:  输入的字符串

            sign: 传出的值，枚举

                     ndot:  传出的值, 0: 不是浮点数 其它值：小数点所在字符串的位置索引

Return:     剔除'-'和'.'后的字符串

Notes:      返回的字符串内存是在这个函数内部分配的，需要在函数外部进行内存释放

------------------------------------------------------------------------------------------*/

char *extract_string(char *sour, e_sign_type &sign, unsigned int &ndot)

{

       // 是否是负数的标示

       if ('-' == *sour)

              sign = ENUM_NEGATIVE;

       else

              sign = ENUM_POSITIVE;

       // 乘数是否是浮点数的标志，ndot是小数点的位数

       ndot = check_floating(sour);     

       unsigned int nlen = strlen(sour);

       if (ENUM_NEGATIVE == sign)  // 判断是否有负号

              nlen--;

       if (ndot > 0)   // 判断是否是浮点数

              nlen--;

       // new memory

       char *sz_ret = new char[nlen+1];

       memset(sz_ret, 0,  nlen+1);

       char *cur = sz_ret;

       if (0 == ndot)

       {

              // 如果是负数，则'-'号跳过

              if (ENUM_NEGATIVE == sign)

                     sour++;

              while (0 != *sour)

                     *cur++ = *sour++;

       }

       else

       {

              char *sz_inp = sour;

              if (ENUM_NEGATIVE == sign)

                     sz_inp++;

              while (0 != *sz_inp)

              {

                     if ('.' != *sz_inp)

                            *cur++ = *sz_inp++;

                     else

                            sz_inp++;

              }            

       }

       return sz_ret;

}

/*--------------------------------------------------------------------------------------

Function:   给输入的字符串添加字符'-'和'.'

Parameter:  sour:  输入的字符串

            sign:  传入的值，枚举

                     ndot:  传入的值, 0: 不是浮点数 其它值：小数点所在字符串的位置索引

Return:     添加'-'和'.'后的字符串

Notes:      返回的字符串内存是在这个函数内部分配的，需要在函数外部进行内存释放

------------------------------------------------------------------------------------------*/

char *recover_string(char *sour, e_sign_type sign, unsigned int ndot)

{

       int nlen = strlen(sour);

       if (ENUM_POSITIVE == sign)

              nlen++;     //如果是负数的话，长度加一，for '-'

       if (ndot > 0)

              nlen++;    //如果浮点数的话，长度加一，for '.'

       char *sz_ret = new char[nlen+1];

       memset(sz_ret, 0, nlen+1);

       // 特殊情况: sour等于

       if (0 == atoi(sour))

       {

              *sz_ret = 0x30;

              return sz_ret;

       }

       else

       {

              char *ret_cur = sz_ret;

              if (ENUM_NEGATIVE == sign)

              {

                     *ret_cur = '-';

                     ret_cur++;

              }

              // 考虑小数点左边的整数

              int nlen_int = strlen(sour)-ndot;  // 整数长度

              char *sz_int = new char[nlen_int+1];

              memset(sz_int, 0, nlen_int+1);

              memcpy(sz_int, sour, nlen_int);

              if (0 == atoi(sz_int))   // 整数部分全部为

              {

                     *ret_cur = 0x30;

                     ret_cur++;

              }

              else

              {

                     int num = 0;  // 即无用的个数，比如: 00011,即num = 3

                     char *cur = sz_int;

                     while(cur < sz_int+nlen_int)

                     {

                            if (0x30 == *cur)

                            {

                                   cur++;

                                   num++;

                            }

                            else

                                   break;

                     }

                     memcpy(ret_cur, sour+num, nlen_int-num);

                     ret_cur += (nlen_int-num);

              }

              delete []sz_int;

              sz_int = NULL;

              // 考虑小数部分, ndot即为小数部分的长度

              if (ndot > 0)

              {

                     char *pdeci = sour+strlen(sour)-ndot;

                     if (0 == atoi(pdeci))

                     {//do nothing

                     }

                     else

                     {

                            // 处理小数点

                            *ret_cur = '.';

                            ret_cur++;

                            int num = 0; // 小数位无效的个数，比如：.11000，即num为

                            char *end = sour+strlen(sour)-1;

                            while (pdeci < end)

                            {

                                   if (0x30 == *end)

                                   {

                                          end--;

                                          num++;

                                   }

                                   else

                                          break;

                            }

                            memcpy(ret_cur, pdeci, ndot-num);

                     }

                     }

              }

              return sz_ret;

       }

/*--------------------------------------------------------------------------------------

Function:   2个字符串相乘

Parameter:  mult1: 乘数，mult2: 乘数

Return:     两数相乘的结果

Condition:  1. 这个数可以是有符号的，也可以是浮点数

            2. 返回值的内存在这个函数里动态分配，注意在外部释放内存

------------------------------------------------------------------------------------------*/

char *mult_signed_num(char *mult1, char *mult2)

{

       if  ((NULL==mult1) && (NULL==mult2))

              return NULL;

       e_sign_type sign1 = ENUM_POSITIVE;     // 乘数是否是负数的标示

       e_sign_type sign2 = ENUM_POSITIVE;

       unsigned int ndot1 = 0;      // 乘数是否是浮点数的标志，ndot是小数点的位数

       unsigned int ndot2 = 0;

       char *sz_para1 = extract_string(mult1, sign1, ndot1);

       char *sz_para2 = extract_string(mult2, sign2, ndot2);    

       char *sz_res = mult_pos_int(sz_para1, sz_para2);

       if (NULL != sz_para1)

       {

              delete []sz_para1;

              sz_para1 = NULL;

       }

       if (NULL != sz_para2)

       {

              delete []sz_para2;

              sz_para2 = NULL;

       }

       char *sz_val = recover_string( sz_res,

                                                           (sign1==sign2) ? ENUM_POSITIVE : ENUM_NEGATIVE,

                                                           ndot1+ndot2);

       if (NULL != sz_res)

       {

              delete []sz_res;

              sz_res = NULL;

       }

       return sz_val;

}

int _tmain(int argc, _TCHAR* argv[])

{

              char sz1[256] = {0};

              cout << "pls enter num1" << endl;

              cin >> sz1;

              char sz2[256] = {0};

              cout << "pls enter num2" << endl;

              cin >> sz2;

              char *sz_res = mult_signed_num(sz1, sz2);

              cout << "num1 * num2 = " << endl;

              cout << sz_res << endl;

              if (NULL != sz_res)

              {

                     delete sz_res;

                     sz_res = NULL;

              }

      

              return 0;

}