Python 非递归后缀表达式转换算法详解

以下是非递归方式的后缀表达式转换算法的 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()  # remove '(' from stack
        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 = 'a+b*c-(d/e+f)*g'
postfix_expression = infix_to_postfix(expression)
print(postfix_expression)  # 输出：abc*+de/f+g*-

该算法利用了一个操作符栈（stack）和一个后缀表达式列表（postfix），遍历中缀表达式的每个字符，根据不同情况进行处理。具体步骤如下：

初始化空的操作符栈和后缀表达式列表。
遍历中缀表达式的每个字符：
- 如果字符是字母或数字，则直接将其添加到后缀表达式列表中。
- 如果字符是左括号'('，则将其压入操作符栈。
- 如果字符是右括号')'，则将操作符栈中的元素弹出并添加到后缀表达式列表中，直到遇到左括号为止。然后将左括号从栈中弹出。
- 如果字符是操作符，则判断其与操作符栈栈顶元素的优先级：
  - 如果操作符栈为空或栈顶元素是左括号'('，则将操作符直接压入操作符栈。
  - 否则，将操作符栈中优先级高于等于当前操作符的元素弹出并添加到后缀表达式列表中，直到遇到优先级小于当前操作符的元素或栈为空。然后将当前操作符压入操作符栈。
遍历完中缀表达式后，将操作符栈中剩余的元素依次弹出并添加到后缀表达式列表中。
将后缀表达式列表中的元素连接起来，形成最终的后缀表达式。

该算法的时间复杂度为O(n)，其中n是中缀表达式的长度。