实现中缀后缀表达式以及基本的计算器功能
- 后缀表达式求值
逆波兰表达式求值
https://leetcode-cn.com/problems/evaluate-reverse-polish-notation/// 隐藏BUG,如果要用stoi或者atoi函数,必须要是有效数字才可以判断,否则输入“+”这种符号,会抛出异常 int evalRPN(vector<string>& tokens) { // int res; stack<int> st; // for (auto& token : tokens) { for (int i = 0; i < tokens.size(); i++) { // if (tokens[i] == "+" || tokens[i] == "-" || tokens[i] == "*" || tokens[i] == "/") { // int num1 = st.top(); // st.pop(); // int num2 = st.top(); // st.pop(); // if (tokens[i] == "+") st.push(num2 + num1); // if (tokens[i] == "-") st.push(num2 - num1); // if (tokens[i] == "*") st.push(num2 * num1); // if (tokens[i] == "/") st.push(num2 / num1); // } else { // st.push(stoi(tokens[i])); // } // } int temp1, temp2; string& token = tokens[i]; if (tokens[i] == "+") { temp1 = st.top(); st.pop(); temp2 = st.top(); st.pop(); st.push(temp1 + temp2); } else if (tokens[i] == "-") { temp1 = st.top(); st.pop(); temp2 = st.top(); st.pop(); st.push(temp2 - temp1); } else if (tokens[i] == "*") { temp1 = st.top(); st.pop(); temp2 = st.top(); st.pop(); st.push(temp2 * temp1); } else if (tokens[i] == "/") { temp1 = st.top(); st.pop(); temp2 = st.top(); st.pop(); st.push(temp2 / temp1); } else { st.push(std::stoi(tokens[i])); } } return st.top(); }
- 中缀表达式基础版
基本思想是将乘除的结果压入栈中,加减的话,直接带上符号压入栈中,最后计算所有加减的结果
面试题 16.26. 计算器
https://leetcode-cn.com/problems/calculator-lcci/class Solution { public: int calculate(string s) { char preSign = '+'; stack<int> st; for (int i = 0; i < s.size(); i++) { if (s[i] == ' ') { continue; } if (s[i] >= '0' && s[i] <= '9') { int num = 0; // while 的 意义 while (i < s.size() && s[i] >= '0' && s[i] <= '9') { num = num * 10 + (s[i] - '0'); // s[i] - '0'的计算需要加括号 i++; } i--; if (preSign == '*') { int temp = st.top(); st.pop(); st.push(num * temp); } if (preSign == '/') { int temp = st.top(); st.pop(); st.push(temp / num); } if (preSign == '+') { st.push(num); } if (preSign == '-') { st.push(-num); } } else { preSign = s[i]; } } int res = 0; // for (int i = 0; i < st.size(); i++) { // res += st.top(); // st.pop(); // 隐藏的BUG,醉了,pop之后会导致边界core dump // } while (!st.empty()) { res += st.top(); st.pop(); } return res; } };