class Solution:
def calculate(self, s): # 中缀转后缀
def evalRPN(RPN):
stack = []
for i in range(len(RPN)):
if RPN[i].isnumeric() or RPN[i][0]=="-" and RPN[i][1:].isnumeric():
stack.append(RPN[i])
else:
x = int(stack.pop())
y = int(stack.pop())
if RPN[i] == "-":
stack.append(y-x)
elif RPN[i] == "+":
stack.append(y+x)
elif RPN[i] == "*":
stack.append(y*x)
elif RPN[i] == "/":
stack.append(y/x)
return int(stack[-1])
op_priority = {'+': 0, '-': 0, '*': 1, '/': 1, '%': 1, '^': 2} # 定义操作符优先级
if s[0] == "-": s="0"+s # 第一个数字是负数
s = "(" + s.replace(" ", "").replace("(-", "(0-").replace("--","+").replace("+-","-") + ")" # 注：不能解决*-和/-
n = len(s)
op_stack = [] # 符号操作栈
RPN = [] # 后缀表达式
i = 0
while i < n:
c = s[i] # 当前字符
i += 1 # 下一个字符
if c.isdigit():
num = int(c) # 当前字符
while i < n and s[i].isdigit(): # 下一个字符
num = num * 10 + int(s[i])
i += 1
RPN.append(str(num))
elif c == '(': # (
op_stack.append(c)
elif c == ')': # calculate until see '('
while op_stack and op_stack[-1] != '(':
RPN.append(op_stack.pop())
op_stack.pop()
else:
while op_stack and op_stack[-1] != '(':
if op_priority[c] <= op_priority[op_stack[-1]]:
RPN.append(op_stack.pop())
else:
break
op_stack.append(c)
return evalRPN(RPN)
print(Solution().calculate("3+2*2"))
@TOC
# 同上，注释掉最后一行print()
class Solution:
def calculate(self, s): # 中缀转后缀
def evalRPN(RPN):
stack = []
for i in range(len(RPN)):
if RPN[i].isnumeric() or RPN[i][0]=="-" and RPN[i][1:].isnumeric():
stack.append(RPN[i])
else:
x = int(stack.pop())
y = int(stack.pop())
if RPN[i] == "-":
stack.append(y-x)
elif RPN[i] == "+":
stack.append(y+x)
elif RPN[i] == "*":
stack.append(y*x)
elif RPN[i] == "/":
stack.append(y/x)
return int(stack[-1])
op_priority = {'+': 0, '-': 0, '*': 1, '/': 1, '%': 1, '^': 2} # 定义操作符优先级
if s[0] == "-": s="0"+s # 第一个数字是负数
s = "(" + s.replace(" ", "").replace("(-", "(0-").replace("--","+").replace("+-","-") + ")" # 注：不能解决*-和/-
n = len(s)
op_stack = [] # 符号操作栈
RPN = [] # 后缀表达式
i = 0
while i < n:
c = s[i] # 当前字符
i += 1 # 下一个字符
if c.isdigit():
num = int(c) # 当前字符
while i < n and s[i].isdigit(): # 下一个字符
num = num * 10 + int(s[i])
i += 1
RPN.append(str(num))
elif c == '(': # (
op_stack.append(c)
elif c == ')': # calculate until see '('
while op_stack and op_stack[-1] != '(':
RPN.append(op_stack.pop())
op_stack.pop()
else:
while op_stack and op_stack[-1] != '(':
if op_priority[c] <= op_priority[op_stack[-1]]:
RPN.append(op_stack.pop())
else:
break
op_stack.append(c)
return evalRPN(RPN)
#print(Solution().calculate("3+2*2"))
leetcode227
class Solution:
def calculate(self, s): # 中缀转后缀
def evalRPN(RPN):
stack = []
for i in range(len(RPN)):
if RPN[i].isnumeric() or RPN[i][0]=="-" and RPN[i][1:].isnumeric():
stack.append(RPN[i])
else:
x = int(stack.pop())
y = int(stack.pop())
if RPN[i] == "-":
stack.append(y-x)
elif RPN[i] == "+":
stack.append(y+x)
elif RPN[i] == "*":
stack.append(y*x)
elif RPN[i] == "/":
stack.append(y/x)
return int(stack[-1])
op_priority = {'+': 0, '-': 0, '*': 1, '/': 1, '%': 1, '^': 2} # 定义操作符优先级
if s[0] == "-": s="0"+s # 第一个数字是负数
# s = "(" + s.replace(" ", "").replace("(-", "(0-").replace("--","+").replace("+-","-") + ")" # 注：不能解决*-和/-
s = s.replace(" ", "").replace("--","+").replace("+-","-")
n = len(s)
op_stack = [] # 符号操作栈
RPN = [] # 后缀表达式
i = 0
while i < n:
c = s[i] # 当前字符
i += 1 # 下一个字符
if c.isdigit():
num = int(c) # 当前字符
while i < n and s[i].isdigit(): # 下一个字符
num = num * 10 + int(s[i])
i += 1
RPN.append(str(num))
# elif c == '(': # (
# op_stack.append(c)
# elif c == ')': # calculate until see '('
# while op_stack and op_stack[-1] != '(':
# RPN.append(op_stack.pop())
# op_stack.pop()
else:
while op_stack:
if op_priority[c] <= op_priority[op_stack[-1]]:
RPN.append(op_stack.pop())
else:
break
op_stack.append(c)
while op_stack:
RPN.append(op_stack.pop())
return evalRPN(RPN)
