表达式转换是栈的重要应用之一，尤其在处理算术表达式时非常有用。常见的转换包括：

1. 中缀表达式转后缀表达式（逆波兰表达式）
2. 中缀表达式转前缀表达式

下面以中缀转后缀为例说明：

中缀表达式

• 运算符在操作数之间，例如：A + B * C

后缀表达式

• 运算符在操作数之后，例如：A B C * +

转换规则

使用栈结构进行中缀表达式到后缀表达式的转换时，遵循以下步骤：

1.初始化

• 创建一个空栈用于存放运算符。
• 遍历中缀表达式的每个字符。

2.遇到操作数

直接将操作数加入到输出（后缀表达式）。

3.遇到左括号 (

将左括号直接入栈。

4.遇到右括号 )

• 弹出栈顶元素并加入输出，直到遇到左括号。
• 弹出左括号（不加入输出）。

5.遇到运算符

• 如果栈为空，或者栈顶为左括号 (，直接将运算符入栈。
• 否则比较当前运算符和栈顶运算符的优先级：若当前运算符的优先级高于栈顶运算符，入栈。若当前运算符的优先级小于或等于栈顶运算符，弹出栈顶运算符并加入输出，重复比较直到可以将当前运算符入栈。

6.表达式遍历结束后

将栈中剩余的所有运算符依次弹出并加入输出。

优先级定义

• 括号：( 和 ) 的优先级最高。
• 乘除：* 和 / 优先级高于加减。
• 加减：+ 和 - 优先级最低。

实例：A + B * C + D

1. 中缀表达式：

A + B * C + D

2. 转换过程：

3. 栈清空：

A B C * + D +

完整算法的代码实现（Python）

def infix_to_postfix(expression):
    precedence = {'+': 1, '-': 1, '*': 2, '/': 2, '(': 0}
    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 precedence[stack[-1]] >= precedence[char]:
                postfix.append(stack.pop())
            stack.append(char)
    
    while stack:  # 清空栈
        postfix.append(stack.pop())
    
    return ''.join(postfix)

# 示例
expression = "A+B*C+D"
print(infix_to_postfix(expression))  # 输出: "ABC*+D+"

每天坚持学习一点点，不求有回报，只愿可以丰富自己！！！

Tags：表达式