基本计算器 II

实现一个基本的计算器来计算一个简单的字符串表达式的值。
字符串表达式仅包含非负整数，+， - ，*，/ 四种运算符和空格 。 整数除法仅保留整数部分。

示例 1:
输入: “3+2*2”
输出: 7

示例 2:
输入: " 3/2 "
输出: 1

示例 3:
输入: " 3+5 / 2 "
输出: 5

说明：
你可以假设所给定的表达式都是有效的。
请不要使用内置的库函数 eval。

---

思路：

1. 首先记录每个运算符的位置，每个运算符后面跟一个非负整数，假设第一个元素的前面是“+”号。

2. 遍历运算符，假设其后面跟着元素n，判断运算符
   （1）若为“+”，则将n压入栈。
   （2）若为“-”，则将-n压入栈。
   （3）若为“”，则从栈中取出前一个元素m，并将mn压入栈中。
   （4）若为“/”，则从栈中取出前一个元素m，并将m/n压入栈中。

3. 我们现在需要计算运算符后面的元素n了。
   (1)由于元素n在两个运算符之间，所以假设当前运算符在整个字符串 s 中的位置p1（运算符位置在第1步已经计算）,下一个运算符位置p2，则代表数字的字符串为
   $\qquad\qquad$tmp_s=s.substr(p1+1,p2-p1+1)
   substr(i,j)指的是从第i个位置，往后取j个字符。
   (2)此时tmp_s为字符串，我们还需要将其转为数字，
   $\qquad\qquad\qquad$n=stoi(tmp_s)

4. 对于栈中的元素求和，即为表达式的值。

代码：

class Solution {
public:int calculate(string s) {stack<int> res;     //每个符号运算后的结果，最终按元素求和即可//保存运算符的位置s='+'+s;           //方便编码，前面补充'+'号vector<int> pos; for(int i=0;i<s.length();i=i+1){if(s[i]=='+' || s[i]=='-' || s[i]=='*' || s[i]=='/'){pos.push_back(i);}}pos.push_back(s.length());//针对每个运算符，挑选出运算数字int p1=0,p2=0;                     //用于指示每个数字前后运算符的位置   for(int i=0;i<pos.size()-1;i++){p1=pos[i];p2=pos[i+1];string tmp_s=s.substr(p1+1,p2-p1-1);  //选出该数字的字符串int tmp_int=stoi(tmp_s);      //将字符串转为整型if(s[p1]=='+')                //判断该数字前的运算符{res.push(tmp_int);}else if(s[p1]=='-'){res.push(-tmp_int);}else if(s[p1]=='*'){int tmp=res.top();res.pop();res.push(tmp*tmp_int);}else if(s[p1]=='/'){int tmp=res.top();res.pop();res.push(tmp/tmp_int);  //此处为前面的数字除以当前数，不要搞反了}}//计算最后结果int sum=0;while(!res.empty()){sum+=res.top();res.pop();}return sum;}
};

结果：