数据结构入门(二)栈的应用之数学表达式求值
??在文章数据结构入门(一)栈的实现中,我们已经知道了如何去实现“栈”这个数据结构,并且介绍了一个它的应用:数的进制转换。在本文中,将会介绍栈的第二个应用,也就是栈在数学表达式求值中的应用。 ??我们分以下几步对数学表达式进行求值。 栈的实现; 中缀表达式转后缀表达式; 后缀表达式求值。 先不着急明白上述术语,你看下去就会明白了。 栈的实现??以下是栈的Python实现(Stack.py),代码如下: # -*- coding: utf-8 -*- class Empty(Exception): # Error attempting to access an element from an empty container pass class Stack: # initialize def __init__(self): self.__data = [] # length of Stack def __len__(self): return len(self.__data) # whether the Stack is empty def is_empty(self): return len(self.__data) == 0 # push an element is Stack def push(self,e): self.__data.append(e) # top element of Stack def top(self): if self.is_empty(): raise Empty('Stack is empty') return self.__data[-1] # remove the top element of Stack def pop(self): if self.is_empty(): raise Empty('Stack is empty') return self.__data.pop() # clear the Stack def clear(self): while not self.is_empty(): self.pop() 中缀表达式转后缀表达式??首先,我们来看一下数学表达式的三种形式:前缀表达式,中缀表达式,后缀表达式。 ??**中缀表达式(Infix Expression)**就是我们平时常用的书写方式,带有括号。**前缀表达式(Prefix Expression)**要求运算符出现在运算数字的前面,**后缀表达式(Postfix Expression)**要求运算符出现在运算数字的后面,一般这两种表达式不出现括号。示例如下: 中缀表达式 前缀表达式 后缀表达式 A + B * C + D + + A * B C D A B C * + D + (A + B) * (C + D) * + A B + C D A B + C D + * A * B + C * D + * A B * C D A B * C D * + A + B + C + D + + + A B C D A B + C + D + 一般在计算机中,为了方便对表达式求值,我们需要将熟悉的中缀表达式转化为后缀表达式。 ??中缀表达式转后缀表达式的算法如下: 创建一个空栈opstack,用于储存运算符。创建一个空的列表,用于储存输出结果。 将输入的中缀表达式(字符串形式)用字符串的split方法转化为一个列表。 从左到右对该列表进行遍历操作(元素为token),如下: 如果token为运算数,则将它添加(append)至输出列表中。 如果token为左小括号,则将它压入(psuh)到opstack中。 如果token是右小括号,则对opstack进行pop操作,直至对应的左小括号被移出。将移出的运算符添加(append)到输出列表的末端。 如果token是 *,/,+,-,中的一个,则将其压入(push)到opstack中。注意,先要移除那些运算优先级大于等于该token的运算符,并将它们添加到输出列表中。 当上述过程结果后,检查opstack。任何还在opstack中的运算符都应移除,并将移出的运算符添加(append)到输出列表的末端。 ??上述过程的完整Python代码如下: # -*- coding: utf-8 -*- from Stack import Stack # 中缀表达式转化为后缀表达式 def infixToPostfix(infixexpr): prec = {"*": 3,"/": 3,"+": 2,"-": 2,"(": 1} opStack = Stack() postfixList = [] tokenList = infixexpr.split() for token in tokenList: if token.isdigit() or '.' in token: postfixList.append(token) elif token == '(': opStack.push(token) elif token == ')': topToken = opStack.pop() while topToken != '(': postfixList.append(topToken) topToken = opStack.pop() else: while (not opStack.is_empty()) and (prec[opStack.top()] >= prec[token]): postfixList.append(opStack.pop()) opStack.push(token) while not opStack.is_empty(): postfixList.append(opStack.pop()) return " ".join(postfixList) # inExpr = "( ( 1 + 2 ) * 3 ) * ( 3 - 1.2 )" inExpr = "10 + 3 * 5 / ( 16 - 4 )" postExpr = infixToPostfix(inExpr) print(postExpr) 输出结果如下: 10 3 5 * 16 4 - / + 后缀表达式求值??当把中缀表达式转化为后缀表达式之后,我们再利用栈对后缀表达式求值。其具体的算法如下: 建立一个栈来存储待计算的运算数; 遍历字符串,遇到运算数则压入栈中,遇到运算符则出栈运算数(2次),进行相应的计算,计算结果是新的操作数,压入栈中,等待计算; 按上述过程,遍历完整个表达式,栈中只剩下最终结果; ??完整的Python代码如下:(接以上代码) # -*- coding: utf-8 -*- from Stack import Stack # 两个数的运算,除法时分母不为0 def operate(op,num1,num2): if num2 == 0: raise ZeroDivisionError else: res = { '+': num1 + num2, '-': num1 - num2, '*': num1 * num2, '/': num1 / num2, } return res[op] # 将字符串转化为浮点型或整型数字 def str2num(s): if '.' in s: return float(s) else: return int(s) # 后缀表达式求值 def evalPostfix(e): tokens = e.split() # 后缀表达式转化为列表 s = Stack() for token in tokens: if token.isdigit() or '.' in token: # 如果当前元素是数字 s.push(str2num(token)) elif token in '+-*/': # 如果当前元素是运算符 op2 = s.pop() op1 = s.pop() s.push(operate(token,op1,op2)) # 计算结果入栈 return s.pop() # inExpr = "( ( 1 + 2 ) * 3 ) * ( 3 - 1.2 )" inExpr = "10 + 3 * 5 / ( 16 - 4 )" postExpr = infixToPostfix(inExpr) print(postExpr) result = evalPostfix(postExpr) print(result) 输出结果: 11.25 请务必注意,我们输入的中缀表达式中,每个运算符或运算符要用空格隔开。 参考文献3.9. Infix,Prefix and Postfix Expressions: http://interactivepython.org/runestone/static/pythonds/BasicDS/InfixPrefixandPostfixExpressions.html Python算法实战系列之栈: http://python.jobbole.com/87581/ 注意:本人现已开通微信公众号: Python爬虫与算法(微信号为:easy_web_scrape), 欢迎大家关注哦~~ (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |