逆波兰表达式 栈表达式计算

#include<bits/stdc++.h>
using namespace std;
#define LL long long
const int MAXN = 1000010;
string res[MAXN];
stack<string>St;
LL num[MAXN];
int topn,len,tops;
string str;
string ret[MAXN];

bool judgenum(string tmp) {
    if (isdigit(tmp[0])) return true;
    else if (tmp[0] == '-' && tmp.size() >= 2 && isdigit(tmp[1])) return true;
    return false;
}

bool comp(string &a,string &b) {
    if (b == "(") return true;
    if ((a == "*" || a == "/") && (b == "+" || b == "-")) return true;
    return false;
}

bool isoperator (string & a) {
    if (a == "+" || a == "-"  || a == "*" || a == "/"  || a == "(" || a == ")")  return true;
    return false;
}


void transto_RPN() {
    tops = 0;
    while (!St.empty()) St.pop();
    for (int i = 0 ; i < len ; i++) {
        if (ret[i].size() == 1 && isoperator(ret[i])) {
            if (St.empty()) St.push(ret[i]);
            else if (ret[i] == "(") {
                St.push(ret[i]);
            }
            else if (ret[i] == ")") {
                while (St.top() != "(") {
                    res[tops++] = St.top();
                    St.pop();
                }
                St.pop();
            }
            else {
                if (comp(ret[i],St.top())) St.push(ret[i]);
                else {
                    while (!St.empty() && comp(ret[i],St.top()) == false) {
                        res[tops++] = St.top();
                        St.pop();
                    }
                    St.push(ret[i]);
                }
            }
        }
        else {
            res[tops++] = ret[i];
        }
    }
    while (!St.empty()) {
        res[tops++] = St.top();
        St.pop();
    }
}

void debug() {
    for (int i = 0 ; i < len ; i++) cout << ret[i] << endl;
    cout << endl;
    for (int i = 0 ; i < tops ; i++) cout << res[i] << endl;
}

LL myatol(string str) {
    bool negative = false,st = 0;
    if (str[0] == '-') {negative = true; st++;}
    LL x = 0;
    for (int i = st ; i < str.size() ; i++)
        x = x * 10 + str[i] - '0';
    if (negative) x = x * -1;
    return x;
}

LL calcu() {
    topn = 0;
    for (int i = 0 ; i < tops ; i++) {
        if (judgenum(res[i])) {
            LL val = myatol(res[i]);
            num[topn++] = val;
        }
        else {
            LL b = num[--topn];
            LL a = num[--topn];
            LL answ;
            if (res[i][0] == '+') answ = a + b;
            else if (res[i][0] == '-') answ = a - b;
            else if (res[i][0] == '*') answ = a * b;
            else answ = a / b;
            num[topn++] = answ;
        }
    }
    return num[0];
}

int main() {
    int T;
    scanf("%d",&T);
    while (T--) {
        len = 0;
        cin >> str;
        for (int i = 0 ; i < str.size() ; ) {
            string tmp = "";
            if (isdigit(str[i])) {
                int j = i;
                while (j < str.size() && isdigit(str[j]))
                    j++;
                tmp = str.substr(i,j - i);
                ret[len++] = tmp;
                i = j;
            }
            else {
                tmp = str.substr(i,1);
                ret[len++] = tmp;
                i++;
            }
        }
        transto_RPN();
        //debug();
        LL ret = calcu();
        cout << ret << endl;
    }
    return 0;
}