数据结构表达式计算代码
时间: 2024-04-29 19:18:06 浏览: 7
当涉及到表达式计算时,数据结构是非常重要的。常见的数据结构用于表达式计算的代码包括栈和队列。
一种常见的表达式计算方法是使用逆波兰表达式(Reverse Polish Notation,RPN),也称为后缀表达式。在逆波兰表达式中,操作符位于操作数之后。例如,表达式 "2 + 3" 的逆波兰表达式为 "2 3 +"。
下面是一个使用栈来计算逆波兰表达式的示例代码:
```python
def evaluate_expression(expression):
stack = []
operators = {'+': lambda x, y: x + y,
'-': lambda x, y: x - y,
'*': lambda x, y: x * y,
'/': lambda x, y: x / y}
for token in expression:
if token.isdigit():
stack.append(int(token))
elif token in operators:
operand2 = stack.pop()
operand1 = stack.pop()
result = operators[token](operand1, operand2)
stack.append(result)
return stack.pop()
expression = ['2', '3', '+']
result = evaluate_expression(expression)
print(result) # 输出 5
```
在这个示例代码中,我们使用一个栈来存储操作数,并且定义了一个字典来存储操作符及其对应的操作函数。遍历逆波兰表达式中的每个标记,如果是数字,则将其转换为整数并压入栈中;如果是操作符,则从栈中弹出两个操作数,并使用对应的操作函数进行计算,然后将结果压入栈中。最后,栈中剩下的唯一元素就是表达式的计算结果。