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 st;int num=0;char sign='+';//记录num前的符号，默认为'+'for(;i