大数乘法、大数加法实现

<span style="font-size:14px;">#include <iostream>
#include <stack>
#include <queue>
#include <algorithm>
#include <string.h>
#include <cstdio>
#include <stdlib.h>
#include <cctype>
using namespace std;


// 实现两个数的加法

// 判断一个字符串是否为有效的数
bool isValidNumber( const string &s )
{
	bool ret = true;
	int len = s.length();

	if( len <= 0 )
	{
		ret = false;
		return ret;
	}

	if( 1 == len && ( '+' == s[0] || '-' == s[0] ) )
	{
		ret = false;
		return ret;
	} 

	for( int i = 0; i < len; i++ )
	{
		if( 0 == isdigit( s[i] ) )
		{
			if( 0 == i && ( '+' == s[0] || '-' == s[0] ) )
			{
				continue;
			}
			else
			{
				ret = false;
				break;
			}
		}
	}
	
	return ret;
}


// 实现两个正数的加法
string twoPositivePlus( const string &lhs,const string &rhs )
{
	string result = "";

	if( !isValidNumber( lhs ) || !isValidNumber( rhs ) )
	{
		return result;
	}

	int len1 = lhs.length();
	int len2 = rhs.length();

	int len = len1 > len2 ? len1 + 2 : len2 + 2;

	result.resize(len);

	string lhs1 = lhs;
	string rhs1 = rhs;
		
	if( '+' == lhs[0] )
	{
		lhs1.assign( lhs,1,len1 - 1 );
	}
	
	if( '+' == rhs[0] )
	{
		rhs1.assign( rhs,len2 - 1 );
	}

	int len11 = lhs1.length();
	int len22 = rhs1.length();
	int i = 0;
	int j = 0;
	int up = 0;
	int idx = 0;

	for( i = len11 - 1,j = len22 - 1; i >= 0 && j >= 0; i--,j-- )
	{
		int add = ( lhs1[i] - '0' ) + ( rhs1[j] - '0' ) + up;
			
		if( add >= 10 )
		{
			add = add - 10;
			result[ idx++ ] = add + '0';
			up = 1;
		}
		else
		{
			result[ idx++ ] = add + '0';
			up = 0;
		}
				
	}


	while( i >= 0 )
	{
		int add = ( lhs1[i] - '0' ) + up;

		if( add >= 10 )
		{
			add = add - 10;
			result[ idx++ ] = add + '0';
			up = 1;
		}
		else
		{
			result[ idx++ ] = add + '0';
			up = 0;
		}

		i--;
	}

	while( j >= 0 )
	{
		int add = ( rhs1[j] - '0' ) + up;

		if( add >= 10 )
		{
			add = add - 10;
			result[ idx++ ] = add + '0';
			up = 1;
		}
		else
		{
			result[ idx++ ] = add + '0';
			up = 0;
		}

		j--;
	}

	if( 1 == up )
	{
		result[ idx++ ] = '1';
	}

	result[idx] = '';
	result.resize( idx + 1 );
	//result.reverse();
	for( i = 0,j = idx - 1; i < j; i++,j-- )
	{
		char ch = result[i];
		result[i] = result[j];	
		result[j] = ch;
	}
	
	return result;
	
}


// 正数加上负数
string posiveAddNegative( const string &lhs,const string &rhs )
{
	string result = "";

	if( !isValidNumber( lhs ) || !isValidNumber( rhs ) )
	{
		return result;
	}

	int len1 = lhs.length();
	int len2 = rhs.length();

	int len = len1 > len2 ? len1 + 2 : len2 + 2;

	result.resize(len);
	string lhs1 = lhs;
	string rhs1 = rhs;
		
	if( '+' == lhs[0] )
	{
		lhs1.assign( lhs,len1 - 1 );
	}
	
	if( '-' == rhs[0] )
	{
		rhs1.assign( rhs,len2 - 1 );
	}

	int flag = lhs1.compare( rhs1 );

	if( 0 == flag )
	{
		return "0";
	}

	int isMinus = 0;

	int len11 = lhs1.length();
	int len22 = rhs1.length();
	
	if( ( len11 == len22 && flag < 0 ) || len11 < len22 )
	{
		string tmp = lhs1;
		lhs1 = rhs1;
		rhs1 = tmp;
		isMinus = 1;
	}

	int up = 0;
	int idx = 0;
	int i = 0;
	int j = 0;

	len11 = lhs1.length();
	len22 = rhs1.length();
	//cout << lhs1 << ' ' << rhs1 << endl;

	for( i = len11 - 1,j-- )
	{
		int minus = ( lhs1[i] - '0' - up ) - ( rhs1[j] - '0' );
			
		if( minus < 0 )
		{
			up = 1;
			result[ idx++ ] = minus + 10 + '0';
			
		}	
		else
		{
			up = 0;
			result[ idx++ ] = minus + '0';

		}		
		
	}

	//cout << i << ' ' << j << ' ' << result[0] << endl;

	while( i >= 0 )
	{
		int minus = ( lhs1[i] - '0' - up );
		//cout << minus << endl;
		if( minus < 0 )
		{
			up = 1;
			result[ idx++ ] = minus + 10 + '0';
		}	
		else
		{
			up = 0;
			result[ idx++ ] = minus + '0';
		}		
		
		i--;
	}

	while( j >= 0 )
	{
		int minus = ( rhs1[j] - '0' - up );
			
		if( minus < 0 )
		{
			up = 1;
			result[ idx++ ] = minus + 10 + '0';
		}	
		else
		{
			up = 0;
			result[ idx++ ] = minus + '0';
		}		
		
		j--;
	}

	result[idx] = '';
	//result.resize( idx + 1 );
	//cout << "result=" << result << endl;
	
	for( i = 0,j-- ) //逆置一下
	{
		char ch = result[i];
		result[i] = result[j];	
		result[j] = ch;
	}

	//cout << idx << ' ' <<  "result=" << result << endl; // 0001

	int k = 0;
	int cur = 0;

	while( '0' == result[k] )
	{
		k++;
	}

	while( k <= idx )
	{
		result[ cur++ ] = result[ k++ ];
	}

	result[cur] = '';
	result.resize( cur + 1 ); //预留一个字符给符号位 

	//cout << result << " sf" << ' ' << cur << endl;
	idx = cur;

	if( 1 == isMinus ) //结果为负数
	{
		
		for( i = idx - 1; i >= 0; i-- )
		{
			result[ i + 1 ] = result[i];
		}

		result[0] = '-';
		result[ idx + 1 ] = '';
		result.resize( idx + 2 );
	}

	//cout << result << endl;
	return result;
}

