大數運算，
運算元只有+ - * 還有**(指數)，
輸入測資的運算子都是正數，
所以不會有像 -2+2 這樣的測資
但是像 2-2 這樣的測資是可以的喔
還有指數是由後面往前算
所以2**2**3 = 2**(2**3) = 2**8 = 256
0**0=1，
0**0**0 = 0**(0**0) = 0**1 = 0
--------------------------------------------------
我的作法:
我是用C++..好辛苦
首先要先將輸入的柿子做分割，
分割成運算元和運算子兩堆
並分別用陣列存取，
例如:
12345678*129876+2**1993
變成
12345678 129876 2 1993
和
* + **
運算要先從指數開始做，再做乘，最後做加和減
舉個例子:
1**2+3*4+5*6-7**0
運算7**0，(指數要從後面開始做)
然後將運算結果放回式子，1**2+3*4+5*6-1
然後運算1**2，
一樣將運算結果放回式子，1+3*4+5*6-1
指數做完換做乘法，
1+12+5*6-1
1+12+30-1
乘做完最後做加和減
13+30-1
43-1
42
要拿一個運算子和兩個運算元出來做運算，就是從剛剛那兩個陣列去拿，
例如在運算子的陣列裡，[6]="**"，
而相對應的運算元的陣列中，[6]和[7]就是 7 和 0 ，也就是要做運算的兩個運算元!
注意做完運算後要把那兩個運算元和那個運算子刪掉，
並將運算結果再放回運算元陣列!
再來就是自訂大數型別了，
我使用1個大陣列，
最多3000位數，所以可以開750個格子就好，
每個格子存4個位數(10000進位)，
例如:數字1234567890，
陣列[0][1][2]分別存[ 7890 ] [ 3456 ] [ 12 ] 。
還有需要一個記號表示該大數的正負。
重載有用到的運算子，
+ ,- ,* ,^(指數) ,<
在處理運算元有幾點需要注意的
。不管做哪個運算，最後運算完都需要進位
。需要注意正負數
+:
A(正)+B(正)直接做A+B，
A(負)+B(負)直接做A+B，最後結果再作負數記號，
A(負)+B(正)可以換成B-A
不會有A(正)+B(負)的情形
-:
A-B要先判斷A跟B誰比較大，然後用大的減小的，再看有沒有負號
*:
正*正=正，負*負=正，正*負=負，負*正=負
。判斷A<B，先判斷正負數後，然後判斷位數，最後再從最高位數開始判斷
。輸出時除了最高位數的數字以外，小於1000的都要補0
--------------------------------------------------
/* 20150929
* hanting
* UVa 288 - Arithmetic Operations With Large Integers
* C++
*/
#include <iostream>
#include <vector>
#include <cstdlib> //atoi
#include <cstring> //strtok
#include <iomanip> //setw ,setfill
using namespace std;
#define BNum B.Num
#define Bdigit B.digit
struct BigInteger
{
bool sign;//1(-),0(+)
int Num[1001];
int digit;
BigInteger(string num="");
BigInteger operator+(BigInteger &B);
BigInteger operator-(BigInteger &B);
BigInteger operator*(BigInteger &B);
BigInteger operator^(BigInteger &B);
bool operator<(BigInteger &B);
bool IsZero();
void operator--(int);
void operator*=(BigInteger &B);
void CountDigit();
friend ostream& operator<<(ostream& out,BigInteger &B);
};
int main()
{
string expression,tmp;
while(cin>>expression)
{
copy(expression.begin(),expression.end(),back_inserter(tmp));
vector<BigInteger> num;
vector<string> op;
char *pch=strtok((char*)expression.c_str(),"+-*");
while(pch)
{
num.push_back(BigInteger(pch));
pch=strtok(NULL,"+-*");
}
expression=tmp;
pch=strtok((char*)expression.c_str(),"0123456789");
while(pch)
{
op.push_back(pch);
pch=strtok(NULL,"0123456789");
}
for(int i=op.size()-1;i>=0;i--)
{
if(op[i]=="**")
{
num[i]=num[i]^num[i+1];
op.erase(op.begin()+i);
num.erase(num.begin()+i+1);
}
}
for(int i=0;i<op.size();i++)
{
if(op[i]=="*")
{
num[i]=num[i]*num[i+1];
num.erase(num.begin()+i+1);
op.erase(op.begin()+i);
i--;
}
}
for(int i=0;i<op.size();i++)
{
if(op[i]=="+") num[i]=num[i]+num[i+1];
else if(op[i]=="-")num[i]=num[i]-num[i+1];
num.erase(num.begin()+i+1);
op.erase(op.begin()+i);
i--;
}
cout<<num[0]<<endl;
tmp.clear();
}
return 0;
}
BigInteger::BigInteger(string str):sign(0),digit(0),Num{0}
{
while(str.size()>4)
{
string tmp=str.substr(str.size()-4);
Num[digit++]=atoi(tmp.c_str());
str.erase(str.size()-4,4);
}
if(str.size())
{
Num[digit++]=atoi(str.c_str());
}
}
void BigInteger::CountDigit()
{
for(int i=1000;i>=0;i--)
{
if(Num[i]!=0)
{
digit=i+1;
return ;
}
}
}
void BigInteger::operator--(int)
{
if(digit<=0) return ;
Num[digit-1]--;
for(int i=0;i<digit-1;i++)
{
Num[i]+=9999;
}
CountDigit();
for(int i=1;i<digit;i++)
{
Num[i]+=Num[i-1]/10000;
Num[i-1]%=10000;
}
CountDigit();
}
void BigInteger::operator*=(BigInteger &B)
{
*this=(*this)*B;
}
bool BigInteger::IsZero()
{
return digit==1 and Num[0]==0;
}
bool BigInteger::operator<(BigInteger &B)
{
if(sign==B.sign)
{
if(sign==0)//都是正數
{
if(digit<Bdigit) return true;
else if(digit==Bdigit)
{
for(int i=digit-1;i>=0;i--)
{
if(Num[i]<BNum[i]) return true;
else if(Num[i]==BNum[i]) continue;
else return false;
}
}
else return false;
}
else//都是負數
{
if(digit<Bdigit) return false;
else if(digit==Bdigit)
{
for(int i=digit-1;i>=0;i--)
{
if(Num[i]<BNum[i]) return false;
else if(Num[i]==BNum[i]) continue;
else return true;
}
}
else return true;
}
}
else if(sign==1 and B.sign==0)//負數<正數
{
return true;
}
else//正數<負數
{
return false;
}
}
BigInteger BigInteger::operator+(BigInteger &B)
{
BigInteger result;
if(sign==B.sign)
{
for(int i=0;i<digit or i<Bdigit;i++)
{
result.Num[i]+=Num[i]+BNum[i];
result.Num[i+1]+=result.Num[i]/10000;
result.Num[i]%=10000;
}
}
else//-3+2
{
this->sign=0;
result=B-(*this);
}
result.CountDigit();
return result;
}
BigInteger BigInteger::operator-(BigInteger &B)
{
BigInteger result;
if(*this<B)
{
result.sign=1;//負數
if(Bdigit>1)
{
BNum[Bdigit-1]--;
for(int i=Bdigit-2;i>0;i--)
{
BNum[i]+=9999;
}
BNum[0]+=10000;
for(int i=0;i<Bdigit;i++)
{
if(sign==0) result.Num[i]=BNum[i]-Num[i];
else result.Num[i]=BNum[i]+Num[i];
}
}
else
{
if(sign==0)result.Num[0]=BNum[0]-Num[0];
else result.Num[0]=BNum[0]+Num[0];
}
}
else
{
if(digit>1)
{
Num[digit-1]--;
for(int i=digit-2;i>0;i--)
{
Num[i]+=9999;
}
Num[0]+=10000;
for(int i=0;i<digit;i++)
{
result.Num[i]=Num[i]-BNum[i];
}
}
else
{
result.Num[0]=Num[0]-BNum[0];
}
}
for(int i=1;i<Bdigit or i<digit;i++)
{
result.Num[i]+=result.Num[i-1]/10000;
result.Num[i-1]%=10000;
}
result.CountDigit();
return result;
}
BigInteger BigInteger::operator*(BigInteger &B)
{
BigInteger result;
if(sign) result.sign=!result.sign;
if(B.sign) result.sign=!result.sign;
for(int i=0;i<digit;i++)
{
for(int j=0;j<Bdigit;j++)
{
result.Num[i+j]+=Num[i]*BNum[j];
}
}
for(int i=1;i<digit+Bdigit;i++)
{
result.Num[i]+=result.Num[i-1]/10000;
result.Num[i-1]%=10000;
}
result.CountDigit();
return result;
}
BigInteger BigInteger::operator^(BigInteger &B)
{
BigInteger result("1");
while(!B.IsZero())
{
result*=(*this);
B--;
}
return result;
}
ostream& operator<<(ostream& out,BigInteger &B)
{
if(Bdigit==0) out<<0;
else
{
if(B.sign) cout<<"-";
if(Bdigit) cout<<BNum[Bdigit-1];
for(int i=Bdigit-2;i>=0;i--)
{
out<<setw(4)<<setfill('0')<<BNum[i];
}
}
return out;
}
沒有留言:
張貼留言