Python中缀表达式转换成后缀

在Python中，中缀表达式（如 "A + B * C"）通常表示数学运算的顺序，而后缀表达式（也称为逆波兰表示法，记作 "ABC*" +）则是将操作符放在它们作用的两个操作数之后。转换中缀表达式到后缀表达式的算法通常是通过栈的数据结构来实现的，例如Shunting Yard算法：

1. 创建一个空的后缀表达式列表和一个栈。
2. 遍历中缀表达式的每个字符：
- 如果它是数字，就直接添加到后缀表达式列表。
- 如果它是左括号，将其压入栈。
- 如果它是右括号，弹出栈中的元素直到遇到左括号，并依次添加到后缀表达式列表。
- 如果它是运算符，比较其优先级，如果栈顶运算符优先级低，则将其推入栈；如果优先级高或相等，就将栈顶运算符弹出并添加到列表，然后将当前运算符压入栈。当遍历完运算符后，再将剩余的栈顶运算符添加到列表。
3. 当遍历完整个中缀表达式后，如果栈非空，将栈中的所有运算符依次弹出并添加到后缀表达式列表。

以下是一个简单的Python示例，展示了如何使用递归来实现这个过程：

def infix_to_postfix(expression):
    # 定义操作符优先级
    prec = {"+": 1, "-": 1, "*": 2, "/": 2, "^": 3}

    def apply_operator(operators, values):
        op = operators.pop()
        val2 = values.pop()
        val1 = values.pop()
        values.append(str(eval(f"{val1}{op}{val2}")))

    def greater_precedence(op1, op2):
        return prec[op1] > prec[op2]

    def tokenize(expression):
        i, n = 0, len(expression)
        while i < n:
            if expression[i].isdigit():
                j = i
                while j < n and expression[j].isdigit():
                    j += 1
                yield int(expression[i:j])
                i = j
            elif expression[i] in "+-*/^":
                yield expression[i]
                i += 1
            else:
                i += 1

    operators = []
    values = []

    for token in tokenize(expression):
        if isinstance(token, int):
            values.append(str(token))
        elif token in "+-*/^":
            while (operators and greater_precedence(token, operators[-1])):
                apply_operator(operators, values)
            operators.append(token)
        else:
            while operators and operators[-1] != '(':
                apply_operator(operators, values)
            operators.append(token)
    
    while operators:
        apply_operator(operators, values)
    
    return ' '.join(values)

# 测试
expression = "A + B * C"
postfix_expression = infix_to_postfix(expression)
print(f"Infix to postfix conversion: {expression} -> {postfix_expression}")