??在文章數(shù)據(jù)結(jié)構(gòu)入門(mén)（一）棧的實(shí)現(xiàn)中稠茂，我們已經(jīng)知道了如何去實(shí)現(xiàn)“椖”這個(gè)數(shù)據(jù)結(jié)構(gòu)桩引，并且介紹了一個(gè)它的應(yīng)用：數(shù)的進(jìn)制轉(zhuǎn)換。在本文中澎语，將會(huì)介紹棧的第二個(gè)應(yīng)用，也就是棧在數(shù)學(xué)表達(dá)式求值中的應(yīng)用。
??我們分以下幾步對(duì)數(shù)學(xué)表達(dá)式進(jìn)行求值擅羞。
- 棧的實(shí)現(xiàn)尸变；
- 中綴表達(dá)式轉(zhuǎn)后綴表達(dá)式；
- 后綴表達(dá)式求值减俏。
先不著急明白上述術(shù)語(yǔ)召烂，你看下去就會(huì)明白了。
棧的實(shí)現(xiàn)
??以下是棧的Python實(shí)現(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()
中綴表達(dá)式轉(zhuǎn)后綴表達(dá)式
??首先奏夫，我們來(lái)看一下數(shù)學(xué)表達(dá)式的三種形式：前綴表達(dá)式，中綴表達(dá)式历筝，后綴表達(dá)式酗昼。
??中綴表達(dá)式（Infix Expression）就是我們平時(shí)常用的書(shū)寫(xiě)方式，帶有括號(hào)漫谷。前綴表達(dá)式（Prefix Expression）要求運(yùn)算符出現(xiàn)在運(yùn)算數(shù)字的前面仔雷，后綴表達(dá)式（Postfix Expression）要求運(yùn)算符出現(xiàn)在運(yùn)算數(shù)字的后面，一般這兩種表達(dá)式不出現(xiàn)括號(hào)舔示。示例如下：
| 中綴表達(dá)式 | 前綴表達(dá)式 | 后綴表達(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 | A B + C + D + |
一般在計(jì)算機(jī)中碟婆，為了方便對(duì)表達(dá)式求值，我們需要將熟悉的中綴表達(dá)式轉(zhuǎn)化為后綴表達(dá)式惕稻。
??中綴表達(dá)式轉(zhuǎn)后綴表達(dá)式的算法如下：
- 創(chuàng)建一個(gè)空棧opstack竖共，用于儲(chǔ)存運(yùn)算符。創(chuàng)建一個(gè)空的列表俺祠，用于儲(chǔ)存輸出結(jié)果公给。
- 將輸入的中綴表達(dá)式（字符串形式）用字符串的split方法轉(zhuǎn)化為一個(gè)列表。
- 從左到右對(duì)該列表進(jìn)行遍歷操作（元素為token）蜘渣，如下：
- 如果token為運(yùn)算數(shù)淌铐，則將它添加（append）至輸出列表中。
- 如果token為左小括號(hào)蔫缸，則將它壓入（psuh）到opstack中腿准。
- 如果token是右小括號(hào)，則對(duì)opstack進(jìn)行pop操作拾碌，直至對(duì)應(yīng)的左小括號(hào)被移出吐葱。將移出的運(yùn)算符添加（append）到輸出列表的末端。
- 如果token是 *, /, +, -, 中的一個(gè)校翔，則將其壓入（push）到opstack中弟跑。注意，先要移除那些運(yùn)算優(yōu)先級(jí)大于等于該token的運(yùn)算符防症，并將它們添加到輸出列表中孟辑。
- 當(dāng)上述過(guò)程結(jié)果后哎甲，檢查opstack。任何還在opstack中的運(yùn)算符都應(yīng)移除扑浸，并將移出的運(yùn)算符添加（append）到輸出列表的末端烧给。
??上述過(guò)程的完整Python代碼如下：
# -*- coding: utf-8 -*-
from Stack import Stack
# 中綴表達(dá)式轉(zhuǎn)化為后綴表達(dá)式
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 - / +
后綴表達(dá)式求值
??當(dāng)把中綴表達(dá)式轉(zhuǎn)化為后綴表達(dá)式之后，我們?cè)倮脳?duì)后綴表達(dá)式求值喝噪。其具體的算法如下：
- 建立一個(gè)棧來(lái)存儲(chǔ)待計(jì)算的運(yùn)算數(shù)础嫡；
- 遍歷字符串，遇到運(yùn)算數(shù)則壓入棧中酝惧，遇到運(yùn)算符則出棧運(yùn)算數(shù)(2次)榴鼎，進(jìn)行相應(yīng)的計(jì)算，計(jì)算結(jié)果是新的操作數(shù)晚唇，壓入棧中巫财，等待計(jì)算；
- 按上述過(guò)程哩陕，遍歷完整個(gè)表達(dá)式平项，棧中只剩下最終結(jié)果；
??完整的Python代碼如下：(接以上代碼)
# -*- coding: utf-8 -*-
from Stack import Stack
# 兩個(gè)數(shù)的運(yùn)算, 除法時(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)化為浮點(diǎn)型或整型數(shù)字
def str2num(s):
if '.' in s:
return float(s)
else:
return int(s)
# 后綴表達(dá)式求值
def evalPostfix(e):
tokens = e.split() # 后綴表達(dá)式轉(zhuǎn)化為列表
s = Stack()
for token in tokens:
if token.isdigit() or '.' in token: # 如果當(dāng)前元素是數(shù)字
s.push(str2num(token))
elif token in '+-*/': # 如果當(dāng)前元素是運(yùn)算符
op2 = s.pop()
op1 = s.pop()
s.push(operate(token, op1, op2)) # 計(jì)算結(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
請(qǐng)務(wù)必注意悍及，我們輸入的中綴表達(dá)式中闽瓢，每個(gè)運(yùn)算符或運(yùn)算符要用空格隔開(kāi)。
參考文獻(xiàn)
- 3.9. Infix, Prefix and Postfix Expressions: http://interactivepython.org/runestone/static/pythonds/BasicDS/InfixPrefixandPostfixExpressions.html
- Python算法實(shí)戰(zhàn)系列之棧: http://python.jobbole.com/87581/
注意：本人現(xiàn)已開(kāi)通微信公眾號(hào)： Python爬蟲(chóng)與算法（微信號(hào)為：easy_web_scrape）心赶， 歡迎大家關(guān)注哦~~
