数据结构入门（二）栈的应用之数学表达式求值

概述本文章向大家介绍数据结构入门（二）栈的应用之数学表达式求值，主要包括数据结构入门（二）栈的应用之数学表达式求值使用实例、应用技巧、基本知识点总结和需要注意事项，具有一定的参考价值，需要的朋友可以参考一下。

  在文章数据结构入门（一）栈的实现中，我们已经知道了如何去实现“栈”这个数据结构，并且介绍了一个它的应用：数的进制转换。在本文中，将会介绍栈的第二个应用，也就是栈在数学表达式求值中的应用。

  我们分以下几步对数学表达式进行求值。

栈的实现；

中缀表达式转后缀表达式；

后缀表达式求值。

先不着急明白上述术语，你看下去就会明白了。

栈的实现

  以下是栈的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）， 欢迎大家关注哦~~

总结

以上是内存溢出为你收集整理的数据结构入门（二）栈的应用之数学表达式求值全部内容，希望文章能够帮你解决数据结构入门（二）栈的应用之数学表达式求值所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。