Python中缀表达式转后缀表达式及其实现

2023-04-10 00:00:00 表达式 后缀 中缀

中缀表达式转后缀表达式是一种常见的算法问题，其主要思路是使用栈数据结构来存储运算符和操作数，并按照一定的优先级进行操作，最终得到后缀表达式。

具体实现步骤如下：

  1. 定义运算符优先级，并将每个运算符与其优先级对应起来。

  2. 遍历中缀表达式，对于每个操作数，直接输出到输出字符串中。

  3. 对于每个运算符，判断其与栈顶运算符的优先级。

    • 如果当前运算符优先级大于栈顶运算符优先级，则直接将运算符入栈；

    • 否则，弹出栈顶运算符，将其输出，并继续判断当前运算符与新的栈顶运算符的优先级，直到当前运算符可以入栈。

  4. 遍历完中缀表达式后，如果栈中还有运算符，则依次弹出并输出。

接下来是Python代码实现：

# 定义运算符优先级
precedence = {'+': 1, '-': 1, '*': 2, '/': 2}

def infix_to_postfix(expression):
    stack = []  # 定义栈
    output = []  # 定义输出的列表

    # 遍历中缀表达式
    for char in expression:
        # 如果是操作数，直接输出到结果列表中
        if char.isalnum():
            output.append(char)
        # 如果是运算符
        elif char in precedence:
            # 如果栈中有运算符，并且栈顶运算符优先级大于等于当前运算符优先级，则弹出栈顶运算符
            while stack and stack[-1] in precedence and precedence[stack[-1]] >= precedence[char]:
                output.append(stack.pop())
            # 将当前运算符入栈
            stack.append(char)
        # 如果是括号
        elif char == '(':
            # 直接入栈
            stack.append(char)
        elif char == ')':
            # 弹出栈顶运算符，并输出直到遇到左括号
            while stack and stack[-1] != '(':
                output.append(stack.pop())
            # 弹出左括号
            stack.pop()

    # 将剩余的运算符依次弹出并输出
    while stack:
        output.append(stack.pop())

    # 将输出列表转换为字符串并返回
    return ''.join(output)

测试代码如下：

expression = '1+2*3-4/(5+6)'
print(infix_to_postfix(expression)) # 输出：123*+45+6/+-

即可得到中缀表达式1+2*3-4/(5+6)的后缀表达式123*+45+6/+-。

相关文章