1.名詞解釋

? ? ? ? 1.1?中綴表達式

? ? ? ? ? ? ? ? ? ? ? ? 普通表達式,即操作符位于操作數的中間。如''2+3*5'',''(2+3)*5''。這種表達式的特點是根據運算符的優先級不同，計算順序不同。可以通過添加括號來改變計算的順序，這種表達式人類理解起來沒什么問題，但計算機識別起來就有點困難。

? ? ? ? 1.2 全括號表達式

? ? ? ? ? ? ? ? ? ? ? ? 為了方便計算機識別表達式，可以將中綴通過添加括號的方法轉化為全括號表達式，即每一次運算都添加一對括號來保證計算的優先級。如"(2+(3*5))","((2+3)*5)",全括號表達式解決了計算機識別的問題。但是又出現了新的問題，括號太多，增加了處理負擔。顯得不夠優雅，發現了問題，自然就會誕生解決問題的牛人，1929年波蘭的邏輯學家盧卡西維茲(Jan Lucasiewicz)提出了將運算符放在運算項前面的邏輯表達式，又稱“波蘭表達式”。優雅地地解決了這個問題

? ? ? ? 1.3?前綴表達式(波蘭式)

? ? ? ? ? ? ? ? ? ? ? ? 波蘭式表達式，就是將運算符放在兩個運算數的前面的表達式，如"+ 2 * 3 5","*+ 2 3 5"。可以發現波蘭式完全消滅了括號，而且還能保證運算順序和對應的中綴表達式相同。這里也解釋一下波蘭式的運算規則，（后續將利用這個規則進行波蘭式的求值。）如果一個操作符的后面是兩個操作數，則直接運算，如果是一個操作數+一個操作符，說明要先運算第二個操作符。再將結果與第一個數進行運算得到結果 。

eg："+ 2 * 3 5"

第一個操作符 “+” ，接下來是操作數 2，

? ? ? ? 接下來又是操作符’* ，說明要先運算”*“

? ? ? ? ? ? ? ? 接下來是兩個操作數 3 和 5 ，作乘法的結果是15

? ? ? ? 將結果15作為’+“的第二個操作數
得到2+15 =17

? ? ? ? 1.4?后綴表達式(逆波蘭式)

? ? ? ? ? ? ? ? ? ? ? ? 所謂逆波蘭式，就是將運算符放在兩個運算數的后面的表達式，如"2 3 5 * +","2 3 +5*"。

2.如何把中綴表達式轉化為波蘭式

????????2.1 先轉化為全括號表達式

???????????????如："2+3*5''

????????????????得到全括號表達式："（2+（3*5））''

????????????????觀察全括號表達式,得到轉化的方法：將運算符替換掉對應的左括號，同時刪除右括號

? ? ? ? ?2.2 利用棧的后進先出的特性來轉化

2.2.1 先用python來定義一個棧的抽象數據類型

代碼如下：

class Stack:def __init__(self):self.items = []def push(self,item):self.items.append(item)def pop(self):return self.items.pop()def isEmpty(self):return self.items == []def size(self):return len(self.items)def peek(self):return self.items[-1]def __str__(self):return '{}←'.format(self.items)

? ? ?2.2.2接下來定義一個函數來處理輸入數據。將中綴表達式的字符串轉成一個列表，方便后續處理

def inputProcess(inputString):'''將輸入的字符串轉化為包含操作數和操作符的列表'''resList = []tmp = '' # 用于保存多位的數字時的中間結果for ele in inputString:if ele.isdigit() or ele == '.': # 能處理小數點的情況tmp += str(ele)else:if tmp != '':resList.append(tmp)tmp = ''resList.append(ele)if tmp != '':resList.append(tmp)return resList

? ? 這里有一個問題，將一個字符串變為列表，可能有更加簡單的方法，如? ? ? ? ? ? ?

