??在文章數(shù)據(jù)結(jié)構(gòu)入門（一）棧的實現(xiàn)中，我們已經(jīng)知道了如何去實現(xiàn)“?！边@個數(shù)據(jù)結(jié)構(gòu)，并且介紹了一個它的應(yīng)用：數(shù)的進制轉(zhuǎn)換。在本文中，將會介紹棧的第二個應(yīng)用，也就是棧在數(shù)學表達式求值中的應(yīng)用。
??我們分以下幾步對數(shù)學表達式進行求值。

• 棧的實現(xiàn)；
• 中綴表達式轉(zhuǎn)后綴表達式；
• 后綴表達式求值。

先不著急明白上述術(shù)語，你看下去就會明白了。

棧的實現(xiàn)

??以下是棧的Python實現(xiàn)（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()

中綴表達式轉(zhuǎn)后綴表達式

??首先，我們來看一下數(shù)學表達式的三種形式：前綴表達式，中綴表達式，后綴表達式。
??中綴表達式（Infix Expression）就是我們平時常用的書寫方式，帶有括號。前綴表達式（Prefix Expression）要求運算符出現(xiàn)在運算數(shù)字的前面，后綴表達式（Postfix Expression）要求運算符出現(xiàn)在運算數(shù)字的后面，一般這兩種表達式不出現(xiàn)括號。示例如下：

一般在計算機中，為了方便對表達式求值，我們需要將熟悉的中綴表達式轉(zhuǎn)化為后綴表達式。
??中綴表達式轉(zhuǎn)后綴表達式的算法如下：

1. 創(chuàng)建一個空棧opstack，用于儲存運算符。創(chuàng)建一個空的列表，用于儲存輸出結(jié)果。
2. 將輸入的中綴表達式（字符串形式）用字符串的split方法轉(zhuǎn)化為一個列表。
3. 從左到右對該列表進行遍歷操作（元素為token），如下：
   • 如果token為運算數(shù)，則將它添加（append）至輸出列表中。
   • 如果token為左小括號，則將它壓入（psuh）到opstack中。
   • 如果token是右小括號，則對opstack進行pop操作，直至對應(yīng)的左小括號被移出。將移出的運算符添加（append）到輸出列表的末端。
   • 如果token是 *, /, +, -, 中的一個，則將其壓入（push）到opstack中。注意，先要移除那些運算優(yōu)先級大于等于該token的運算符，并將它們添加到輸出列表中。
4. 當上述過程結(jié)果后，檢查opstack。任何還在opstack中的運算符都應(yīng)移除，并將移出的運算符添加（append）到輸出列表的末端。

??上述過程的完整Python代碼如下：

# -*- coding: utf-8 -*-
from Stack import Stack

# 中綴表達式轉(zhuǎn)化為后綴表達式
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)

輸出結(jié)果如下：

10 3 5 * 16 4 - / +

后綴表達式求值

??當把中綴表達式轉(zhuǎn)化為后綴表達式之后，我們再利用棧對后綴表達式求值。其具體的算法如下：

1. 建立一個棧來存儲待計算的運算數(shù)；
2. 遍歷字符串，遇到運算數(shù)則壓入棧中，遇到運算符則出棧運算數(shù)(2次)，進行相應(yīng)的計算，計算結(jié)果是新的操作數(shù)，壓入棧中，等待計算；
3. 按上述過程，遍歷完整個表達式，棧中只剩下最終結(jié)果；

??完整的Python代碼如下：(接以上代碼)

# -*- coding: utf-8 -*-
from Stack import Stack

# 兩個數(shù)的運算, 除法時分母不為0
def operate(op, num1, num2):
    if num2 == 0:
        raise ZeroDivisionError
    else:
        res = {
                '+': num1 + num2,
                '-': num1 - num2,
                '*': num1 * num2,
                '/': num1 / num2,
              }
        return res[op]

# 將字符串轉(zhuǎn)化為浮點型或整型數(shù)字
def str2num(s):
    if '.' in s:
        return float(s)
    else:
        return int(s)

# 后綴表達式求值
def evalPostfix(e):

    tokens = e.split()  # 后綴表達式轉(zhuǎn)化為列表
    s = Stack()
    for token in tokens:
        if token.isdigit() or '.' in token:  # 如果當前元素是數(shù)字
            s.push(str2num(token))
        elif token in '+-*/':  # 如果當前元素是運算符
            op2 = s.pop()
            op1 = s.pop()
            s.push(operate(token, op1, op2))  # 計算結(jié)果入棧
    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)

輸出結(jié)果：

11.25

請務(wù)必注意，我們輸入的中綴表達式中，每個運算符或運算符要用空格隔開。

參考文獻

1. 3.9. Infix, Prefix and Postfix Expressions: http://interactivepython.org/runestone/static/pythonds/BasicDS/InfixPrefixandPostfixExpressions.html
2. Python算法實戰(zhàn)系列之棧: http://python.jobbole.com/87581/

注意：本人現(xiàn)已開通微信公眾號： Python爬蟲與算法（微信號為：easy_web_scrape）， 歡迎大家關(guān)注哦~~