leetcode-224-Basic Calculator

问题

题目：[leetcode-224]

思路

注意连续数字的情形。 注意只有操作数的情形。

问题：中缀表达式计算 分析：这个前面做过，有几个关键问题。怎么识别元素的问题。还有优先级一定不能变。 先乘除后加减，同类运算符先进栈的优先级高 输入：中缀表达式（字符串），没有空格 处理： 1.读取表达式 2.循环：遍历表达式中每一个字符 2.1.如果是opnd，保存临时结果。 2.2.如果是optr 2.2.1.临时结果的操作数入opnd栈。 2.2.2.判断 当前优先级 和 栈顶优先级关系 2.2.2.1.大于，入栈 2.2.2.2.循环：栈顶优先级 < 当前优先级 2.2.2.2.1.从optr中弹出optr 2.2.2.2.2.从opnd栈中弹出两个操作数 2.2.2.2.3.计算，将中间结果入栈 2.2.2.3.入栈（因为当前操作符早晚是要入栈的） 3.将最后一个操作数入栈 4.循环：optr栈不空 4.1.从optr栈中弹出元素 4.2.判断是不是# 4.2.1.是，跳出 4.2.2.不是，从opnd栈中弹出两个元素进行计算，中间结果入栈。 5.将opnd栈中结果输出即为最终元素 输出：结果

代码

class Solution { public: int calculate(string s) { stack<int> opnd; // 操作数 stack<char> optr; // 操作符 int sz = s.size(); if(1==sz) return string_to_int(s); bool flag = true; std::string val; // 暂存操作数，为了避免大于1位的数字 for(int i = 0; i < sz; ++i){ if(isspace(s[i])) continue; else if( isdigit(s[i]) ) val += s[i]; else{ if(val != ""){ opnd.push(string_to_int(val)); val = ""; } if(optr.empty()) optr.push(s[i]); // 栈空 else if( s[i] == '(' ) optr.push(s[i]); // 左括号 else if( s[i] == ')'){ // 右括号 while(!optr.empty()){ char top = optr.top(); optr.pop(); if(top == '(') break; int right = opnd.top(); opnd.pop(); int left = opnd.top(); opnd.pop(); int tmp = cal(left, right, top); opnd.push(tmp); } } else{ // 其他操作符 while(!optr.empty()){ char top = optr.top(); int top_prior = get_prior(top); int cur_prior = get_prior(s[i]); if(cur_prior > top_prior) break; else{ int right = opnd.top(); opnd.pop(); int left = opnd.top(); opnd.pop(); int tmp = cal(left, right, top); opnd.push(tmp); optr.pop(); } } optr.push(s[i]); // 当前操作符入栈 } } } if(val != "") opnd.push(string_to_int(val)); // 为了避免只有操作数没有操作符的情形 while(!optr.empty()){ int top = optr.top(); optr.pop(); int right = opnd.top(); opnd.pop(); int left = opnd.top(); opnd.pop(); int tmp = cal( left, right, top ); opnd.push(tmp); } return opnd.top(); } private: int cal(int left, int right, char op){ int ans = 0; switch(op){ case '+' : ans = left + right;break; case '-' : ans = left - right;break; case '*' : ans = left * right;break; case '/' : ans = left / right;break; default : break; } return ans; } int get_prior(char op){ if( op == '+' || op == '-' ) return 1; else if( op == '*' || op =='/' ) return 2; else return -1; } int string_to_int(std::string& s){ std::stringstream ss; ss << s; int val; ss >> val; return val; } };