栈实现四则远算
总结
四则运算表达式求值分两步:
中缀转后缀,栈中存符号
后缀算结果,栈中存数字
中缀表达式与后缀表达式转换
中缀表达式1+(2-3)*4+5/6
后缀表达式1,2,+
通过栈进行转换
当前字符串 | 后缀表达式 | 栈 |
---|---|---|
1+(2-3)*4+5/6 | ||
+(2-3)*4+5/6 | 1 | |
(2-3)*4+5/6 | 1 | + |
2-3)*4+5/6 | 1 | +( |
-3)*4+5/6 | 12 | +( |
3)*4+5/6 | 12 | +(- |
)*4+5/6 | 123 | +(- |
*4+5/6 | 123- | + |
4+5/6 | 123- | +* |
+5/6 | 123-4 | +* |
5/6 | 123-4*+ | + |
/6 | 123-4*+5 | + |
6 | 123-4*+5 | +/ |
123-4*+56 | +/ | |
123-4*+56/+ |
后缀表达式的计算
数字进栈,符号远算
[1,[[[2,3,-],4,*],[5,6,/],+],+]
2-3=-1
-1*4=-4
5/6=0.833
-4+0.833=-3.167
1+(-3.167)=-2.167
python实现
def calculator(s: str) -> float:
s = s.replace(" ", "")
s_list = []
for c in list(s):
if c.isdigit():
if len(s_list) == 0 or isinstance(s_list[-1], str):
s_list.append(int(c))
else:
s_list[-1] *= 10+int(c)
else:
s_list.append(c)
# 中缀转后缀
stack = []
s_end = []
for c in s_list:
if isinstance(c, int):
s_end.append(c)
elif c == "(":
stack.append(c)
elif c == ")":
while stack[-1] != "(":
s_end.append(stack.pop())
stack.pop()
elif c in ["*", "/"]:
while len(stack) != 0 and stack[-1] in ["*", "/"]:
s_end.append(stack.pop())
stack.append(c)
elif c in ["+", "-"]:
while len(stack) != 0 and stack[-1] in ["+", "-", "*", "/"]:
s_end.append(stack.pop())
stack.append(c)
else:
continue
while stack:
s_end.append(stack.pop())
print(s_end)
# 计算后缀表达式
stack = []
for c in s_end:
if isinstance(c, int):
stack.append(c)
elif c == "+":
stack[-2] += stack[-1]
stack.pop()
elif c == "-":
stack[-2] -= stack[-1]
stack.pop()
elif c == "*":
stack[-2] *= stack[-1]
stack.pop()
elif c == "/":
stack[-2] /= stack[-1]
stack.pop()
else:
continue
return stack[0]
if __name__ == "__main__":
print(calculator("1+(2-3)*4+5/6"))