[問題] 基礎大數乘法TLE 求改善

[applejuice64 (凝時)]

開發平台(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其實會浪費時間?
希望能得到建議

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.113.90.205
※ 文章網址: https://www.ptt.cc/bbs/C_and_CPP/M.1552895971.A.A8B.html
※ 編輯: applejuice64 (140.113.90.205), 03/18/2019 16:01:32
※ 編輯: applejuice64 (140.113.90.205), 03/18/2019 16:09:13
推 firejox: google fast integer multiplication algorithm
推 TitanEric: reverse要n 應該可以不用太特別的大數乘法才對
推 HanaYukii: 修競程一辛苦了XD
→ HanaYukii: 測資真的滿多坑的
→ TitanEric: 原來是競技程式 菜逼八我乖乖退下
推 lc85301: 1+2*3 預期結果 9？