题解 | #表达式求值#
表达式求值
http://www.nowcoder.com/practice/c215ba61c8b1443b996351df929dc4d4
#
# 返回表达式的值
# @param s string字符串 待计算的表达式
# @return int整型
#
class Solution:
def solve(self , s: str) -> int:
# 对符号和数字进行分离
arr = []
for i in s:
if len(arr) >= 1 and arr[-1][0] in "0123456789" and '0' <= i <= '9':
temp = arr.pop()
arr.append(temp+i)
else:
arr.append(i)
# 维持两个栈,一个保存符号,一个保存数字
stack1,stack2 = [],[]
i = 0
while i < len(arr):
# 左括号直接入符号栈( 3 + ( 33 * 2 + 3 ) ) - 2 / 1 * 2
if arr[i] == '(':
stack1.append(arr[i])
# 遇到运算符
elif arr[i] in ['+','-','*','/']:
if not stack1:
stack1.append(arr[i])
else:
temp = stack1[-1]
# 若没有大于或等于的符号,则加入
if temp not in ['+','-','*','/']:
stack1.append(arr[i])
# 若有,则判断优先级大小
else:
# 乘除计算
if temp in ['*','/']:
b = stack2.pop()
a = stack2.pop()
temp = stack1.pop()
stack1.append(arr[i])
if temp == '*': stack2.append(int(a)*int(b))
else: stack2.append(int(a)/int(b))
# 加减
if temp in ['+','-']:
if arr[i] in ['*','/']:
stack1.append(arr[i])
else:
b = stack2.pop()
a = stack2.pop()
temp = stack1.pop()
stack1.append(arr[i])
if temp == '+': stack2.append(int(a) + int(b))
else: stack2.append(int(a) - int(b))
# 右括号
elif arr[i] == ')':
# stack1弹出到(为止
while True :
op = stack1.pop()
if op == '(': break
else:
b = stack2.pop()
a = stack2.pop()
# 加减乘除
if op == '+':
stack2.append(int(a) + int(b))
elif op == '-':
stack2.append(int(a) - int(b))
elif op == '*':
stack2.append(int(a) * int(b))
else:
stack2.append(int(a) / int(b))
# 数字
else:
stack2.append(int(arr[i]))
i += 1
# 判断stack1是否还有元素
while stack1:
op = stack1.pop()
b = stack2.pop()
a = stack2.pop()
# 加减乘除
if op == '+':
stack2.append(int(a) + int(b))
elif op == '-':
stack2.append(int(a) - int(b))
elif op == '*':
stack2.append(int(a) * int(b))
else:
stack2.append(int(a) / int(b))
return stack2.pop()