实现一个基本的计算器来计算一个简单的字符串表达式的值。
字符串表达式仅包含非负整数,+, - ,*,/ 四种运算符和空格 。 整数除法仅保留整数部分。
示例 1:
输入: "3+2*2"
输出: 7
示例 2:
输入: " 3/2 "
输出: 1
示例 3:
输入: " 3+5 / 2 "
输出: 5
说明:
你可以假设所给定的表达式都是有效的。
请不要使用内置的库函数 eval。
通过次数28,612提交次数74,932
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/basic-calculator-ii
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
from typing import List
class Solution:
def calculate(self, s: str) -> int:
# 将中缀表达式转换为后缀表达式
# 遵循以下步骤:
# (1) 初始化两个栈:运算符栈stack和储存中间结果的栈ls;
# (2) 从左至右扫描中缀表达式;
# (3) 遇到操作数时,将其压入ls;
# (4) 遇到运算符时,比较其与stack栈顶运算符的优先级:
# (4-1) 如果stack为空,则直接将此运算符入栈;
# (4-2) 否则,若优先级比栈顶运算符的高,也将运算符压入stack(注意转换为前缀表达式时是优先级较高或相同,而这里则不包括相同的情况);
# (4-3) 否则,将stack栈顶的运算符弹出并压入到ls中,再次转到(4-1)与stack中新的栈顶运算符相比较;
# (5) 重复步骤(2)至(4),直到表达式的最右边;
# (7) 将stack中剩余的运算符依次弹出并压入ls;
# (8) 依次弹出ls
# 中的元素并输出,结果的逆序即为中缀表达式对应的后缀表达式(转换为前缀表达式时不用逆序)。
ls=[]
stack=[]
def priority(s:str)->int:
if s in ['+','-']:
return 1
if s in ['*','/']:
return 2
num=0
for i ,x in enumerate(s):
if x.isdigit():
num=num*10+int(x)
if x==' ' and i!=len(s)-1:
continue
if x in['+','-','*','/']:
ls.append(num)#将数字加入ls
num=0
if not stack:
stack.append(x)
elif priority(x)>priority(stack[-1]):
stack.append(x)
else:
while( stack and priority(stack[-1])>=priority(x)):
ls.append(stack.pop())
stack.append(x)
if i==len(s)-1 and (s[i].isdigit() or s[i]==' '):
ls.append(num)
while stack:
ls.append(stack.pop())
#计算
#t=0
for x in ls:
if x not in ['+','-','*','/']:
stack.append(x)
else:
a=stack.pop()
b=stack.pop()
if x=='+':stack.append(a+b)
if x=='-':stack.append(b-a)
if x=='*':stack.append(a*b)
if x=='/':stack.append(int(b/a))
return stack[0]