224. 基本计算器

224. 基本计算器

给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。

注意:不允许使用任何将字符串作为数学表达式计算的内置函数，比如 eval() 。

示例 1：

输入：s = "1 + 1"

输出：2

示例 2：

输入：s = " 2-1 + 2 "

输出：3

示例 3：

输入：s = "(1+(4+5+2)-3)+(6+8)"

输出：23

提示：

• 1 <= s.length <= 3 * 105

• s 由数字、'+'、'-'、'('、')'、和 ' ' 组成

• s 表示一个有效的表达式

• '+' 不能用作一元运算(例如， "+1" 和 "+(2 + 3)" 无效)

• '-' 可以用作一元运算(即 "-1" 和 "-(2 + 3)" 是有效的)

• 输入中不存在两个连续的操作符

• 每个数字和运行的计算将适合于一个有符号的 32位 整数

如何实现一个计算器 :: labuladong的算法小抄 (gitee.io)

思路：栈

当i遇到运算符时，将前一个num和sign入栈，然后再更新sign为当前运算符，num为0。

这里还额外实现了'*'、'/'，为了做到先乘除后加减：

'+'、'-' 运算符只能给栈内push值，而'*'、'/' 运算符可以从栈内pop出被乘数或被除数，再将乘除运算后的结果push入栈内。

class Solution {
public:int calculate(string s){int index=0;return deal(s,index);}int deal(string& s,int& i) //注意：传入i的引用{stack<int> st;int num=0;char sign='+';//记录num前的符号，默认为'+'for(;i<s.size();i++){char c=s[i];if(c=='(')//遇到左括号，开始递归，求(...)算出的值{num=deal(s,++i);//因为传入的是i的引用，所以递归调用结束后，i此时就是与该'('对应的')'的下标}if(isdigit(c)){num=num*10+(c-'0');}if((!isdigit(c)&&c!=' ')||i==s.size()-1)//遇到运算符或者来到字符串末尾，将前一个num和sign入栈(跳过' '){int temp=0;switch(sign)//前一个num的符号{case '+':st.push(num);break;case '-':st.push(-num);break;case '*':temp=st.top();st.pop();st.push(temp*num);break;case '/':temp=st.top();st.pop();st.push(temp/num);break;}sign=c;//更新当前num的符号num=0;//更新num的值}if(c==')')//遇到右括号，结束递归break;}int res=0;while(!st.empty())//栈内所有的元素之和即为表达式之值{res+=st.top();st.pop();}return res;}
};