问题

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

解析

class Solution { public: //比较运算符的优先级 int compare(char top, char curr){ if (top == '+' || top == '-'){ if (curr == '*' || curr == '/' || curr == '(') return 1; //返回1表示当前元素进栈 else return 0; //返回0表示弹出栈顶元素 } else if (top == '*' || top == '/'){ if (curr == '(') return 1; else return 0; } else{ return 1; } } //将中缀表达式转换为后缀表达式 vector<string> changeToPostfix(string s) { vector<string> result; stack<char> operators; string number; for (int i = 0; i < s.size(); i++){ if (s[i] >= '0'&&s[i] <= '9'){ number += s[i]; } else{ if (number != ""){ result.push_back(number); number = ""; } if (s[i] == ' '){ continue; } if (s[i] != ')'){ while (!operators.empty() && !compare(operators.top(), s[i])){ result.push_back(string(1,operators.top())); operators.pop(); } operators.push(s[i]); } else{ while (operators.top() != '('){ result.push_back(string(1,operators.top())); operators.pop(); } operators.pop(); } } } if (number != ""){ result.push_back(number); } while (!operators.empty()){ result.push_back(string(1,operators.top())); operators.pop(); } return result; } //后缀表达式求值 int evalRPN(vector<string>& tokens) { stack<int>nums; for (int i = 0; i<tokens.size(); i++){ if (tokens[i] == "+" || tokens[i] == "-" || tokens[i] == "*" || tokens[i] == "/"){ int right = nums.top(); nums.pop(); int left = nums.top(); nums.pop(); if (tokens[i] == "+"){ nums.push(left + right); } else if (tokens[i] == "-"){ nums.push(left - right); } else if (tokens[i] == "*"){ nums.push(left*right); } else{ nums.push(left / right); } } else{ nums.push(stoi(tokens[i])); } } return nums.top(); } int calculate(string s) { vector<string> postfix=changeToPostfix(s); return evalRPN(postfix); } };