表达式求值

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67

namespace CAL {
    int expression(char*&s);  // 计算一个不带括号的表达式值
    int token(char*&s) {      // 取出一个值加入到栈中
        if(*s == '(') {
            s ++;
            int ret = expression(s);
            s ++;
            return ret;
        }
        int ret = 0;
        while('0' <= *s && *s <= '9'){
            ret = ret * 10 + *s++ - '0';
        }
        return ret % mod;
    }
    int rank(char op) {
        switch(op) {
            case '-': return 1;
            case '+': return 1;
            case '*': return 0;
        }
        return 2;
    }
    int expression(char*&s){
        stack<int> svar;
        stack<char> sop;
        svar.push(token(s));
        while(true){
            char op = *s;
            if(!op || op == ')') op = '$';
            else s++;
            while(!sop.empty() && rank(sop.top()) <= rank(op)){
                int b = svar.top();
                svar.pop();
                int a = svar.top();
                svar.pop();
                switch(sop.top()){
                    case '+':{
                        svar.push(a + b);
                        break;
                    }
                    case '-':{
                        svar.push(a - b);
                        break;
                    }
                    case '*': {
                        svar.push(a * b);
                        break;
                    }
                }
                sop.pop();
            }
            if(op == '$') break;
            svar.push(token(s));
            sop.push(op);
        }
        return svar.top();
    }
}
char s[MAXN];
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> s;
	char *test = s;
	cout << CAL::expression(test);
}