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

女爷i 2022-04-02 04:55 143阅读 0赞

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

*  栈的实现；
 *  中缀表达式转后缀表达式；
 *  后缀表达式求值。

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

### 栈的实现 ###

以下是栈的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）\*\*要求运算符出现在运算数字的后面，一般这两种表达式不出现括号。示例如下：

<table> 
 <thead> 
  <tr> 
   <th>中缀表达式</th> 
   <th>前缀表达式</th> 
   <th>后缀表达式</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>A + B * C + D</td> 
   <td>+ + A * B C D</td> 
   <td>A B C * + D +</td> 
  </tr> 
  <tr> 
   <td>(A + B) * (C + D)</td> 
   <td>* + A B + C D</td> 
   <td>A B + C D + *</td> 
  </tr> 
  <tr> 
   <td>A * B + C * D</td> 
   <td>+ * A B * C D</td> 
   <td>A B * C D * +</td> 
  </tr> 
  <tr> 
   <td>A + B + C + D</td> 
   <td>+ + + A B C D</td> 
   <td>A B + C + D +</td> 
  </tr> 
 </tbody> 
</table>

一般在计算机中，为了方便对表达式求值，我们需要将熟悉的中缀表达式转化为后缀表达式。  
  中缀表达式转后缀表达式的算法如下：

1.  创建一个**空栈opstack**，用于储存运算符。创建一个**空的列表**，用于储存输出结果。
2.  将输入的中缀表达式（字符串形式）用字符串的**split**方法转化为一个列表。
3.  从左到右对该列表进行遍历操作（元素为token），如下：
    
     *  如果token为运算数，则将它添加（append）至输出列表中。
     *  如果token为左小括号，则将它压入（psuh）到opstack中。
     *  如果token是右小括号，则对opstack进行pop操作，直至对应的左小括号被移出。将移出的运算符添加（append）到输出列表的末端。
     *  如果token是 \*, /, +, -, 中的一个，则将其压入（push）到opstack中。注意，先要移除那些运算优先级大于等于该token的运算符，并将它们添加到输出列表中。
4.  当上述过程结果后，检查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 - / +

### 后缀表达式求值 ###

当把中缀表达式转化为后缀表达式之后，我们再利用栈对后缀表达式求值。其具体的算法如下：

1.  建立一个栈来存储待计算的运算数；
2.  遍历字符串，遇到运算数则压入栈中，遇到运算符则出栈运算数(2次)，进行相应的计算，计算结果是新的操作数，压入栈中，等待计算；
3.  按上述过程，遍历完整个表达式，栈中只剩下最终结果；

完整的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

请务必注意，我们输入的中缀表达式中，每个运算符或运算符要用空格隔开。

### 参考文献 ###

1.  3.9. Infix, Prefix and Postfix Expressions: [http://interactivepython.org/runestone/static/pythonds/BasicDS/InfixPrefixandPostfixExpressions.html][http_interactivepython.org_runestone_static_pythonds_BasicDS_InfixPrefixandPostfixExpressions.html]
2.  Python算法实战系列之栈: [http://python.jobbole.com/87581/][http_python.jobbole.com_87581]

注意：本人现已开通微信公众号： Python爬虫与算法（微信号为：easy\_web\_scrape）， 欢迎大家关注哦~~

[Link 1]: https://www.jianshu.com/p/d47397c21f2e
[Stack.py]: http://Stack.py
[http_interactivepython.org_runestone_static_pythonds_BasicDS_InfixPrefixandPostfixExpressions.html]: http://interactivepython.org/runestone/static/pythonds/BasicDS/InfixPrefixandPostfixExpressions.html
[http_python.jobbole.com_87581]: http://python.jobbole.com/87581/