表达式求值模板
class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * 返回表达式的值 * @param s string字符串 待计算的表达式 * @return int整型 */ int solve(string s) { // write code here int n = s.size(); int i = 0; stack<char>op; stack<int> sk; unordered_map<char, int> f ; f['+'] = f['-'] = 1; f['*'] = f['/'] = 2; while (i < n) { if (s[i] == ' ') { i++; continue; } if (s[i] == '(') { op.push(s[i++]); } else if (s[i] == ')') { while (op.size() && op.top() != '(' && f[op.top()] >= f[s[i]]) sk.push(todo(sk, op)); if (op.top() == '(') op.pop(); i++; } else if (s[i] >= '0' && s[i] <= '9') { int val = eat(s, i); sk.push(val); } else { if (i == 0) sk.push(0); while (op.size() && op.top() != '(' && f[op.top()] >= f[s[i]]) sk.push(todo(sk, op)); op.push(s[i++]); } } while (op.size()) sk.push(todo(sk, op)); return sk.top(); } int todo(stack<int>& sk, stack<char>& op) { int a = sk.top(); sk.pop(); int b = sk.top(); sk.pop(); char p = op.top(); op.pop(); printf("%d %c %d\n", b, p, a); switch (p) { case '+': return b + a; case '-': return b - a; case '*': return b * a; case '/': return b / a; case '(': { puts("error"); } } return -1; } int eat(string& s, int& i) { int val = 0; while (s[i] >= '0' && s[i] <= '9') { val = val * 10 + (s[i++] - '0'); } return val; } }; #ifdef debug int main() { cout << " * " << endl; Solution k; auto arr = {1, 2, 3, 3, 5}; cout << "result: " << k.solve("3+2*3*4-1") << endl; return 0; } #endif