题目:
实现一个基本的计算器来计算一个简单的字符串表达式的值。
字符串表达式仅包含非负整数，+， - ，*，/ 四种运算符和空格 。 整数除法仅保留整数部分。
示例 1:
输入: "3+2*2"
输出: 7
示例 2:
输入: " 3/2 "
输出: 1
示例 3:
输入: " 3+5 / 2 "
输出: 5
说明：
你可以假设所给定的表达式都是有效的。
请不要使用内置的库函数 eval
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/basic-calculator-ii
解题思路:
任何算法题,我们都可以假设最简单的情况入手,写一个简单的框架出来,再逐步拓展复杂的情况,逐渐完善自己的算法
1.只考虑加减法情况,并且没有括号,如s = “1+123”
设变量num=0,存放当前数字,给它初始化为0, 这里它的变化过程是 0 1 123
变量sign=‘+’,存放当前符号,并给他初始化为‘+’,这里它的变化过程是 ‘+’ ‘+’
变量stack=[]来存放结果,并初始化为空列表
2.遍历s,当碰到不同的情况将它的值放到上述不同的容器里
这里num有个难点,比如字符串‘123’遍历是是1->2->3这样进来的,怎么将它变成整型123?
如果只用int转换,如果是一个巨大的数字,立马就内存溢出了,所以要循环遍历 比如先进来1
num = 0
num = 10*num+new num
10*0 +1 = 1
10*1+2 = 12
10*12+3 = 123
3.数字的结果num 和运算符stack 计算完成后 添加到stack,最后只需要计算stack中的和就好了
if sign =='+':
stack.append(num)
elif sign =='-':
stack.append(-num)
4.补充
运算符乘法: 乘法等于上一个的值乘以下一个的值,所以取stack[-1]*num
运算符出发: 乘法等于上一个的值整除(这道题不考虑小数)下一个的值,所以取stack[-1] //num
括号:
因为括号具有递归性质。我们拿字符串3*(4-5/2)-6举例：
calculate(3*(4-5/2)-6)
= 3 * calculate(4-5/2) - 6
= 3 * 2 - 6
= 0
可以脑补一下，无论多少层括号嵌套，通过 calculate 函数递归调用自己，都可以将括号中的算式化简成一个数字。换句话说，括号包含的算式，我们直接视为一个数字就行了。
现在的问题是，递归的开始条件和结束条件是什么？遇到(开始递归，遇到)结束递归
完整的代码:
def calculate(s:str) ->int:
def helper(s: List) ->int:
stack = []
sign ='+'
num =0
while len(s) >0:
c = s.pop(0)
if c.isdigit():
num =10 * num +int(c)
if (not c.isdigit()and c !=' ')or len(s) ==0:
if sign =='+':
stack.append(num)
elif sign =='-':
stack.append(-num)
elif sign =='*':
stack[-1] = stack[-1] * num
elif sign =='/':
# python 除法向 0 取整的写法
stack[-1] =int(stack[-1] /float(num))
num =0
sign = c
return sum(stack)
# 需要把字符串转成列表方便操作
return helper(list(s))
