參考：http://interactivepython.org/runestone/static/pythonds/BasicDS/InfixPrefixandPostfixExpressions.html

本文主要探討簡單的數(shù)學(xué)算術(shù)表達(dá)式求值算法的原理和實(shí)現(xiàn)。

1. 約束

本文只是探討簡單的算術(shù)表達(dá)式的求值算法，為了將主要精力放在算法思想的探討和實(shí)現(xiàn)上，避免陷入對其他不是直接相關(guān)的細(xì)節(jié)的過多思考，所以提前做如下約束：

• 本文所討論的算術(shù)表達(dá)式字符串中每個運(yùn)算數(shù)、運(yùn)算符之間都有空白符分隔開（方便后面用python字符串的split函數(shù)分割處理成列表）。

• 算術(shù)表達(dá)式中參與運(yùn)算的運(yùn)算數(shù)都為1位整數(shù)。

• 表達(dá)式中的運(yùn)算符都為二元運(yùn)算符（即一個運(yùn)算符需要兩個運(yùn)算數(shù)），不會出現(xiàn)其他元的運(yùn)算符（如一元運(yùn)算符負(fù)號：-）。

• 運(yùn)算的中間結(jié)果和最終結(jié)果也都為整數(shù)，且都不會產(chǎn)生異常（如除數(shù)為0等）。

• 暫且只支持如下幾種運(yùn)算符：+ - \* / ( )

2. 中綴表達(dá)式與后綴表達(dá)式

算術(shù)表達(dá)式，根據(jù)運(yùn)算符和運(yùn)算數(shù)的相對位置不同，可以分為三種：前綴表達(dá)式（prefix）、中綴表達(dá)式（infix）和后綴表達(dá)式（postfix），其中后綴表達(dá)式又稱為逆波蘭式，在本文中只討論中綴和后綴表達(dá)式。

• 中綴表達(dá)式：就是我們平時常見的算術(shù)表達(dá)式，如1 + 2 \* 3，( 1 + 2 ) \* 3這樣的運(yùn)算符在運(yùn)算數(shù)中間的表達(dá)式，中綴表達(dá)式的特點(diǎn)是符合人的理解習(xí)慣，并且可以加小括號改變運(yùn)算的先后順序。但缺點(diǎn)是如果用編程來求值的話比較困難。

• 后綴表達(dá)式：是將中綴表達(dá)式進(jìn)行變換后得到的表達(dá)式，如1 2 3 \* +，1 2 + 3 \*這樣的運(yùn)算符在運(yùn)算數(shù)后面的表達(dá)式，后綴表達(dá)式的特點(diǎn)是雖然不符合人的理解習(xí)慣，但編程來求值卻很方便，且沒有括號的煩惱。

后綴表達(dá)式因為不需要括號，所以編程求值起來比較方便，下面將先從如何對后綴表達(dá)式求值講起。

3. 后綴表達(dá)式求值

1. 核心算法：

• 創(chuàng)建一個空棧，名為numstack，用于存放運(yùn)算數(shù)。

• 用python字符串的split函數(shù)將輸入的后綴表達(dá)式（postfix）分割為列表，將該列表記為input。

• 從左到右遍歷input的每一個元素token：

• 若token為運(yùn)算數(shù)，將其轉(zhuǎn)換為整數(shù)并push進(jìn)numstack；

• 若token為運(yùn)算符，則將numstack pop兩次，將第一次pop得到的數(shù)作為運(yùn)算符的右操作數(shù)，將第二次pop得到的數(shù)作為運(yùn)算符的左操作數(shù)，然后求出運(yùn)算結(jié)果，并將結(jié)果push進(jìn)numstack；

• 遍歷完input后，numstack僅剩下一個元素，這就是表達(dá)式的最終求值結(jié)果，pop出這個元素，算法結(jié)束。

2. 舉例

比如求4 5 6 \* +這樣一個后綴表達(dá)式的值（注：其前綴表達(dá)式為：4 + 5 \* 6，值為34），按照上述算法，過程如下：

所以最終的表達(dá)式求值結(jié)果為：34

3. 代碼實(shí)現(xiàn)

# 準(zhǔn)備工作：創(chuàng)建一個棧類
class Stack():
    def __init__(self):
        self.data = []
    
    def __str__(self):
        return str(self.data)
    
    __repr__ = __str__
    
    def pop(self):
        if len(self.data) != 0:
            return self.data.pop()
        return None
    
    def push(self,e):
        self.data.append(e)
        
    def clear(self):
        del self.data[:]
    
    # 獲取棧頂元素，但不彈出此元素
    def peek(self):
        if len(self.data) != 0:
            return self.data[-1]
        return None
    
    # 判斷棧是否為空
    def empty(self):
        return len(self.data) == 0
    
