LeetCode Basic Calculator II Implement a basic calculator to evaluate a simple expression string. The expression string contains only non-negative integers, +, -, *, / operators and empty spaces . The integer division should truncate toward zero. You may assume that the given expression is always valid. Some examples:

"3+2*2" = 7
" 3/2 " = 1
" 3+5 / 2 " = 5

Note: Do not use the eval built-in library function.

---

本题是LeetCode Basic Calculator的简化版，去掉了括号，增加了乘除法。但是算法都是一模一样的，先把中缀转换为后缀，然后用栈求值。 代码如下： [cpp] // 优先级 unordered_map<string, int> priority = { {"+", 1},{"-", 1},{"*", 2},{"/", 2} }; class Solution { private: void push(stack<string> &numbers, stack<string> &opers, const string& numOrop) { if (isdigit(numOrop[0])) { numbers.push(numOrop); } else { if (numOrop == ")") { while (opers.top() != "(") { numbers.push(opers.top()); opers.pop(); } opers.pop(); } else if (numOrop == "(") { opers.push(numOrop); } else if (opers.empty() || opers.top() == "(") { opers.push(numOrop); } else if (priority[numOrop] > priority[opers.top()]) { opers.push(numOrop); } else { while (!opers.empty() && opers.top() != "(" && priority[numOrop] <= priority[opers.top()]) { numbers.push(opers.top()); opers.pop(); } opers.push(numOrop); } } } // 中缀转后缀表达式 list<string> in2post(const string& s) { stack<string> numbers, opers; int start = 0, end = 1, n = s.size(); while (start < n) { while (start < n&&s[start] == ‘ ‘)++start; if (start >= n)break; if (isdigit(s[start])) { end = start + 1; while (end < n&&isdigit(s[end]))++end; string num = s.substr(start, end – start); push(numbers, opers, num); start = end; } else { string op = string(1, s[start]); push(numbers, opers, op); ++start; } } while (!opers.empty()) { numbers.push(opers.top()); opers.pop(); } list<string> ans; while(!numbers.empty()) { ans.push_front(numbers.top()); numbers.pop(); } return ans; } // 求值后缀表达式的值 int eval(list<string>& post) { int ans = 0; stack<int> numbers; for (const auto& s : post) { if (priority.find(s) != priority.end()) { int num2 = numbers.top(); numbers.pop(); int num1 = numbers.top(); numbers.pop(); if (s == "+")numbers.push(num1 + num2); else if (s == "-")numbers.push(num1 – num2); else if (s == "*")numbers.push(num1*num2); else numbers.push(num1 / num2); } else numbers.push(stoi(s)); } return numbers.top(); } public: int calculate(string s) { list<string> ans = in2post(s); return eval(ans); } }; [/cpp] 本代码提交AC，用时85MS。]]>