前缀表达式和中缀表达式和后缀表达式的代码
时间: 2025-01-18 11:06:38 浏览: 28
前缀表达式(波兰式)、中缀表达式和后缀表达式(逆波兰式)是计算机科学中用于表示数学表达式的三种不同方式。以下是它们的定义和相应的代码示例:
1. **中缀表达式**:这是我们日常使用的表达式形式,如 `3 + 4 * 2 / (1 - 5)`。
2. **前缀表达式**:操作符位于操作数之前,如 `+ 3 / * 4 2 - 1 5`。
3. **后缀表达式**:操作符位于操作数之后,如 `3 4 2 * 1 5 - / +`。
### 中缀表达式转后缀表达式(逆波兰式)
```python
def infix_to_postfix(expression):
precedence = {'+':1, '-':1, '*':2, '/':2, '^':3}
stack = []
postfix = []
for char in expression:
if char.isalnum():
postfix.append(char)
elif char == '(':
stack.append(char)
elif char == ')':
while stack and stack[-1] != '(':
postfix.append(stack.pop())
stack.pop()
else:
while stack and stack[-1] != '(' and precedence[char] <= precedence.get(stack[-1], 0):
postfix.append(stack.pop())
stack.append(char)
while stack:
postfix.append(stack.pop())
return ' '.join(postfix)
# 示例
expression = "3+4*2/(1-5)"
print(infix_to_postfix(expression))
```
### 后缀表达式求值
```python
def evaluate_postfix(expression):
stack = []
for char in expression:
if char.isalnum():
stack.append(int(char))
else:
b = stack.pop()
a = stack.pop()
if char == '+':
stack.append(a + b)
elif char == '-':
stack.append(a - b)
elif char == '*':
stack.append(a * b)
elif char == '/':
stack.append(a / b)
return stack.pop()
# 示例
expression = "342*15-/+" # 对应中缀表达式 "3+4*2/(1-5)"
print(evaluate_postfix(expression))
```
### 前缀表达式求值
```python
def evaluate_prefix(expression):
stack = []
for char in reversed(expression):
if char.isalnum():
stack.append(int(char))
else:
a = stack.pop()
b = stack.pop()
if char == '+':
stack.append(a + b)
elif char == '-':
stack.append(a - b)
elif char == '*':
stack.append(a * b)
elif char == '/':
stack.append(a / b)
return stack.pop()
# 示例
expression = "+3/*42-15" # 对应中缀表达式 "3+4*2/(1-5)"
print(evaluate_prefix(expression))
```
通过这些代码示例,你可以将中缀表达式转换为后缀表达式,并对后缀和前缀表达式进行求值。
阅读全文
相关推荐


















