MENU

中缀表达式转后缀表达式-python实现

• September 1, 2020 • Python,Algorithm阅读设置

【零】、概念与用处

  • 中缀表达式 - 操作符在两个数或代数中间,如a+b
  • 后缀表达式 - 操作符在两个数或代数后面,如ab+
  • 栈内优先级(isp) - in stack pripority,当操作符被放置于临时栈内时所拥有的优先级(权重)
  • 站外优先级(icp) - in coming priority,当操作符还未入栈,即在中值表达式中时所拥有的优先级
  • '#' - 用于标识表达式的开始,当栈尾为优先级为0的'#'时,可以便于运算,不用判断是否空栈
  • 操作符 - 该demo实现()+-*/
  • 代数和数 - 该demo将所有没被预设优先级的字符均当作代数和数直接输出,值得注意的是表达式中不该出现'#',因为多加个对'#'的异常判断会让代码不好看,所以没有处理'#'异常
  • 栈 - 栈是操作受限的线性表,即对一个线性表,如数组,限定其操作只能在一段进行插入和取出,则成为一个栈。因此,在python中可以直接通过list来作为一个栈,list中的append和pop方法即为入栈和出栈

虽然中缀表达式更便于人类理解,但后缀表达式更便于计算机计算,在计算表达式时,转换为后缀表达式是十分必要的
同时,中缀表达式转后缀表达式也是对栈的一个重要实践与应用

【一】、中缀转后缀逻辑

对于一个中缀表达式字符串,通过如下步骤转换为后缀表达式,整理自王道的《数据结构》

操作符#(*, /+, -)
栈内优先(isp)01536
栈外优先(icp)06421
  1. 创建一个临时的栈,用于调整运算符的顺序
  2. 设定运算符优先级
  3. 逐个处理中缀表达式字符

    1. 若为'(':入栈
    2. 若为')':栈中运算符依次出栈,直至遇到'(',并将'('删除
    3. 若为其它运算符:

      • 栈外优先级 高于 栈内:入栈
      • 栈外优先级 低于 或 等于 栈内:栈顶依次出栈并加入到后缀表达式,直至栈顶的优先级高于当前运算符,将当前运算符入栈
    4. 若为数字:直接加入后缀表达式

【二】、Demo的逻辑

  1. 创建一个临时的栈,用于调整运算符的顺序
  2. 设定运算符优先级
  3. 逐个处理中缀表达式字符

    1. 若字符拥有优先级,即字符为运算符,['#','(',')','+','-','*','/'],则:

      1. 栈顶先出栈用于对比,(也可以直接取栈顶对比不出栈,这样写只是不喜欢len-1算偏移)

        1. 当前运算符优先级 高于 栈顶:

          1. 栈顶归栈
          2. 当前运算符入栈
          3. 跳出处理下个字符
        2. 优先级相等:是'('和')'或'#'和'#',(出现'#'其实应该抛出异常,这里没作处理)

          1. 不作处理,即将括号或#抛弃
          2. 跳出处理下个字符
        3. 当前运算符优先级 低于 栈顶:

          1. 将栈顶运算符追加到后缀表达式尾部
          2. 继续对比下一个栈顶,直至符合3.1.1.1或3.1.1.2
    2. 若字符没有优先级,则默认该字符为代数或数字,直接将字符追加到后缀表达式尾部
  4. 输出后缀表达式

值得注意的是,对于优先级的处理与王道书中中缀转后缀逻辑不完全相同,因为在优先级表格设计得足够好的情况下,并不需要额外对比括号等特殊符号。这有利于扩展更多的运算符如中括号大括号等

【三】、代码

def infix_to_postfix(infix_expression):
    isp = {'#':0, '(':1, '*':5, '/':5, '+':3, '-':3, ')':6}
    icp = {'#':0, '(':6, '*':4, '/':4, '+':2, '-':2, ')':1}

    operator_stack = ['#']
    postfix_expression = ''
    print("|code\t\t|stack\t\t|expression\t\t")
    for char in infix_expression:
        if char not in isp:
            # 将非操作符的视为数字或代数直接输出
            postfix_expression += char
        else:
            while len(operator_stack)>0:
                # 取出栈顶元素用于对比
                top_elem = operator_stack.pop()
                if icp[char] > isp[top_elem]:
                    # 新操作符优先级高于栈顶,入栈,并跳到下个字符
                    operator_stack.append(top_elem)
                    operator_stack.append(char)
                    break
                if icp[char] == isp[top_elem]:
                    # 优先级相等,比如'('和')',则抛弃,并跳到下个字符
                    break
                # 新操作符优先级低于栈顶,输出栈顶,继续对比下一个栈顶
                postfix_expression += top_elem
        print("|%s\t\t|%s\t\t|%s\t\t" % (char, ''.join(operator_stack), postfix_expression))


    # 将栈中剩余的,除'#'外的依次出栈          
    while len(operator_stack)>1:
        postfix_expression += operator_stack.pop()

    # 移除后缀表达式中的'(',')'
    postfix_expression = postfix_expression.replace('(','').replace(')','')
    return postfix_expression

【四】、测试输出

print(infix_to_postfix("a+b-a*((c+d)/e-f)+g"))

============ RESTART: C:\Users\Nukami\Desktop\infix_to_postfix_b.py ============
|code        |stack        |expression        
|a        |#        |a        
|+        |#+        |a        
|b        |#+        |ab        
|-        |#-        |ab+        
|a        |#-        |ab+a        
|*        |#-*        |ab+a        
|(        |#-*(        |ab+a        
|(        |#-*((        |ab+a        
|c        |#-*((        |ab+ac        
|+        |#-*((+        |ab+ac        
|d        |#-*((+        |ab+acd        
|)        |#-*(        |ab+acd+        
|/        |#-*(/        |ab+acd+        
|e        |#-*(/        |ab+acd+e        
|-        |#-*(-        |ab+acd+e/        
|f        |#-*(-        |ab+acd+e/f        
|)        |#-*        |ab+acd+e/f-        
|+        |#+        |ab+acd+e/f-*-        
|g        |#+        |ab+acd+e/f-*-g        
ab+acd+e/f-*-g+