# 求值函數(shù)
def get_value(num1,op,num2):
    if op == '+':
        return num1 + num2
    elif op == '-':
        return num1 - num2
    elif op == '*':
        return num1 * num2
    elif op == '/':
        return num1 / num2
    else:
        raise ValueError('invalid operator!')
    
# 后綴表達(dá)式求值函數(shù)
def get_postfix_value(postfix):
    # 1. 創(chuàng)建一個運(yùn)算數(shù)棧
    numstack = Stack()
    
    # 2. 分割postfix
    inPut = postfix.strip().split()  # 注：因為'input'是內(nèi)置函數(shù)名，所以用'inPut';strip函數(shù)的作用是去掉字符串的開始和結(jié)尾的空白字符
    
    # 3. 遍歷inPut
    for token in inPut:
        # 3.1 如果token為運(yùn)算數(shù)
        if token.isdigit():
            numstack.push(int(token))
        # 3.2 如果token是運(yùn)算符
        else:
            num2 = numstack.pop()
            num1 = numstack.pop()
            numstack.push(get_value(num1,token,num2))
    
    # 4. 輸出numstack的最后一個元素
    return numstack.pop()
            
# 后綴表達(dá)式
# 注：對應(yīng)的中綴表達(dá)式為：(1+2)*(3+4)，運(yùn)算結(jié)果為：21
postfix = '1 2 + 3 4 + *'

print '【Output】'
print get_postfix_value(postfix)

【Output】
21

4. 中綴表達(dá)式轉(zhuǎn)后綴表達(dá)式

1. 核心算法

• 創(chuàng)建一個空棧opstack，用于存放運(yùn)算符，創(chuàng)建一個空列表output用于保存輸出結(jié)果。

• 使用python字符串的split函數(shù)將輸入的中綴表達(dá)式（infix）字符串分割成列表并存入input列表中。

• 從左到右遍歷input列表的每個元素token：

• 若token是運(yùn)算數(shù)，直接append到output中；

• 若token是運(yùn)算符，先判斷它與opstack棧頂元素的運(yùn)算優(yōu)先級（注：小括號的優(yōu)先級約定為最低），若：token的優(yōu)先級小于等于棧頂元素優(yōu)先級，則先從opstack中pop出棧頂元素并append到output，再將token push進(jìn)opstack；否則直接將token push進(jìn)opstack；

• 若token是左括號，直接將其push進(jìn)opstack；

• 若token是右括號，依次pop出opstack中的元素并依次append到output，直到遇到左括號，將左括號繼續(xù)pop出（但不append到output）。

• 當(dāng)遍歷完成input，將opstack中所有的剩余元素pop出并依次append到output。

• 將output轉(zhuǎn)換為字符串，即為最終求得的后綴表達(dá)式。

2. 舉例

比如將(A+B)\*C這樣一個中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式（其中A,B,C表示整數(shù)），按照上述算法，轉(zhuǎn)換過程如下：

所以最終求得的后綴表達(dá)式為：A B + C *

3. 代碼實(shí)現(xiàn)

# 準(zhǔn)備工作：創(chuàng)建一個棧類
class Stack():
    def __init__(self):
        self.data = []
    
    def __str__(self):
        return str(self.data)
    
    __repr__ = __str__
    
    def pop(self):
        if len(self.data) != 0:
            return self.data.pop()
        return None
    
    def push(self,e):
        self.data.append(e)
        
    def clear(self):
        del self.data[:]
    
    # 獲取棧頂元素，但不彈出此元素
    def peek(self):
        if len(self.data) != 0:
            return self.data[-1]
        return None
    
    # 判斷棧是否為空
    def empty(self):
        return len(self.data) == 0
    
# 求值函數(shù)
def get_value(num1,op,num2):
    if op == '+':
        return num1 + num2
    elif op == '-':
        return num1 - num2
    elif op == '*':
        return num1 * num2
    elif op == '/':
        return num1 / num2
    else:
        raise ValueError('invalid operator!')
        
# 將中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式的函數(shù)
def infix2postfix(infix):
    # 1. 創(chuàng)建運(yùn)算符棧和輸出結(jié)果列表
    opstack = Stack()
    output = []
    
    # 準(zhǔn)備一個運(yùn)算符優(yōu)先級字典，其中左小括號的優(yōu)先級最低
    priority = {'(' : 0,'+' : 3,'-' : 3,'*' : 4,'/' : 4}
    
    # 2. 分割infix
    inPut = infix.strip().split()
    
    # 3. 遍歷inPut
    for token in inPut:
        # 3.1 若token是運(yùn)算數(shù)
        if token.isdigit():
            output.append(token)
        # 3.2 若token是運(yùn)算符
        elif token in ['+','-','*','/']:
            if not opstack.empty() and priority[token] <= priority[opstack.peek()]:
                output.append(opstack.pop())
            opstack.push(token)
        # 3.3 若token是左括號
        elif token == '(':
            opstack.push(token)
        # 3.4 若token是右括號
        elif token == ')':
            while opstack.peek() != '(':
                output.append(opstack.pop())
            # 彈出左括號
            opstack.pop()
        else:
            raise ValueError('invalid token:{0}'.format(token))
    # 4. 將opstack中剩余元素append到output
    while not opstack.empty():
        output.append(opstack.pop())
        
    # 5. 將output轉(zhuǎn)換為字符串（每個元素用空格隔開）并輸出
    return ' '.join(output)

infix = '( 1 + 2 ) * ( 3 + 4 )'

print '【Output】'
print infix2postfix(infix)

【Output】
1 2 + 3 4 + *

5. 整理：中綴表達(dá)式求值

1. 核心算法

經(jīng)過前面的討論，那么現(xiàn)在求中綴表達(dá)式的值就很簡單了，分為兩步：第1步，將中綴表達(dá)式轉(zhuǎn)換為對應(yīng)的后綴表達(dá)式；第2步，對后綴表達(dá)式求值。

2. 完整代碼實(shí)現(xiàn)

# 準(zhǔn)備工作：創(chuàng)建一個棧類
class Stack():
    def __init__(self):
        self.data = []
    
    def __str__(self):
        return str(self.data)
    
    __repr__ = __str__
    
    def pop(self):
        if len(self.data) != 0:
            return self.data.pop()
        return None
    
    def push(self,e):
        self.data.append(e)
        
    def clear(self):
        del self.data[:]
    
    # 獲取棧頂元素，但不彈出此元素
    def peek(self):
        if len(self.data) != 0:
            return self.data[-1]
        return None
    
    # 判斷棧是否為空
    def empty(self):
        return len(self.data) == 0
    
# 求值函數(shù)
def get_value(num1,op,num2):
    if op == '+':
        return num1 + num2
    elif op == '-':
        return num1 - num2
    elif op == '*':
        return num1 * num2
    elif op == '/':
        return num1 / num2
    else:
        raise ValueError('invalid operator!')

# 將中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式的函數(shù)
def infix2postfix(infix):
    # 1. 創(chuàng)建運(yùn)算符棧和輸出結(jié)果列表
    opstack = Stack()
    output = []
    
    # 準(zhǔn)備一個運(yùn)算符優(yōu)先級字典，其中左小括號的優(yōu)先級最低
    priority = {'(' : 0,'+' : 3,'-' : 3,'*' : 4,'/' : 4}
    
    # 2. 分割infix
    inPut = infix.strip().split()
    
    # 3. 遍歷inPut
    for token in inPut:
        # 3.1 若token是運(yùn)算數(shù)
        if token.isdigit():
            output.append(token)
        # 3.2 若token是運(yùn)算符
        elif token in ['+','-','*','/']:
            if not opstack.empty() and priority[token] <= priority[opstack.peek()]:
                output.append(opstack.pop())
            opstack.push(token)
        # 3.3 若token是左括號
        elif token == '(':
            opstack.push(token)
        # 3.4 若token是右括號
        elif token == ')':
            while opstack.peek() != '(':
                output.append(opstack.pop())
            # 彈出左括號
            opstack.pop()
        else:
            raise ValueError('invalid token:{0}'.format(token))
    # 4. 將opstack中剩余元素append到output
    while not opstack.empty():
        output.append(opstack.pop())
        
    # 5. 將output轉(zhuǎn)換為字符串（每個元素用空格隔開）并輸出
    return ' '.join(output)
    
# 后綴表達(dá)式求值函數(shù)
def get_postfix_value(postfix):
    # 1. 創(chuàng)建一個運(yùn)算數(shù)棧
    numstack = Stack()
    
    # 2. 分割postfix
    inPut = postfix.strip().split()  # 注：因為'input'是內(nèi)置函數(shù)名，所以用'inPut';strip函數(shù)的作用是去掉字符串的開始和結(jié)尾的空白字符
    
    # 3. 遍歷inPut
    for token in inPut:
        # 3.1 如果token為運(yùn)算數(shù)
        if token.isdigit():
            numstack.push(int(token))
        # 3.2 如果token是運(yùn)算符
        else:
            num2 = numstack.pop()
            num1 = numstack.pop()
            numstack.push(get_value(num1,token,num2))
    
    # 4. 輸出numstack的最后一個元素
    return numstack.pop()

# 中綴表達(dá)式求值函數(shù)
def get_infix_value(infix):
    postfix = infix2postfix(infix)
    return get_postfix_value(postfix)

infix = '( 1 + 2 ) * ( 3 + 4 )'

print '【Output】'
print get_infix_value(infix)

【Output】
21