中綴表達(dá)式

9 + (3 - 1)*3 + 8 / 2

后綴表達(dá)式

9 3 1 - 3 * + 8 2 / +

簡易計算器晚凿，可以通過棧來實現(xiàn)。然而如果直接使用中綴表達(dá)式瘦馍，需要處理括號歼秽，而使用后綴表達(dá)式則可以規(guī)避這種麻煩。后綴表達(dá)式計算起來更加方便情组，步驟如下：

1.將后綴表達(dá)式入棧燥筷，數(shù)字直接入棧

2.遇到操作符，將棧頂?shù)膬蓚€元素出棧呻惕，
第一個出棧的是操作數(shù)荆责，第二個出棧的是被操作數(shù)，
根據(jù)操作符計算兩個數(shù)的結(jié)果亚脆，然后將結(jié)果再次入棧

3.重復(fù)上面的步驟做院，直到后綴表達(dá)式遍歷結(jié)束，最后在棧中的元素便是計算結(jié)果

例：9 3 1 - 3 * + 8 2 / +

第一步：
  后綴表達(dá)式的第一個元素是9濒持，數(shù)字直接入棧键耕。
第二步：
  后綴表達(dá)式的第二個元素3，數(shù)字直接入棧柑营。
第三步：
  后綴表達(dá)式的第三個元素1屈雄，數(shù)字直接入棧。
第四步：
  后綴表達(dá)式的第四個元素‘-’官套，將棧頂?shù)膬蓚€元素出棧酒奶，
  第一個出棧的1作為操作數(shù)，第二個出棧的3作為被操作數(shù)奶赔，
  而操作符是‘-’惋嚎，計算結(jié)果為：3 - 1 = 2，然后將2入棧站刑。
第五步：
  后綴表達(dá)式的第五個元素3另伍，數(shù)字直接入棧。
第六步：
  后綴表達(dá)式的第六個元素‘*’绞旅，將棧頂?shù)膬蓚€元素出棧摆尝，
  第一個出棧的3作為操作數(shù)温艇，第二個出棧的2作為被操作數(shù)，
  而操作符是‘-’堕汞，計算結(jié)果為：2 * 3 = 6勺爱，然后將6入棧。
第七步：
  后綴表達(dá)式的第七個元素‘+’臼朗，將棧頂?shù)膬蓚€元素出棧邻寿，
  第一個出棧的6作為操作數(shù)，第二個出棧的9作為被操作數(shù)视哑，
  而操作符是‘-’绣否，計算結(jié)果為：9 + 6 = 15挡毅，然后將15入棧。
第八步：
   后綴表達(dá)式的第八個元素8段磨，數(shù)字直接入棧耗绿。
第九步：
   后綴表達(dá)式的第九個元素2，數(shù)字直接入棧债蜜。
第十步：
  后綴表達(dá)式的第十個元素‘/’究反，將棧頂?shù)膬蓚€元素出棧，
  第一個出棧的2作為操作數(shù)狼速，第二個出棧的8作為被操作數(shù)卦停，
  而操作符是‘-’，計算結(jié)果為：8 / 2 = 4僵芹，然后將4入棧专执。
第十一步：
  后綴表達(dá)式的第十一個元素‘/’郁油，將棧頂?shù)膬蓚€元素出棧攀痊，
  第一個出棧的4作為操作數(shù)苟径，第二個出棧的15作為被操作數(shù)躬审，
  而操作符是‘-’，計算結(jié)果為：15 + 4 = 19遭殉，然后將19入棧博助。
第十二步：
  后綴表達(dá)式遍歷結(jié)束，棧中的元素就是最后的計算結(jié)果蛔糯。

在了解了后綴表達(dá)式的計算過程窖式，我們可以通過棧輕松實現(xiàn)該計算過程，那如何將中綴表達(dá)式轉(zhuǎn)化成后綴表達(dá)式淮逻？

中綴表達(dá)式轉(zhuǎn)化為后綴表達(dá)式

規(guī)則：從左到右遍歷中綴表達(dá)式的數(shù)字和符號蜒灰，若是數(shù)字就輸出，即成為后綴表達(dá)式的一部分凸椿；若是符號翅溺，則判斷其與棧頂符號的優(yōu)先級。是右括號或優(yōu)先級低于棧頂符號（乘除優(yōu)先加減）則棧頂元素依次出棧并輸出优幸，并將當(dāng)前符號進(jìn)棧网杆，一直到最終輸出后綴表達(dá)式為止。

