使用栈结构实现表达式求值
时间: 2024-05-13 07:19:25 浏览: 15
表达式求值可以通过使用栈来实现。具体步骤如下:
1. 创建两个栈,一个用于存储操作数(Operand Stack),一个用于存储运算符(Operator Stack)。
2. 从左到右遍历表达式中的每个元素,若为数字,则直接入操作数栈中;若为运算符,则与运算符栈的栈顶元素进行比较。
3. 如果运算符栈为空,则将该运算符入栈。
4. 如果该运算符的优先级高于运算符栈栈顶元素的优先级,则将该运算符入栈。
5. 如果该运算符的优先级低于或等于运算符栈栈顶元素的优先级,则从操作数栈中取出两个操作数,从运算符栈中取出一个运算符,进行运算,并将结果入操作数栈中。重复此步骤直到该运算符可以入栈。
6. 当表达式遍历完成后,若运算符栈不为空,则从操作数栈中取出两个操作数,从运算符栈中取出一个运算符,进行运算,并将结果入操作数栈中。重复此步骤直到运算符栈为空。
7. 最后操作数栈中的唯一元素即为表达式的最终计算结果。
下面是一个使用栈结构实现表达式求值的 Python 代码实现:
```
def evaluate_expression(expression):
operator_stack = []
operand_stack = []
precedence = {'+': 1, '-': 1, '*': 2, '/': 2}
for token in expression:
if token.isdigit():
operand_stack.append(int(token))
else:
while operator_stack and precedence[token] <= precedence.get(operator_stack[-1], 0):
operator = operator_stack.pop()
operand2 = operand_stack.pop()
operand1 = operand_stack.pop()
result = perform_operation(operand1, operand2, operator)
operand_stack.append(result)
operator_stack.append(token)
while operator_stack:
operator = operator_stack.pop()
operand2 = operand_stack.pop()
operand1 = operand_stack.pop()
result = perform_operation(operand1, operand2, operator)
operand_stack.append(result)
return operand_stack.pop()
def perform_operation(operand1, operand2, operator):
if operator == '+':
return operand1 + operand2
elif operator == '-':
return operand1 - operand2
elif operator == '*':
return operand1 * operand2
elif operator == '/':
return operand1 / operand2
```
在上面的代码中,我们定义了一个 `evaluate_expression` 函数来实现表达式求值,同时定义了一个 `perform_operation` 函数来完成两个操作数和一个运算符的计算。在 `evaluate_expression` 函数中,我们使用了两个栈 `operator_stack` 和 `operand_stack` 来分别存储运算符和操作数。我们还使用了一个 `precedence` 字典来保存每个运算符的优先级。
在遍历表达式中的每个元素时,如果该元素是数字,则将其入操作数栈中;如果是运算符,则与运算符栈的栈顶元素进行比较。如果运算符栈为空或者该运算符的优先级高于运算符栈栈顶元素的优先级,则将该运算符入栈。否则,从操作数栈中取出两个操作数,从运算符栈中取出一个运算符,进行运算,并将结果入操作数栈中,直到该运算符可以入栈。
当表达式遍历完成后,我们还需要将运算符栈中的剩余运算符和操作数栈中的剩余操作数进行计算,直到运算符栈为空。最后,操作数栈中的唯一元素即为表达式的最终计算结果。