Implement a basic calculator to evaluate a simple expression string.
The expression string may contain open ( and closing parentheses ), the plus + or minus sign -, non-negative integers and empty spaces .
You may assume that the given expression is always valid.
Some examples:
"1 + 1" = 2 " 2-1 + 2 " = 3 "(1+(4+5+2)-3)+(6+8)" = 23
Note: Do not use the eval built-in library function.
Subscribe to see which companies asked this question
解法1：对于一般四则运算，包含括号的表达式计算一般先将中缀表达式转为前缀或者后缀表达式，再进行计算。
（1）中缀表达式转前缀表达式再计算：
class Solution { public: int calculate(string s) { stack<string> preExp; // 去除表达式中的空格 int k = 0; for (int i = 0; i < s.size(); ++i) { if (s[i] != ‘ ‘) s[k++] = s[i]; } s.resize(k); // 中缀表达式转前缀表达式 midExpToPreExp(s, preExp); // 求解前缀表达式 stack<string> preExp2; while (!preExp.empty()) { preExp2.push(preExp.top()); preExp.pop(); } int res = calcPreExp(preExp2); return res; } private: void midExpToPreExp(const string& midExp, stack<string>& preExp) { stack<char> tmp; // 运算符栈 for (int i = midExp.size() - 1; i >= 0; --i) { if (midExp[i] >= ‘0‘ && midExp[i] <= ‘9‘) { // 操作数直接入前缀表达式栈 int n = 0, pro = 1; while (i >= 0 && (midExp[i] >= ‘0‘ && midExp[i] <= ‘9‘)) { n = n + (midExp[i] - ‘0‘) * pro; --i; pro *= 10; } ++i; preExp.push(to_string(n)); } else if (midExp[i] == ‘+‘ || midExp[i] == ‘-‘ || midExp[i] == ‘*‘ || midExp[i] == ‘/‘) { // 运算符 loop: if (tmp.empty() || tmp.top() == ‘)‘) // 运算符栈为空或者栈顶为右括号直接入运算符栈 tmp.push(midExp[i]); else if (priority(midExp[i]) >= priority(tmp.top())) // 当前运算符优先级较高或相同直接入运算符栈 tmp.push(midExp[i]); else { // 否则运算符栈栈顶弹出压入到前缀表达式栈中，再将当前运算符与运算符栈栈顶运算符比较 preExp.push(string(1, tmp.top())); tmp.pop(); goto loop; } } else if (midExp[i] == ‘)‘) // 遇到右括号直接入运算符栈 tmp.push(midExp[i]); else if (midExp[i] == ‘(‘) { // 遇到左括号，依次弹出运算符栈栈顶，直至遇到右括号 while (tmp.top() != ‘)‘) { preExp.push(string(1, tmp.top())); tmp.pop(); } tmp.pop(); // 丢弃右括号 } } while (!tmp.empty()) { // 运算符栈中剩余运算符压入前缀表达式栈中 preExp.push(string(1, tmp.top())); tmp.pop(); } } int calcPreExp(stack<string>& preExp) { // 从右至左扫描表达式，遇到数字时，将数字压入堆栈，遇到运算符时，弹出栈顶的两个数，用运算符对它们做相应的计算（栈顶元素 op 次顶元素），并将结果入栈； // 重复上述过程直到表达式最左端，最后运算得出的值即为表达式的结果。 stack<int> tmp; while (!preExp.empty()) { if (preExp.top().size() > 1 || (preExp.top().size() == 1 && (preExp.top()[0] >= ‘0‘ && preExp.top()[0] <= ‘9‘))) { tmp.push(stoi(preExp.top())); preExp.pop(); } else { int i1 = tmp.top(); tmp.pop(); int i2 = tmp.top(); tmp.pop(); char op = preExp.top()[0]; preExp.pop(); if (op == ‘+‘) tmp.push(i1 + i2); if (op == ‘-‘) tmp.push(i1 - i2); if (op == ‘*‘) tmp.push(i1 * i2); if (op == ‘/‘) tmp.push(i1 / i2); } } return tmp.top(); } int priority(char op) { if (op == ‘+‘ || op == ‘-‘) return 1; if (op == ‘*‘ || op == ‘/‘) return 2; return -1; } };
（2）中缀表达式转后缀表达式再计算:
class Solution { public: int calculate(string s) { stack<string> postExp; // 去除表达式中的空格 int k = 0; for (int i = 0; i < s.size(); ++i) { if (s[i] != ‘ ‘) s[k++] = s[i]; } s.resize(k); // 中缀表达式转后缀表达式 midExpToPostExp(s, postExp); // 求解后缀表达式 stack<string> postExp2; while (!postExp.empty()) { postExp2.push(postExp.top()); postExp.pop(); } int res = calcPostExp(postExp2); return res; } private: void midExpToPostExp(const string& midExp, stack<string>& postExp) { stack<char> tmp; // 运算符栈 for (int i = 0; i < midExp.size(); ++i) { if (midExp[i] >= ‘0‘ && midExp[i] <= ‘9‘) { // 操作数直接入后缀表达式栈 int n = 0; while (i < midExp.size() && (midExp[i] >= ‘0‘ && midExp[i] <= ‘9‘)) { n = n * 10 + (midExp[i] - ‘0‘); ++i; } --i; postExp.push(to_string(n)); } else if (midExp[i] == ‘+‘ || midExp[i] == ‘-‘ || midExp[i] == ‘*‘ || midExp[i] == ‘/‘) { // 运算符 loop: if (tmp.empty() || tmp.top() == ‘(‘) // 运算符栈为空或者栈顶为左括号直接入运算符栈 tmp.push(midExp[i]); else if (priority(midExp[i]) > priority(tmp.top())) // 当前运算符优先级较高直接入运算符栈 tmp.push(midExp[i]); else { // 否则运算符栈栈顶弹出压入到前缀表达式栈中，再将当前运算符与运算符栈栈顶运算符比较 postExp.push(string(1, tmp.top())); tmp.pop(); goto loop; } } else if (midExp[i] == ‘(‘) // 遇到左括号直接入运算符栈 tmp.push(midExp[i]); else if (midExp[i] == ‘)‘) { // 遇到右括号，依次弹出运算符栈栈顶，直至遇到左括号 while (tmp.top() != ‘(‘) { postExp.push(string(1, tmp.top())); tmp.pop(); } tmp.pop(); // 丢弃左括号 } } while (!tmp.empty()) { // 运算符栈中剩余运算符压入后缀表达式栈中 postExp.push(string(1, tmp.top())); tmp.pop(); } } int calcPostExp(stack<string>& postExp) { // 从左至右扫描表达式，遇到数字时，将数字压入堆栈，遇到运算符时，弹出栈顶的两个数，用运算符对它们做相应的计算（次顶元素 op 栈顶元素），并将结果入栈； // 重复上述过程直到表达式最右端，最后运算得出的值即为表达式的结果。 stack<int> tmp; while (!postExp.empty()) { if (postExp.top().size() > 1 || (postExp.top().size() == 1 && (postExp.top()[0] >= ‘0‘ && postExp.top()[0] <= ‘9‘))) { tmp.push(stoi(postExp.top())); postExp.pop(); } else { int i1 = tmp.top(); tmp.pop(); int i2 = tmp.top(); tmp.pop(); char op = postExp.top()[0]; postExp.pop(); if (op == ‘+‘) tmp.push(i2 + i1); if (op == ‘-‘) tmp.push(i2 - i1); if (op == ‘*‘) tmp.push(i2 * i1); if (op == ‘/‘) tmp.push(i2 / i1); } } return tmp.top(); } int priority(char op) { if (op == ‘+‘ || op == ‘-‘) return 1; if (op == ‘*‘ || op == ‘/‘) return 2; return -1; } };
解法2：因为本题限定了运算符在+、-，因此没有运算符优先级的考虑，可以简化很多。
[LeetCode]72. Basic Calculator基本计算器
原文：http://www.cnblogs.com/aprilcheny/p/4955420.html