中綴表達式
9 + (3 - 1)*3 + 8 / 2
后綴表達式
9 3 1 - 3 * + 8 2 / +
簡易計算器，可以通過棧來實現(xiàn)。然而如果直接使用中綴表達式，需要處理括號，而使用后綴表達式則可以規(guī)避這種麻煩。后綴表達式計算起來更加方便，步驟如下：
1.將后綴表達式入棧，數(shù)字直接入棧
2.遇到操作符，將棧頂?shù)膬蓚€元素出棧，
第一個出棧的是操作數(shù)，第二個出棧的是被操作數(shù)，
根據(jù)操作符計算兩個數(shù)的結果，然后將結果再次入棧
3.重復上面的步驟，直到后綴表達式遍歷結束，最后在棧中的元素便是計算結果
例：9 3 1 - 3 * + 8 2 / +
第一步：
后綴表達式的第一個元素是9，數(shù)字直接入棧。
第二步：
后綴表達式的第二個元素3，數(shù)字直接入棧。
第三步：
后綴表達式的第三個元素1，數(shù)字直接入棧。
第四步：
后綴表達式的第四個元素‘-’，將棧頂?shù)膬蓚€元素出棧，
第一個出棧的1作為操作數(shù)，第二個出棧的3作為被操作數(shù)，
而操作符是‘-’，計算結果為：3 - 1 = 2，然后將2入棧。
第五步：
后綴表達式的第五個元素3，數(shù)字直接入棧。
第六步：
后綴表達式的第六個元素‘*’，將棧頂?shù)膬蓚€元素出棧，
第一個出棧的3作為操作數(shù)，第二個出棧的2作為被操作數(shù)，
而操作符是‘-’，計算結果為：2 * 3 = 6，然后將6入棧。
第七步：
后綴表達式的第七個元素‘+’，將棧頂?shù)膬蓚€元素出棧，
第一個出棧的6作為操作數(shù)，第二個出棧的9作為被操作數(shù)，
而操作符是‘-’，計算結果為：9 + 6 = 15，然后將15入棧。
第八步：
后綴表達式的第八個元素8，數(shù)字直接入棧。
第九步：
后綴表達式的第九個元素2，數(shù)字直接入棧。
第十步：
后綴表達式的第十個元素‘/’，將棧頂?shù)膬蓚€元素出棧，
第一個出棧的2作為操作數(shù)，第二個出棧的8作為被操作數(shù)，
而操作符是‘-’，計算結果為：8 / 2 = 4，然后將4入棧。
第十一步：
后綴表達式的第十一個元素‘/’，將棧頂?shù)膬蓚€元素出棧，
第一個出棧的4作為操作數(shù)，第二個出棧的15作為被操作數(shù)，
而操作符是‘-’，計算結果為：15 + 4 = 19，然后將19入棧。
第十二步：
后綴表達式遍歷結束，棧中的元素就是最后的計算結果。
在了解了后綴表達式的計算過程，我們可以通過棧輕松實現(xiàn)該計算過程，那如何將中綴表達式轉化成后綴表達式？
中綴表達式轉化為后綴表達式
規(guī)則：從左到右遍歷中綴表達式的數(shù)字和符號，若是數(shù)字就輸出，即成為后綴表達式的一部分；若是符號，則判斷其與棧頂符號的優(yōu)先級。是右括號或優(yōu)先級低于棧頂符號（乘除優(yōu)先加減）則棧頂元素依次出棧并輸出，并將當前符號進棧，一直到最終輸出后綴表達式為止。
具體實現(xiàn)步驟：中綴表達式轉化為后綴表達式可以通過棧和隊列來實現(xiàn)，
需要一個棧，用來存操作符，需要一個隊列，用來存后綴表達式的結果。
1.遍歷中綴表達式，如果是數(shù)字則直接入后綴表達式隊列
2.如果操作符棧為空，操作符直接入操作符棧
3.如果操作符的優(yōu)先級大于操作符棧頂元素的優(yōu)先級，則直接入棧，
否則棧頂元素出棧，并添加到后綴表達式隊列中，直到棧頂元素小于操作符的優(yōu)先級，然后將該操作符入棧到操作符棧
4.如果操作符是右括號，操作符做出棧操作，且添加到后綴表達式隊列中，
直到左括號出棧，左括號不需添加到后綴表達式隊列中
5.中綴表達式遍歷結束，需將操作符棧的元素依次出棧，并添加到后綴表達式隊列中
例：9 + (3 - 1)*3 + 8 / 2
第一步：
中綴表達式的第一個元素是9，數(shù)字直接入后綴表達式隊列
結果：
中綴表達式隊列：9
操作符棧：null
第二步：
中綴表達式的第二個元素是‘+’，操作符棧為空，符號‘+’直接入棧
結果：
中綴表達式隊列：9
操作符棧：+
第三步：
中綴表達式的第三個元素是‘（’，括號的優(yōu)先級大于操作符棧頂元素，‘（’直接入棧
結果：
中綴表達式隊列：9
操作符棧：+ （
第四步：
中綴表達式的第四個元素是3，數(shù)字直接入后綴表達式隊列
結果：
中綴表達式隊列：9 3
操作符棧：+ （
第五步：
中綴表達式的第五個元素是‘-’，
由于棧頂元素是‘（’操作符，‘（’操作符只有遇到‘）’操作符才會出棧，
故‘-’直接入棧
結果：
中綴表達式隊列：9 3
操作符棧：+ （ -
第六步：
中綴表達式的第六個元素是1，數(shù)字直接入后綴表達式隊列
結果：
中綴表達式隊列：9 3 1
操作符棧：+ （ -
第七步：
中綴表達式的第七個元素是‘）’，遇到右括號，棧頂元素依次出棧，
并入到后綴表達式隊列中，直到‘（’出棧，‘（’出棧后不做處理
結果：
中綴表達式隊列：9 3 1 -
操作符棧：+
第八步：
中綴表達式的第八個元素是‘*’，優(yōu)先級高于操作符棧棧頂元素‘+’的優(yōu)先級，故直接入棧
結果：
中綴表達式隊列：9 3 1 -
操作符棧：+ *
第九步：
中綴表達式的第九個元素是3，數(shù)字直接入后綴表達式隊列
結果：
中綴表達式隊列：9 3 1 - 3
操作符棧：+ *
第十步：
中綴表達式的第十個元素是‘+’，優(yōu)先級不大于操作符棧棧頂元素，
棧頂元素出棧，并入到后綴表達式隊列中，
直到棧頂元素的優(yōu)先級小于該元素的優(yōu)先級，最后該元素入棧到操作符棧
結果：
中綴表達式隊列：9 3 1 - 3 * +
操作符棧：+
第十一步：
中綴表達式的第十一個元素是8，數(shù)字直接入后綴表達式隊列
結果：
中綴表達式隊列：9 3 1 - 3 * + 8
操作符棧：+
第十二步：
中綴表達式的第十二個元素是‘/’，優(yōu)先級高于操作符棧棧頂元素的優(yōu)先級，故直接入棧
結果：
中綴表達式隊列：9 3 1 - 3 * + 8
操作符棧：+ /
第十三步：
中綴表達式的第十三個元素是2，數(shù)字直接入后綴表達式隊列
結果：
中綴表達式隊列：9 3 1 - 3 * + 8 2
操作符棧：+ /
第十四步：
中綴表達式遍歷結束，將操作符棧棧頂元素依次出棧，并入到后綴表達式的隊列中
結果：
中綴表達式隊列：9 3 1 - 3 * + 8 2 / +
操作符棧：null
代碼
class Calculator(object):
def __init__(self):
# 操作符集合
self.operators = ['+', '-', '*', '/', '(', ')']
# 操作符優(yōu)先級
self.priority = {
'+': 1,
'-': 1,
'*': 2,
'/': 2,
'(': 3,
')': 3
}
def generate_postfix_expression(self, expression):
"""
生成后綴表達式
:param expression:
:return:
"""
# 去除表達式中所有空格
expression = expression.replace(' ', '')
# 創(chuàng)建list作為棧，list的append和pop方法剛好和棧的入棧和出棧方法相同
# 操作符棧
operator_stack = list()
# 后綴表達式是從尾部插入數(shù)據(jù)，使用后綴表達式計算結果是從頭開始遍歷，可以理解為先進先出，可以使用隊列實現(xiàn)，
# 這里為了簡便用list代替，不做內(nèi)存釋放處理
expression_stack = list()
for element in expression:
# 如果是數(shù)字則直接入表達式棧
if element in self.operators:
# 如果棧為空，操作符直接入操作符棧，或者為左括號，也直接入操作符棧
if not operator_stack:
operator_stack.append(element)
else:
# 如果目標元素是右括號，操作符棧頂出棧直接遇到左括號，且出棧的操作符除了括號入到表達式隊列中
if element == ')':
for top in operator_stack[::-1]:
if top != '(':
expression_stack.append(top)
operator_stack.pop()
else:
operator_stack.pop()
break
else:
for top in operator_stack[::-1]:
# 如果目標元素大于棧頂元素，則直接入棧，否則棧頂元素出棧，入到表達式隊列中
# 左括號只有遇到右括號才出棧
if self.priority[top] >= self.priority[element] and top != '(':
expression_stack.append(top)
operator_stack.pop()
else:
operator_stack.append(element)
break
# 可能操作符棧所有的元素優(yōu)先級都大于等于目標操作符的優(yōu)先級，這樣的話操作符全部出棧了，
# 而目標操作符需要入棧操作
if not operator_stack:
operator_stack.append(element)
else:
expression_stack.append(element)
# 中綴表達式遍歷結束，操作符棧仍有操作符，將操作符棧中的操作符入到表達式棧中
for i in range(len(operator_stack)):
expression_stack.append(operator_stack.pop())
return expression_stack
def calcaulate(self, expression):
# 生成后綴表達式
expression_result = self.generate_postfix_expression(expression)
# 使用list作為棧來計算
calcalate_stack = list()
# 遍歷后綴表達式
for element in expression_result:
# 如果為數(shù)字直接入棧
# 遇到操作符，將棧頂?shù)膬蓚€元素出棧
if element not in self.operators:
calcalate_stack.append(element)
else:
# 操作數(shù)
number1 = calcalate_stack.pop()
# 被操作數(shù)
number2 = calcalate_stack.pop()
# 結果 = 被操作數(shù) 操作符 操作數(shù) （例：2 - 1）
result = self.operate(number1, number2, element)
# 計算結果入棧
calcalate_stack.append(result)
return calcalate_stack[0]
def operate(self, number1, number2, operator):
"""
計算結果
:param number1: 操作數(shù)
:param number2: 被操作數(shù)
:param operator: 操作符
:return:
"""
number1 = int(number1)
number2 = int(number2)
if operator == '+':
return number2 + number1
if operator == '-':
return number2 - number1
if operator == '*':
return number2 * number1
if operator == '/':
return number2 / number1
if __name__ == '__main__':
c = Calculator()
expression = '9 + (3 - 1)*3 + 8 / 2'
expression_result = c.calcaulate(expression)
print(expression_result)
代碼還有許多小問題，還需要優(yōu)化，比如時間復雜度還要降低，中綴表達式?jīng)]法正確拆分，數(shù)字是十位以上的就會出錯了，十位個位等會被拆成單個字符。
