运用栈写表达式计算代码
时间: 2023-08-06 07:22:55 浏览: 86
好的,以下是一个基于栈的表达式计算代码(假设输入的表达式合法):
```python
def calculate(expression):
# 定义操作符和数字的栈
operator_stack = []
number_stack = []
# 定义操作符优先级
priority = {'+': 1, '-': 1, '*': 2, '/': 2}
# 遍历表达式中的每个字符
for c in expression:
if c.isdigit():
# 如果是数字则直接压入数字栈
number_stack.append(int(c))
elif c in priority:
# 如果是操作符
while operator_stack and priority[operator_stack[-1]] >= priority[c]:
# 如果操作符栈不为空并且栈顶操作符的优先级大于等于当前操作符的优先级
# 则将栈顶操作符弹出并进行计算
operator = operator_stack.pop()
num2 = number_stack.pop()
num1 = number_stack.pop()
if operator == '+':
number_stack.append(num1 + num2)
elif operator == '-':
number_stack.append(num1 - num2)
elif operator == '*':
number_stack.append(num1 * num2)
elif operator == '/':
number_stack.append(num1 // num2)
# 将当前操作符压入操作符栈
operator_stack.append(c)
elif c == '(':
# 如果是左括号,则直接压入操作符栈
operator_stack.append(c)
elif c == ')':
# 如果是右括号,则弹出操作符栈中的操作符并进行计算,直到遇到左括号
while operator_stack[-1] != '(':
operator = operator_stack.pop()
num2 = number_stack.pop()
num1 = number_stack.pop()
if operator == '+':
number_stack.append(num1 + num2)
elif operator == '-':
number_stack.append(num1 - num2)
elif operator == '*':
number_stack.append(num1 * num2)
elif operator == '/':
number_stack.append(num1 // num2)
operator_stack.pop() # 弹出左括号
# 处理剩余的操作符
while operator_stack:
operator = operator_stack.pop()
num2 = number_stack.pop()
num1 = number_stack.pop()
if operator == '+':
number_stack.append(num1 + num2)
elif operator == '-':
number_stack.append(num1 - num2)
elif operator == '*':
number_stack.append(num1 * num2)
elif operator == '/':
number_stack.append(num1 // num2)
return number_stack.pop()
```
这个代码使用了两个栈,一个是操作符栈,一个是数字栈。遍历表达式中的每个字符,如果是数字则直接压入数字栈,如果是操作符则判断操作符的优先级和操作符栈顶操作符的优先级进行比较,如果栈顶操作符的优先级大于等于当前操作符的优先级,则弹出栈顶操作符并进行计算,然后将当前操作符压入操作符栈;如果是左括号,则直接压入操作符栈;如果是右括号,则弹出操作符栈中的操作符并进行计算,直到遇到左括号。最后,处理剩余的操作符,直到操作符栈为空,最后数字栈中剩余的数字即为表达式的计算结果。