具體實現(xiàn)步驟：中綴表達(dá)式轉(zhuǎn)化為后綴表達(dá)式可以通過棧和隊列來實現(xiàn)队秩，
需要一個棧昼浦，用來存操作符，需要一個隊列鸟蟹，用來存后綴表達(dá)式的結(jié)果使兔。

1.遍歷中綴表達(dá)式，如果是數(shù)字則直接入后綴表達(dá)式隊列

2.如果操作符棧為空锦针，操作符直接入操作符棧

3.如果操作符的優(yōu)先級大于操作符棧頂元素的優(yōu)先級置蜀，則直接入棧，
否則棧頂元素出棧馋吗，并添加到后綴表達(dá)式隊列中秋秤，直到棧頂元素小于操作符的優(yōu)先級，然后將該操作符入棧到操作符棧

4.如果操作符是右括號绍哎，操作符做出棧操作鞋真，且添加到后綴表達(dá)式隊列中，
直到左括號出棧海诲，左括號不需添加到后綴表達(dá)式隊列中

5.中綴表達(dá)式遍歷結(jié)束檩互，需將操作符棧的元素依次出棧，并添加到后綴表達(dá)式隊列中

例：9 + (3 - 1)*3 + 8 / 2

第一步：
  中綴表達(dá)式的第一個元素是9蚯斯，數(shù)字直接入后綴表達(dá)式隊列
  結(jié)果：
    中綴表達(dá)式隊列：9
    操作符棧：null
第二步：
  中綴表達(dá)式的第二個元素是‘+’，操作符棧為空拍嵌，符號‘+’直接入棧
  結(jié)果：
    中綴表達(dá)式隊列：9
    操作符棧：+
第三步：
  中綴表達(dá)式的第三個元素是‘（’，括號的優(yōu)先級大于操作符棧頂元素，‘（’直接入棧
  結(jié)果：
    中綴表達(dá)式隊列：9
    操作符棧：+ （
第四步：
  中綴表達(dá)式的第四個元素是3打洼，數(shù)字直接入后綴表達(dá)式隊列
  結(jié)果：
    中綴表達(dá)式隊列：9 3
    操作符棧：+ （
第五步：
  中綴表達(dá)式的第五個元素是‘-’，
  由于棧頂元素是‘（’操作符炫惩，‘（’操作符只有遇到‘）’操作符才會出棧阿浓，
  故‘-’直接入棧
  結(jié)果：
    中綴表達(dá)式隊列：9 3
    操作符棧：+ （ -
第六步：
  中綴表達(dá)式的第六個元素是1，數(shù)字直接入后綴表達(dá)式隊列
  結(jié)果：
    中綴表達(dá)式隊列：9 3 1
    操作符棧：+ （ -
第七步：
  中綴表達(dá)式的第七個元素是‘）’筋蓖，遇到右括號退敦，棧頂元素依次出棧，
  并入到后綴表達(dá)式隊列中瓮下，直到‘（’出棧钝域，‘（’出棧后不做處理
  結(jié)果：
    中綴表達(dá)式隊列：9 3 1 -
    操作符棧：+
第八步：
  中綴表達(dá)式的第八個元素是‘*’，優(yōu)先級高于操作符棧棧頂元素‘+’的優(yōu)先級路呜，故直接入棧
  結(jié)果：
    中綴表達(dá)式隊列：9 3 1 -
    操作符棧：+ *
第九步：
  中綴表達(dá)式的第九個元素是3织咧，數(shù)字直接入后綴表達(dá)式隊列
  結(jié)果：
    中綴表達(dá)式隊列：9 3 1 - 3
    操作符棧：+ *
第十步：
  中綴表達(dá)式的第十個元素是‘+’，優(yōu)先級不大于操作符棧棧頂元素巡社，
  棧頂元素出棧手趣，并入到后綴表達(dá)式隊列中肥荔，
  直到棧頂元素的優(yōu)先級小于該元素的優(yōu)先級燕耿，最后該元素入棧到操作符棧
  結(jié)果：
    中綴表達(dá)式隊列：9 3 1 - 3 * +
    操作符棧：+ 
第十一步：
  中綴表達(dá)式的第十一個元素是8姜胖，數(shù)字直接入后綴表達(dá)式隊列
  結(jié)果：
    中綴表達(dá)式隊列：9 3 1 - 3 * + 8
    操作符棧：+ 
第十二步：
  中綴表達(dá)式的第十二個元素是‘/’，優(yōu)先級高于操作符棧棧頂元素的優(yōu)先級蚜锨，故直接入棧
  結(jié)果：
    中綴表達(dá)式隊列：9 3 1 - 3 * + 8
    操作符棧：+ /
第十三步：
  中綴表達(dá)式的第十三個元素是2慢蜓，數(shù)字直接入后綴表達(dá)式隊列
  結(jié)果：
    中綴表達(dá)式隊列：9 3 1 - 3 * + 8 2
    操作符棧：+ /
第十四步：
  中綴表達(dá)式遍歷結(jié)束，將操作符棧棧頂元素依次出棧氛悬，并入到后綴表達(dá)式的隊列中
  結(jié)果：
    中綴表達(dá)式隊列：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):
        """
        生成后綴表達(dá)式
        :param expression:
        :return:
        """

        # 去除表達(dá)式中所有空格
        expression = expression.replace(' ', '')

        # 創(chuàng)建list作為棧如捅，list的append和pop方法剛好和棧的入棧和出棧方法相同
        # 操作符棧
        operator_stack = list()
        # 后綴表達(dá)式是從尾部插入數(shù)據(jù)调煎，使用后綴表達(dá)式計算結(jié)果是從頭開始遍歷，可以理解為先進(jìn)先出烈涮，可以使用隊列實現(xiàn)窖剑，
        # 這里為了簡便用list代替，不做內(nèi)存釋放處理
        expression_stack = list()

        for element in expression:
            # 如果是數(shù)字則直接入表達(dá)式棧
            if element in self.operators:

                # 如果棧為空讶舰，操作符直接入操作符棧需了，或者為左括號，也直接入操作符棧
                if not operator_stack:
                    operator_stack.append(element)
                else:
                    # 如果目標(biāo)元素是右括號鹅颊，操作符棧頂出棧直接遇到左括號墓造，且出棧的操作符除了括號入到表達(dá)式隊列中
                    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]:
                            # 如果目標(biāo)元素大于棧頂元素锚烦，則直接入棧涮俄，否則棧頂元素出棧尸闸，入到表達(dá)式隊列中
                            # 左括號只有遇到右括號才出棧
                            if self.priority[top] >= self.priority[element] and top != '(':
                                expression_stack.append(top)
                                operator_stack.pop()
                            else:
                                operator_stack.append(element)
                                break

                        # 可能操作符棧所有的元素優(yōu)先級都大于等于目標(biāo)操作符的優(yōu)先級，這樣的話操作符全部出棧了苞尝，
                        # 而目標(biāo)操作符需要入棧操作
                        if not operator_stack:
                            operator_stack.append(element)

            else:
                expression_stack.append(element)

        # 中綴表達(dá)式遍歷結(jié)束茧痕，操作符棧仍有操作符踪旷，將操作符棧中的操作符入到表達(dá)式棧中
        for i in range(len(operator_stack)):
            expression_stack.append(operator_stack.pop())

        return expression_stack

    def calcaulate(self, expression):
        # 生成后綴表達(dá)式
        expression_result = self.generate_postfix_expression(expression)
        # 使用list作為棧來計算
        calcalate_stack = list()

        # 遍歷后綴表達(dá)式
        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()
                # 結(jié)果 =  被操作數(shù) 操作符 操作數(shù) （例：2 - 1）
                result = self.operate(number1, number2, element)
                # 計算結(jié)果入棧
                calcalate_stack.append(result)

        return calcalate_stack[0]

    def operate(self, number1, number2, operator):
        """
        計算結(jié)果
        :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)化餐抢，比如時間復(fù)雜度還要降低，中綴表達(dá)式?jīng)]法正確拆分旷痕，數(shù)字是十位以上的就會出錯了，十位個位等會被拆成單個字符售碳。