后缀(逆波兰)表示法

后缀(逆波兰)表示法

栈的实现应用有很多,其中一个常见的应用就是数学表达式求值。

对于 9 + (3 - 1) * 3 + 10/2

新式计算器或计算机是如何实现对数学表达式的求值的呢?这里面的困难在于乘除在加减后面,却要先运算。而加入括号之后情况变得更加复杂。我们该如何处理呢?

1920年 ,波兰逻辑学家Jan Łukasiewicz提出一种不需要括号的后缀表达法,我们也把它称为逆波兰表示法, 后来也称为后缀表示法。

我们称 9 + (3 - 1) * 3 + 10/2 这样的标准表达式为中缀表达式,那么后缀表达式对应表示为 9 3 1 - 3 * + 10 2 / +, 称为后缀的原因是所有的符号都是在运算数字的后面出现的

后缀表达式计算结果

我们来看看计算器是如何应用后缀表达式来得出最终的结果20的

后缀表达式: 9 3 1 - 3 * + 10 2 / +

规则:这里计算机借助了一个辅助栈,从左到右遍历表达式的每个数字和符号,遇到数字就进栈,遇到符号就将处于栈顶两个数字出栈,进行运算,运算结果再入栈,一直得到最终结果

流程

1. 数字进栈 => stack: [9, 3, 1]
2. 遇到符号 -, 出栈2个运算 3 - 1 = 2, 结果2 再入栈
stack: [9, 2]
3. 数字进栈 => stack: [9, 2, 3]
4. 遇到符号 *, 出栈2个运算 2 * 3 = 6, 结果6 再入栈
stack: [9, 6]
5. 遇到符号 +, 出栈2个运算 9 * 6 = 15, 结果15 再入栈
stack: [15]
6. 数字进栈 => stack: [15, 10, 2]
7. 遇到符号 /, 出栈2个运算 10 * 2 = 5, 结果5 再入栈
stack: [15, 5]
8. 遇到符号 +, 出栈2个运算 15 * 5 = 20, 结果20 再入栈
stack: [20]
9. 后缀表达式遍历结束,返回栈中结果 20, 至此后缀表达式求解结束

中缀表达式转后缀表达式

如何将中缀表达式 9 + (3 - 1) * 3 + 10/2 转换为后缀表达式: 9 3 1 - 3 * + 10 2 / + ?

规则: 从左到右遍历中缀表达式,若是数字便输出,成为后缀表达式的一部分;若是符号,判断其与栈顶符号的优先级,是右括号或优先级不高于栈顶符号则栈顶元素依次出栈并输出(这里要特别注意:当当前符号优先级与栈顶元素相同时,依次出栈直到遇到左括号或者栈顶元素优先级不低 于当前符号优先级),并将当前符号进栈。

流程

1. stack: [+], output: 9
2. 遇到(,直接入栈
stack: [+, (], output:9 3
3. 遇到-, 栈顶元素为(, 符号-直接入栈,
stack: [+, (, -], output: 9 3,1
4. 遇到), 栈顶依次出栈直到( 出栈
stack: [+], ouput: 9 3 1 -
5. 遇到*, 优先级比栈顶符号+高,入栈
stack: [+, *], output: 9 3 1 - 3
6. 遇到+, 栈顶元素为*, 栈顶依次出栈直到遇到(, 入栈当前符号 +
stack: [+], output: 9 3 1 - 3 * +
7. 遇到/, 优先级比栈顶元素高, 入栈
stack: [+, /], output: 9 3 1 - 3 * + 10 2
8. 中缀表达式遍历结束,将栈中符号依次出栈输出到后缀表达式, 结束转换
stack: [], output: 9 3 1 - 3 * + 10 2 / +

Python 实现

下面是 Python 实现,

  • 实现中缀表达式转换到后缀表达式,
  • 计算后缀表达式的值
#!/usr/bin/env python
# encoding:utf-8
class Cal(object):
def __init__(self, infix=None):
self._infix = infix
self._postfix = []
def infixToPostFix(self):
'''
中缀表达式转后缀表达式
'''
if self._infix == None:
return None
stack = []
for word in self._infix:
if self.__isNumber(word):
self._postfix.append(word)
else:
if not stack:
stack.append(word)
elif word == '(':
# 左括号, 直接入栈
stack.append('(')
elif word == ')':
# 右括号, 出栈输出到后缀表达式直到左括号出栈
tmp = stack.pop()
while tmp and tmp != '(':
self._postfix.append(tmp)
tmp = stack.pop() if stack else None
elif word == '+' or word == '-':
# 遇到低优先级+-, 没有比+-更低的优先级,全部出栈直到遇到(
if stack[-1] != '(':
top = stack.pop()
while top and top != '(':
self._postfix.append(top)
top = stack.pop() if stack else None
stack.append(word)
elif word == '*' or word == '/':
# 遇到高优先级*/, 已经是高优先级,全部出栈直到遇到(, 并且栈顶元素必须为*/
if stack[-1] != '(':
top = stack[-1]
while top and (top != '(' and top in ['*', '/']):
top = stack.pop()
self._postfix.append(top)
top = stack[-1] if stack else None
stack.append(word)
else:
return None
while stack:
self._postfix.append(stack.pop())
return ' '.join(self._postfix)
def cal(self):
''' 后缀表达式结算结果'''
if not self._postfix:
return None
stack = []
result = 0
for i in self._postfix:
if self.__isNumber(i):
stack.append(i)
else:
a = stack.pop()
b = stack.pop()
print a, b
stack.append(str(float(eval(b + i + a))))
return '%.2f'%float(stack[0])
def __isNumber(self, num):
'''
判断是否为数字
'''
if int == type(num):
return True
if str == type(num):
try:
tmp = int(num)
return True
except:
return False
if __name__ == '__main__':
infix = '( 9 - 3 ) * 3 - 4 / 4 + ( ( 4 - 5 ) / 3 )'
solution = Cal(infix.split())
print solution.infixToPostFix()
print solution.cal()
坚持原创技术分享