【零】、概念与用处
- 中缀表达式 - 操作符在两个数或代数中间,如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 |
- 创建一个临时的栈,用于调整运算符的顺序
- 设定运算符优先级
逐个处理中缀表达式字符
- 若为'(':入栈
- 若为')':栈中运算符依次出栈,直至遇到'(',并将'('删除
若为其它运算符:
- 栈外优先级 高于 栈内:入栈
- 栈外优先级 低于 或 等于 栈内:栈顶依次出栈并加入到后缀表达式,直至栈顶的优先级高于当前运算符,将当前运算符入栈
- 若为数字:直接加入后缀表达式
【二】、Demo的逻辑
- 创建一个临时的栈,用于调整运算符的顺序
- 设定运算符优先级
逐个处理中缀表达式字符
若字符拥有优先级,即字符为运算符,['#','(',')','+','-','*','/'],则:
栈顶先出栈用于对比,(也可以直接取栈顶对比不出栈,这样写只是不喜欢len-1算偏移)
当前运算符优先级 高于 栈顶:
- 栈顶归栈
- 当前运算符入栈
- 跳出处理下个字符
优先级相等:是'('和')'或'#'和'#',(出现'#'其实应该抛出异常,这里没作处理)
- 不作处理,即将括号或#抛弃
- 跳出处理下个字符
当前运算符优先级 低于 栈顶:
- 将栈顶运算符追加到后缀表达式尾部
- 继续对比下一个栈顶,直至符合3.1.1.1或3.1.1.2
- 若字符没有优先级,则默认该字符为代数或数字,直接将字符追加到后缀表达式尾部
- 输出后缀表达式
值得注意的是,对于优先级的处理与王道书中中缀转后缀逻辑不完全相同,因为在优先级表格设计得足够好的情况下,并不需要额外对比括号等特殊符号。这有利于扩展更多的运算符如中括号大括号等
【三】、代码
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+