前缀中缀和后缀表达式计算
时间: 2024-06-14 09:05:41 浏览: 39
前缀、中缀和后缀表达式是数学中常用的三种表示方式。它们在计算机中的应用主要是为了方便计算机进行表达式的求值。
1. 前缀表达式(也称为波兰表达式):运算符位于操作数之前。例如,前缀表达式"+ 2 3"表示的是2+3。
2. 中缀表达式:运算符位于操作数之间。例如,中缀表达式"2 + 3"表示的是2+3。
3. 后缀表达式(也称为逆波兰表达式):运算符位于操作数之后。例如,后缀表达式"2 3 +"表示的是2+3。
计算前缀、中缀和后缀表达式的方法略有不同:
- 前缀表达式的计算方法:
1. 从右到左扫描表达式。
2. 遇到数字时,将其压入栈中。
3. 遇到运算符时,从栈中弹出两个数字进行运算,并将结果压入栈中。
4. 重复上述步骤,直到表达式结束,栈中的数字即为表达式的结果。
- 后缀表达式的计算方法:
1. 从左到右扫描表达式。
2. 遇到数字时,将其压入栈中。
3. 遇到运算符时,从栈中弹出两个数字进行运算,并将结果压入栈中。
4. 重复上述步骤,直到表达式结束,栈中的数字即为表达式的结果。
- 中缀表达式的计算方法:
1. 将中缀表达式转换为后缀表达式。
2. 使用后缀表达式的计算方法计算结果。
下面是一个示例,演示了如何计算前缀、中缀和后缀表达式:
前缀表达式计算:
```python
stack = []
expression = "+ 2 3"
tokens = expression.split()
for token in reversed(tokens):
if token.isdigit():
stack.append(int(token))
else:
operand1 = stack.pop()
operand2 = stack.pop()
if token == '+':
stack.append(operand1 + operand2)
elif token == '-':
stack.append(operand1 - operand2)
elif token == '*':
stack.append(operand1 * operand2)
elif token == '/':
stack.append(operand1 / operand2)
result = stack.pop()
print("Result:", result) # 输出:5
```
后缀表达式计算:
```python
stack = []
expression = "2 3 +"
tokens = expression.split()
for token in tokens:
if token.isdigit():
stack.append(int(token))
else:
operand2 = stack.pop()
operand1 = stack.pop()
if token == '+':
stack.append(operand1 + operand2)
elif token == '-':
stack.append(operand1 - operand2)
elif token == '*':
stack.append(operand1 * operand2)
elif token == '/':
stack.append(operand1 / operand2)
result = stack.pop()
print("Result:", result) # 输出:5
```
中缀表达式转后缀表达式:
```python
def infix_to_postfix(expression):
precedence = {'+': 1, '-': 1, '*': 2, '/': 2}
stack = []
postfix = []
tokens = expression.split()
for token in tokens:
if token.isdigit():
postfix.append(token)
elif token == '(':
stack.append(token)
elif token == ')':
while stack and stack[-1] != '(':
postfix.append(stack.pop())
stack.pop() # 弹出左括号
else:
while stack and stack[-1] != '(' and precedence[token] <= precedence.get(stack[-1], 0):
postfix.append(stack.pop())
stack.append(token)
while stack:
postfix.append(stack.pop())
return ' '.join(postfix)
expression = "2 + 3 * 4"
postfix_expression = infix_to_postfix(expression)
print("Postfix expression:", postfix_expression) # 输出:2 3 4 * +
# 使用后缀表达式的计算方法计算结果
stack = []
tokens = postfix_expression.split()
for token in tokens:
if token.isdigit():
stack.append(int(token))
else:
operand2 = stack.pop()
operand1 = stack.pop()
if token == '+':
stack.append(operand1 + operand2)
elif token == '-':
stack.append(operand1 - operand2)
elif token == '*':
stack.append(operand1 * operand2)
elif token == '/':
stack.append(operand1 / operand2)
result = stack.pop()
print("Result:", result) # 输出:14
```