带有括号的后缀表达式求值
时间: 2023-09-01 08:08:50 浏览: 68
可以使用栈来求解带有括号的后缀表达式,具体步骤如下:
1. 初始化一个空栈,用来存储操作数和中间结果;
2. 从左到右遍历后缀表达式的每个元素,包括数字和运算符,分别进行如下操作:
- 如果遇到数字,直接将其压入栈中;
- 如果遇到运算符,弹出栈顶的两个元素(先弹出的是第二个操作数,后弹出的是第一个操作数),进行运算,并将结果压入栈中;
- 如果遇到左括号,将其压入栈中;
- 如果遇到右括号,不断弹出栈顶元素,直到遇到左括号,将弹出的元素作为一个整体压入栈中,表示括号内的表达式的值。
3. 遍历完后缀表达式后,栈中只剩下一个元素,即为表达式的结果。
以下是一个示例代码实现:
```python
def eval_suffix_expression_with_parenthesis(expression):
stack = []
for elem in expression:
if elem.isdigit():
stack.append(int(elem))
elif elem == '+':
operand1 = stack.pop()
operand2 = stack.pop()
stack.append(operand2 + operand1)
elif elem == '-':
operand1 = stack.pop()
operand2 = stack.pop()
stack.append(operand2 - operand1)
elif elem == '*':
operand1 = stack.pop()
operand2 = stack.pop()
stack.append(operand2 * operand1)
elif elem == '/':
operand1 = stack.pop()
operand2 = stack.pop()
stack.append(operand2 / operand1)
elif elem == '(':
stack.append(elem)
elif elem == ')':
sub_expression = []
while stack[-1] != '(':
sub_expression.append(stack.pop())
stack.pop() # pop out the left parenthesis
sub_expression.reverse()
sub_expression_result = eval_suffix_expression_with_parenthesis(sub_expression)
stack.append(sub_expression_result)
return stack[0]
```
注意这里的实现假设输入的后缀表达式是一个合法的表达式,即括号是匹配的,并且不包含其他非法情况如空白字符等。