用栈实现表达式求值代码
时间: 2023-10-26 19:13:13 浏览: 67
以下是使用栈实现表达式求值的示例代码:
```python
def evaluate_expression(expression):
# 创建两个栈,分别存储数字和操作符
number_stack = []
operator_stack = []
# 定义操作符的优先级
priority = {'+': 1, '-': 1, '*': 2, '/': 2}
# 去除表达式中的空格
expression = expression.replace(' ', '')
# 遍历表达式中的每个字符
index = 0
while index < len(expression):
char = expression[index]
# 如果当前字符是数字,则将其转换为整数并入栈
if char.isdigit():
number = int(char)
index += 1
while index < len(expression) and expression[index].isdigit():
number = number * 10 + int(expression[index])
index += 1
number_stack.append(number)
# 如果当前字符是操作符,则将其入栈,并比较其与栈顶操作符的优先级
elif char in priority:
while operator_stack and priority[char] <= priority[operator_stack[-1]]:
op = operator_stack.pop()
right = number_stack.pop()
left = number_stack.pop()
result = evaluate_operation(left, right, op)
number_stack.append(result)
operator_stack.append(char)
index += 1
else:
index += 1
# 将栈中剩余的操作符依次出栈并计算结果
while operator_stack:
op = operator_stack.pop()
right = number_stack.pop()
left = number_stack.pop()
result = evaluate_operation(left, right, op)
number_stack.append(result)
# 返回最终结果
return number_stack.pop()
def evaluate_operation(left, right, operator):
# 根据操作符计算两个数字的结果
if operator == '+':
return left + right
elif operator == '-':
return left - right
elif operator == '*':
return left * right
elif operator == '/':
return int(left / right)
```
这段代码首先创建了两个栈,一个用于存储数字,一个用于存储操作符。然后遍历表达式中的每个字符,如果是数字则入数字栈,如果是操作符则入操作符栈,并且比较其与栈顶操作符的优先级。如果当前操作符的优先级小于等于栈顶操作符的优先级,则将栈顶操作符出栈并计算其与栈顶两个数字的结果,并将结果入数字栈。最后将栈中剩余的操作符依次出栈并计算结果,最终返回数字栈中的唯一元素作为表达式的计算结果。