// Basic Calculator // operator-precedence parser class Solution { public: int calculate(string s) { stack xs; stack ops; map isp, icp; isp['\0'] = 0; isp['+'] = 3; isp['-'] = 3; isp['('] = 1; icp['\0'] = 0; icp['+'] = 2; icp['-'] = 2; icp['('] = 4; icp[')'] = 1; ops.push('\0'); for (size_t i = 0; i <= s.size(); ) { char op = i == s.size() ? '\0' : s[i]; if (op == ' ') i++; else if (isdigit(op)) { int x = 0; do x = x*10+s[i]-'0'; while (isdigit(s[++i])); xs.push(x); // shift } else { i++; int x, y; for (; isp[ops.top()] > icp[op]; ops.pop()) { y = xs.top(); xs.pop(); x = xs.top(); xs.pop(); xs.push(ops.top() == '+' ? x+y : x-y); // reduce, X '+' Y => X+Y or X '-' Y => X-Y } if (isp[ops.top()] == icp[op]) // reduce, '(' X ')' => X or '\0' X '\0' => X ops.pop(); else ops.push(op); // shift } } return xs.top(); } };