实现一个基本计算器来计算一个简单的字符串表达式s。示例1：输入：s="1+1"输出：2示例2：输入：s="2-1+2"输出：3示例3：输入：s="(1+(4+5+2)-3)+(6+8)"输出：23提示：1.1<=s.length<=3*1052.s由数字、'+'、'-'、'('、')'、而''Form3.s表示题目中给出了有效的表达，难度较难。刚考完，第一感觉还是挺简单的。只有加减法，所以括号没用。提前告诉你，括号没用这句话是错误的。一开始我的想法是先去掉空格和括号，然后创建两个栈，一个存数字，一个存符号，然后线性循环字符串表达式响应Computation。这里推荐邓军华老师的数据结构与算法课程（https://www.bilibili.com/video...写完一个版本，信心满满的提交的时候，遇到了一个省略括号的String表达式：-（3+(4+5)).原来我分析问题一开始就错了。然后，正片开始。首先，字符串表达式中的空格是一个无效字符，可以去掉。创建两个栈，一个存放数字，一个存放符号。并且在字符串表达式的末尾，要加一个终止符，这个终止符可以是表达式中可能出现的任何字符，这里选择$符号。符号栈中也加入一个$符号代表终止符s=s.replace('','')+'$'数栈,symbolstack=[0],['$']加一numberstack0，一是不影响+和-的运算结果，二是防止表达式中的第一个数为负数。（血淋淋的经验，邪恶的leetcode可以解决各种问题）在字符串表达式中，相加和相减的两个数不一定只有个位数，但我们一次只能读取一个字符，所以我们需要存储上一个读取的字符，如果上一个读取的字符是数字，则将数字栈的最后一位出栈，乘以10加到当前数字上。所以我们需要创建一个变量。如何进行最后一个字符=''的操作？判断符号栈中是否有元素，存在则执行循环。Whynot只循环一次字符串表达式，这个可以在最后说。在循环中，如果当前字符是数字，那么必须判断，如果读取的前一个字符是数字，那么数字栈中的最后一个字符一定是pop,乘以10并加上当前数字。否则，直接将其添加到数字堆栈中。然后向前读取字符索引一位。对了，涉及到字符串表达式的索引，需要提前创建一个变量来存放当前索引。ifs[s_index].isnumeric():#是否只包含数字iflastcharacter.isnumeric():#最后一个字符是数字，合并数字stack.append(numberstack.pop()*10+int(value))else:Numberstack.append(int(value))s_index+=1在循环中，如果当前字符是符号，问题就复杂多了。什么时候计算加减法，用括号做什么。设置优先级是正确的解决方案。---+-()$|>|>|<|>|>|>|>|<|>|>(|<|<|<|=|)|||||$|<|<|<||=如果当前字符是符号，则判断符号栈中最后一位与当前字符的优先级关系。如果当前字符具有高优先级，即<.符号栈的最后一位计算不出来，将当前符号加入符号栈。如果当前字符的优先级与符号栈中最后一个符号的优先级相同，那么在优先级表中，只有$和$本身以及(和)具有相同的优先级。$遇到自己表示结束，(和)之间的相遇表示一对括号之间只有一个数字，没有符号。这时候括号就没用了。那么此时的操作就是弹出符号栈的最后一位。执行完以上两个分支后，需要将字符索引前移一位。如果当前字符的优先级较低，即>，则表示可以计算栈中的符号。首先弹出符号栈的最后一位，弹出数栈的最后两位。注意在数栈中，第一个出栈的数应该在计算中的符号之前。然后在计算后将结果添加到数字堆栈中。这里不需要将字符索引前移，因为符号栈中可能有多个字符优先级高于当前字符。循环结束后，数栈中可能有两个元素，第一个就是最开始加入的0，除非特殊情况，否则不会用到这个元素0。在任何情况下，数字堆栈的最后一位是expression.class的结果解决方案：defcalculate(self,s:str)->int:s=s.replace('','')+'$'数字栈，符号栈，最后一个字符，s_index=[0],['$'],'',0符号优先级表={"+":{"+":'>','-':'>','(':'<',')':'>','$':'>'},"-":{"+":'>','-':'>','(':'<',')':'>','$':'>'},"(":{"+":'<','-':'<','(':'<',')':'=','$':''},")":{"+":'','-':'','(':'',')':'','$':''},"$":{"+":'<','-':'<','(':'<',')':'','$':'='}}whilelen(symbolstack)>=1:value=s[s_index]ifs[s_index].isnumeric():#是否只包含数字iflastcharacter.isnumeric():#最后一个字符是数字，应该合并数字栈.append(numberstack.pop()*10+int(value))else:numberstack.append(int(value))s_index+=1else:ifsymbolprioritytable[symbolstack[-1]][value]=='<':#中的值堆栈比当前低，当前符号被压入堆栈Symbolstack.append(value)s_index+=1elifSymbolprioritytable[symbolstack[-1]][value]=='=':#括号闭合，或者结束符号stack.pop()s_index+=1elifSymbolprioritytable[symbolstack[-1]][value]=='>':#栈中优先级高，可以计算符号，数A，数B=symbolstack.pop()，数stack。pop(),numberstack.pop()numberstack.append((numberB-numberA)ifsymbol=='-'else(numberB+numberA))previouscharacter=value返回数字stack.pop()公众号：《python杂货铺》，聚焦python语言及相关知识发现更多原创文章，期待您的关注。