int judgeAddType( const string &s1,const string &s2 )
{
	int type = 0;
	
	if( !isValidNumber(s1) || !isValidNumber(s2) )
	{
		type = -1;
		return type;
	}

	if( s1[0] != '-' && s2[0] != '-' ) 
	{
		type = 0;
	}
	else if( s1[0] != '-' && '-' == s2[0] )
	{
		type = 1;
	}
	else if( '-' == s1[0] && s2[0] != '-' )
	{
		type = 2;
	}
	else if( '-' == s1[0] && '-' == s2[0] )
	{
		type = 3;
	}
	
	return type;
}

// 大数乘法
/*

思想：
	    0  1  2  3  4
	          0  1  2
	-----------------------
        20  21  22  23  24
    10  11  12  13  14
00  01  02  03  04
------------------------------------

*/

string multipy( const string &s1,const string &s2 )
{
	string ret = "";

	if( !isValidNumber(s1) || !isValidNumber(s2) )
	{
		cout << "multipy func: err -1,!isValidNumber(s1) || !isValidNumber(s2)" << endl;
		return ret;
	}

	// 任意元素为0，乘积为0
	if( ( 1 == s1.length() && '0' == s1[0] ) || ( 1 == s2.length() && '0' == s2[0] ) )
	{
		return "0";
	}
	
	bool isPositive = true;

	if( ( '-' == s1[0] && s2[0] != '-' ) || ( s1[0] != '-' && '-' == s2[0] ) )
	{
		isPositive = false;
	}

	string ss1 = s1;
	string ss2 = s2;

	if( !isdigit(s1[0]) )
	{
		ss1.assign( s1,s1.length() - 1 );	
	}

	if( !isdigit(s2[0]) )
	{
		ss2.assign( s2,s2.length() - 1 );	
	}
	
	int len1 = ss1.length();
	int len2 = ss2.length();
	int *pResult = new int[ len1 + len2 ];

	if( NULL == pResult )
	{
		cout << "multipy func: err -1,NULL==pResult" << endl;
		return ret;
	}	

	for( int i = 0; i < len1 + len2; i++ )
	{
		pResult[i] = 0;
	} 

	for( int i = len1 - 1; i >= 0; i-- )
	{
		for( int j = len2 - 1; j >= 0; j-- )
		{
			pResult[ i + j + 1 ] += ( ss1[i] - '0' ) * ( ss2[j] - '0' );
		}
	}

	for( int i = len1 + len2 - 1; i >= 1; i-- )
	{
		if( pResult[i] >= 10 )
		{
			pResult[ i - 1 ] += pResult[i] / 10;
			pResult[i] %= 10;
		}
	}

	char *pch = new char[ len1 + len2 + 1 ];
	
	if( NULL == pch )
	{
		cout << "multipy func: err -1,NULL == pch" << endl;
	}
	
	int k = 0;
	

	while( 0 == pResult[k] ) // 跳过头部0元素
	{
		k++;
	}

	int idx = 0;

	if( !isPositive )
	{
		idx = 1;
	}

	for( ; k < len1 + len2; k++ )
	{
		pch[ idx++ ] = pResult[k] + '0';
	}

	pch[idx] = '';

	if( !isPositive )
	{
		pch[0] = '-';
	}

	string result(pch);

	delete []pch;
	pch = NULL;
	delete []pResult;
	pResult = NULL;

	return result;
}



int main()
{
	int ret = 0;

	string s1;
	string s2;

	while( cin >> s1 >> s2 )
	{
		cout << multipy( s1,s2 ) << endl;

		int type = judgeAddType( s1,s2 );
	
		if( -1 == type )
		{
			cout << "error input" << endl;
			ret = -1;
			return ret;
		}
		else if( 0 == type ) // 正+正
		{
			cout << twoPositivePlus( s1,s2 ) << endl;
		}
		else if( 1 == type ) // 正+负
		{
			cout << posiveAddNegative( s1,s2 ) << endl;
		}
		else if( 2 == type ) // 负+正
		{
			cout << posiveAddNegative( s2,s1 ) << endl;
		}
		else if( 3 == type ) // 负+负
		{
			string tmp1;
			tmp1.assign( s1,s1.length() - 1 );

			string tmp2;
			tmp2.assign( s2,s2.length() - 1 );
	
			cout << "-" << twoPositivePlus( tmp1,tmp2 ) << endl;
		}
	}

	return ret;
}

</span>

（编辑：东莞站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!