[C++知识库]NOIP 2013 普及组 表达式求值

#include <bits/stdc++.h>
using namespace std;

stack <int> a;      //数据栈 
stack <char> b;     //符号栈 
map <char, int> m;

//取出两个数字和一个运算符进行运算，结果放进数据栈 
void calc() {
    int x = a.top(); 	a.pop();
    int y = a.top(); 	a.pop();
    char op = b.top(); 	b.pop();
	
    if (op == '+') a.push((y + x) % 10000);
    if (op == '*') a.push((y * x) % 10000);
}

int main() {
    m['+'] = 1;	m['*'] = 2;
	
	string s;
    cin >> s;
    s += '+';
    for (int i = 0; i < s.size(); i ++) {
    	char c = s[i];
    	
        if (isdigit(c)) {
            int j = i, num = 0;
            while (j < s.size() && isdigit(s[j])) {
                num = num * 10 + s[j] - '0';
                j ++;
            }
            a.push(num % 10000);
            i = j - 1;
        }
        else {
            //把符号栈里优先级大于等于自己的运算做完 
            while (b.size() && m[c] <= m[b.top()]) {
                calc();
            }
            b.push(c);   //把新运算放进符号栈 
        }
    }
    cout << a.top();

    return 0;
}