# 字符串轉列表 lis = list('(1+2+3)*9') print(lis) >>>['(', '1', '+', '2', '+', '3', ')', '*', '9'] # 結果正確 # 但是不能處理如下情況 lis1 = list('(10+28+3)*9') print(lis1) >>>['(', '1', '0', '+', '2', '8', '+', '3', ')', '*', '9'] # 10,28 被分割成了兩個元素

? ? ?2.2.3? ? 編寫轉化的主函數

def inToPreExp(epxString):expList = inputProcess(epxString)s = Stack()optPriorityDict = {')':0,'+':1,'-':1,'*':2,'/':2} # 操作符優先級字典res = [] # 保存結果for ele in expList[::-1]: # 逆序掃描列表if ele.isdigit(): # 1數字直接添加進結果字符串res.insert(0,ele) # 為保證數字順序,所有從左邊插入進結果列表elif ele == ')': # 2.右括號壓棧s.push(ele)elif ele =='(': # 3.左括號,連續出棧直到右括號,并追加到結果字符串top = s.pop()while top != ')':res.insert(0,top)top = s.pop()elif ele in '+-*/': # 4 操作符和棧頂元素比較優先級while (not s.isEmpty() and \optPriorityDict[s.peek()] >= optPriorityDict[ele]): # 當前棧頂元素的優先級大于等于掃描到的運算符res.insert(0, s.pop()) # 出棧并插入結果列表s.push(ele) # 入棧while not s.isEmpty():res.insert(0,s.pop())return res

算法：

1.創建優先級字典,初始化一個空棧,用于保存操作符,一個空列表用于保存結果,

逆序掃描列表

2.如果遇到數字，直接插入進結果列表的最左邊

3.如果是“）”：

? ? ? ? 入棧

4.如果遇到"(":

? ? ? ? 持續出棧,并插入到結果列表,直到遇到")"

5.如果是"+-*/":

? ? ? ? 如果棧頂元素的優先級比當前操作符大,則連續出棧

? ? ? ? 當前操作符入棧

6.掃描完成以后,如果棧不為空,則一次出棧.插入到結果列表

以下是一些測試

print(inToPreExp('(2+3)*5')) print(inToPreExp('2+3*5')) print(inToPreExp('(12-5)*(23+8)')) print(inToPreExp('2+3*7/20-(2+3)'))結果: ['*', '+', '2', '3', '5'] ['+', '2', '*', '3', '5'] ['*', '-', '12', '5', '+', '23', '8'] ['+', '2', '-', '*', '3', '/', '7', '20', '+', '2', '3']

3.波蘭式求值

直接上代碼:

def evalPreExp(postExpList):# 前綴表達式求值s = Stack()for ele in postExpList[::-1]:if ele.isdigit():s.push(ele)else:op1 = s.pop()op2 = s.pop()res = toMath(ele,int(op1),int(op2))s.push(res)return s.pop()def toMath(op,op1,op2):# 根據不同的運算符做四則運算if op == '+':return op1 + op2elif op == '-':return op1 - op2elif op == '*':return op1 * op2elif op == '/':return op1 / op2print(evalPreExp(['*', '-', '12', '5', '+', '23', '8'])) # >>> 結果:217

總結:

波蘭式和逆波蘭式因其優雅簡潔而聞名

大部分教程都是中綴到后綴的轉化

嘗試了一下中綴到前綴的轉化

需要注意的幾個重點:

1.優先級字典中設置右括號為最低優先級,? ?中綴轉后綴時,左括號的優先級最低

2.掃描列表的時候?逆序

3.因為時逆序掃描,為保證操作數的位置不變,所以插入到結果列表的時候使用insert(0,ele)的方法從左邊插入

參考書籍:

Bradley N. Miller, David L. Ranum <<Introduction to Data Structures and Algorithms in Python>>

---

35歲開始學Python ,?也不知道為了啥 ?

總結

以上是生活随笔為你收集整理的中缀表达式To前缀表达式 (python实现)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。