中缀表达式转后缀表达式python

中缀表达式转后缀表达式，也称为前缀表达式，是一种常见的计算机算法题型，通常通过栈来实现。Python中可以使用递归方法来进行转换。基本步骤如下：

1. 创建一个空栈和一个空列表用于存放后缀表达式的元素。
2. 遍历中缀表达式的每个字符：
- 如果遇到数字，直接将其添加到后缀表达式列表中。
- 如果遇到运算符，检查它的优先级：
- 如果栈顶运算符优先级小于当前运算符，将栈顶的运算符和操作数依次加入结果，并清空栈，然后将当前运算符压入栈。
- 否则，继续遍历直到遇到优先级更低或等于当前运算符的，再按照上述规则处理。
- 当遍历完所有字符后，如果栈不为空，需要将栈中的剩余运算符和操作数依次加入结果。
3. 返回后缀表达式列表。

下面是一个简单的示例Python代码：

def infix_to_postfix(expression):
    prec = {"+": 1, "-": 1, "*": 2, "/": 2, "^": 3}  # 定义运算符优先级
    output = []
    stack = []

    for char in expression:
        if char.isdigit():
            output.append(char)
        elif char in "+-*/^":
            while (stack and stack[-1] != "(" and prec[char] <= prec[stack[-1]]):
                output.append(stack.pop())
            stack.append(char)
        elif char == ")":
            while stack[-1] != "(":
                output.append(stack.pop())
            stack.pop()

    while stack:
        output.append(stack.pop())

    return ''.join(output)

# 使用示例
expression = "a+b*(c-d)"
postfix = infix_to_postfix(expression)
print(f"后缀表达式：{postfix}")