2016 UESTC Training for Data Structures N – 秋实大哥搞算数 用栈处理表达式

Source

2016 UESTC Training for Data Structures  Problem N

My Solution

用栈处理表达式

直接STL里的stack

先讨论第一个字符是不是'-'

如果是则记录符号

如果不是则第一个数入栈

然后每次如果+val则直接入栈

              如果-val则把-val入栈

      如果*或/ 则pop()出栈顶了计算表达式，把结果入栈

处理完后把栈里的东西加起来就好了，直到栈为空

复杂度 O(n);

#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef long long LL;
const int maxn = 1e6 + 8;

stack sta;
char line[maxn];

int main()
{
    #ifdef LOCAL
    freopen("a.txt", "r", stdin);
    #endif // LOCAL
    int T;
    LL ans, val;
    scanf("%d", &T);
    while(T--){
        string str;
        char op = '+';
        scanf("%s", line);
        ans = 0;
        int len = strlen(line), sz;
        if(isalnum(line[0])) str = line[0];
        else op = '-';
        for(int i = 1; i < len; i++){
            if(isalnum(line[i])) str += line[i];
            else {
                sz = str.size();
                val = 0; //initialize should be put in the front, unless the first one will be wrong
                for(int j = 0; j < sz; j++){
                    val += (str[j]-'0')*pow(10, sz - j - 1);//cout<<pow(10, (sz - j - 1))<<endl;
                }
                //cout<<str<<endl;
                if(op == '+')sta.push(val);
                else if(op == '-') sta.push(-val);
                else if(op == '*') {LL preval = sta.top();sta.pop();sta.push(preval*val);}
                else if(op == '/') {LL preval = sta.top();sta.pop();sta.push(preval/val);}
                val = 0;
                op = line[i];
                str.clear();
                //cout<<sta.top()<<endl;
            }
        }
        // to progress the last val which has not been add to val and push into stack
        sz = str.size();
        for(int j = 0; j < sz; j++){
            val += (str[j]-'0')*pow(10, sz - j - 1);
        }
        if(op == '+')sta.push(val);
        else if(op == '-') sta.push(-val);
        else if(op == '*') {LL preval = sta.top();sta.pop();sta.push(preval*val);}
        else if(op == '/') {LL preval = sta.top();sta.pop();sta.push(preval/val);}

        ans = sta.top();sta.pop();
        while(!sta.empty()){
            ans += sta.top();
            sta.pop();
        }
        printf("%lldn", ans);
    }
    return 0;
}

非特殊说明，本博所有文章均为博主原创，未经许可不得转载。

https://www.prolightsfxjh.com/

Thank you!

                                                                                                                                             ------from ProLightsfx