【零】、概念与用处

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

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

【一】、中缀转后缀逻辑

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

操作符	#	(	*, /	+, -	)
栈内优先(isp)	0	1	5	3	6
栈外优先(icp)	0	6	4	2	1

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+