開發平台(Platform): (Ex: Win10, Linux, ...)
win10
編譯器(Ex: GCC, clang, VC++...)+目標環境(跟開發平台不同的話需列出)
devc++
額外使用到的函數庫(Library Used): (Ex: OpenGL, ...)
string
問題(Question)：
由左至右算大數 算太慢
餵入的資料(Input)：
1+2*3
預期的正確結果(Expected Output)：
9
錯誤結果(Wrong Output)：
程式碼(Code)：(請善用置底文網頁, 記得排版，禁止使用圖檔)
#include <iostream>
#include <algorithm>
#include <sstream>
#include <string>
using namespace std;
string bigadd(string a,string b);// a=300 b=40000 return 40300
string bigtime(string a,string b);//a=30 b=200000 return 6000000
string simplify(string a);//a=20 return 20 a=0030 return 30
int main(){
int i,j;
int doing;
//0 means there is no operator infront, 1 means there is +infront, 2 means there is * infront
string line,newline;
//input an expression "3+2*1" and output an number "5",
string temp;
while(getline(cin, line))
{
newline="";
doing=0;
temp="";
if(line!="")
{
for(i=0;i<line.size();i++)
{
if('0'<=line[i]&&line[i]<='9')
{
temp+=line[i];//put numbers into temp
}
if(line[i]=='*')//when we find an operator
{
if(doing==0)//check if there is another operator infront, if not
{
newline+=temp;//then store the number of temp into newline
temp="";
doing=2;//turn doing to 2 to tell the program that we found * in the line
}
else if(doing==2)//if there is, do the multiiply
{
newline=(temp.size()>newline.size())?bigtime(temp,newline):bigtime(newline,temp);//and
store it into newline
temp="";
doing=2;
}
else if(doing==1)//or add
{
newline=bigadd(temp,newline);//and store it into newline
temp="";
doing=2;
}
}
if(line[i]=='+')
{
if(doing==0)
{
newline+=temp;
temp="";
doing=1;
}
else if(doing==2)
{
newline=(temp.size()>newline.size())?bigtime(temp,newline):bigtime(newline,temp);
temp="";
doing=1;
}
else if(doing==1)
{
newline=bigadd(temp,newline);
temp="";
doing=1;
}
}
}
if(doing==0)
{
cout<<simplify(temp);
}
else if(doing==2)
{
newline=(temp.size()>newline.size())?bigtime(temp,newline):bigtime(newline,temp);
cout<<newline;
}
else if(doing==1)
{
cout<<bigadd(temp,newline);
}
}
cout<<endl;
}
return 0;
}
//////////////////////////////////////////////////
string bigtime(string temp,string timer)
{
int c=0;
string timetemp;
string result;
char tempp;
result="0";
int i,j,carry;
reverse(temp.begin(), temp.end());//turn 45678 123 to 87654 321
reverse(timer.begin(), timer.end());
j=0;
while(j<timer.size())//j means the number of digits of timer
{
timetemp="";
i=0;
carry=0;
while(1)
{
if(i<temp.size())
{
tempp=temp[i];
}
else
{
tempp='0';
}
tempp-='0';
tempp*=(timer[j]-'0');
tempp+=carry;
carry=tempp/10;
tempp%=10;
tempp+='0';
timetemp+=tempp;
if(carry==0&&i>=temp.size()-1)
{
break;
}
i++;
}
reverse(timetemp.begin(), timetemp.end());
for(i=0;i<j;i++)
{
timetemp+="0";
}
result=bigadd(result,timetemp);
j++;
}
return result;
}
string bigadd(string acc,string add)
{
int i=0;
int carry=0;
string temp="";
char tempp;
reverse(acc.begin(), acc.end());
reverse(add.begin(), add.end());
i=0;
carry=0;
temp="";
while(1)
{
tempp=carry+48;
if(i<acc.size())
{
tempp+=acc[i]%48;
}
if(i<add.size())
{
tempp+=add[i]%48;
}
carry=(tempp-48)/10;
tempp=(tempp-48)%10+48;
temp+=tempp;
if(carry==0)
{
if(i>=acc.size()-1&&i>=add.size()-1)
{
break;
}
}
i++;
}
acc=temp;
reverse(acc.begin(), acc.end());
return simplify(acc);
}
string simplify(string a)
{
int i=0,xx=0;
string s,d;
s="";
d="";
while(i<a.size())
{
if(a[i]!='0')
{
xx=1;
}
if(xx==1)
{
s+=a[i];
}
i++;
}
if(s=="")
{
s="0";
}
return s;
}
補充說明(Supplement)：
我是在寫一個程式題目 input<10MB 由正整數,+,*組成
某些測試資料可以在時間內算出正確答案
另一部分測試資料會TLE
有點不知道遇到這種問題該怎麼處理
是因為某種情況讓我的程式出現無窮迴圈的關係
還是我的程式真的不夠快
用string 儲存數據 中間用很多reverse
不知道是string可能在過程中溢位?
還是reverse其實會浪費時間?
希望能得到建議