淺析前綴，后綴，中綴表達式轉化求值問題
算法，一門既不容易入門，也不容易精通的學問。
上次介紹如何利用棧實現中綴表達式求值，如果我是出題官，當然要考前綴，后綴，中綴表達式相互轉換，然后就變成了利用棧實現前綴和后綴表達式求值。
前綴，后綴，中綴表達式相互轉換及其運算，可以說是計算機考研的一個重點。
首先看下面所示表格：
- 注意：前序表達式和后序表達式是沒有擴號
這篇文章有對應的圖解：https://mp.weixin.qq.com/s/NRbFXZAXEUeXhKKYY7CReg
中綴表達式轉前綴表達式求值
中綴表達式轉前綴表達式的規則：
- 1、反轉輸入字符串，如“2*3/(2-1)+3*(4-1)” 反轉后為“ )1-4(*3+)1-2(/3*2”，
- 2、從字符串中取出下一個字符
- 2.1.如果是操作數，直接輸出
- 2.2.如果是“)”，壓入棧中
- 2.3.如果是運算符但不是“(”，“)”,則不斷循環進行以下處理
- 2.3.1.如果棧為空，則此運算符進棧，結束此步驟
- 2.3.2.如果棧頂是“)”,則此運算符進棧，結束此步驟
- 2.3.2.如果此運算符與棧頂優先級相同或者更高，此運算符進棧，結束此步驟
- 2.3.4.否則，運算符連續出棧，直到滿足上述三個條件之一，然后此運算符進棧
- 2.4、如果是“(”，則運算符連續出棧，直到遇見“)”為止,將“)”出棧且丟棄之
- 3、如果還有更多的字符串，則轉到第2步
- 4、不在有未處理的字符串了，輸出棧中剩余元素
- 5、再次反轉字符串得到最終結果
經過上面的步驟，得到的輸出既是轉換得到的前綴表達式。
前綴表達式的計算方法：對前綴表達式從后向前掃描，設定一個操作數棧，如果是操作數，則將其直接入棧，如果是操作符，則從棧中彈出操作符對應的操作數進行運算，并將計算結果壓棧。直至從右到左掃描完畢整個前綴表達式，這時操作數棧中應該只有一個元素，該元素的值則為前綴表達式的計算結果。
上面的過程使用數據結構棧來實現，具體代碼如下
- '''
- @Author：Runsen
- @WeChat：RunsenLiu
- @微信公眾號：Python之王
- @CSDN：https://blog.csdn.net/weixin_44510615
- @Github：https://github.com/MaoliRUNsen
- @Date：2020/12/17
- '''
- import re
- class Stack():
- def __init__(self):
- self.items = []
- def push(self, item):
- return self.items.append(item)
- def pop(self):
- return self.items.pop()
- def size(self):
- return len(self.items)
- def peek(self):
- return self.items[len(self.items) - 1]
- def display(self):
- print(self.items)
- def infix_to_prefix(s):
- prec = {
- '*': 3,
- '/': 3,
- '+': 2,
- '-': 2,
- '(': 4,
- ')': 1
- }
- a = re.findall('[1-9]\d*|[\+\-\*\/\(\)]', input('請輸入中綴表達式：'))
- prefix = []
- for x in a[::-1]:
- if re.match('[0-9]', x):
- #操作數，直接輸出
- prefix.append(x)
- else:
- #如果是“)”，壓入棧中
- if x == ')':
- s.push(x)
- elif x == '(':
- while True:
- i = s.pop()
- if i == ')':
- break
- else:
- prefix.append(i)
- else:
- if s.size() > 0 and prec[x] <= prec[s.peek()]:
- prefix.append(s.pop())
- s.push(x)
- for _ in range(s.size()):
- prefix.append(s.pop())
- return prefix[::-1]
- def cal_prefix(s, prefix):
- # 思路：對前綴表達式從后向前掃描，設定一個操作數棧，如果是操作數，則將其直接入棧，如果是操作符，則從棧中彈出操作符對應的操作數進行運算，并將計算結果壓棧。
- # 直至從右到左掃描完畢整個前綴表達式，這時操作數棧中應該只有一個元素，該元素的值則為前綴表達式的計算結果。
- for x in prefix[::-1]:
- if re.match('[0-9]', x):
- s.push(x)
- else:
- a2 = int(s.pop())
- a1 = int(s.pop())
- if x == '*':
- a = a1 * a2
- elif x == '/':
- a = a2 / a1
- elif x == '+':
- a = a1 + a2
- else:
- a = a2 - a1
- s.push(a)
- return s.pop()
- if __name__ == '__main__':
- s = Stack()
- prefix = infix_to_prefix(s)
- print('前綴表達式：', prefix)
- prefix_val = cal_prefix(s, prefix)
- print('前綴表達式計算結果：', prefix_val)
- 請輸入中綴表達式：2*3/(2-1)+3*(4-1)
- 前綴表達式： ['+', '*', '2', '/', '3', '-', '2', '1', '*', '3', '-', '4', '1']
- 前綴表達式計算結果： 15
- 請輸入中綴表達式：9+(3-1*2)*3+10/2
- 前綴表達式： ['+', '+', '9', '*', '-', '3', '*', '1', '2', '3', '/', '10', '2']
- 前綴表達式計算結果： 17
中綴表達式轉換為后綴表達式求值
中綴表達式轉后綴表達式的規則：
1.遇到操作數，直接輸出;
2.棧為空時，遇到運算符，入棧;
3.遇到左括號，將其入棧;
4.遇到右括號，執行出棧操作，并將出棧的元素輸出，直到彈出棧的是左括號，左括號不輸出;
5.遇到其他運算符’+”-”*”/’時，彈出所有優先級大于或等于該運算符的棧頂元素，然后將該運算符入棧;
6.最終將棧中的元素依次出棧，輸出。
經過上面的步驟，得到的輸出既是轉換得到的后綴表達式。
后綴表達式的計算方法：對后綴表達式從前向后掃描，設定一個操作數棧，如果是操作數，則將其直接入棧，如果是操作符，則從棧中彈出操作符對應的操作數進行運算，并將計算結果壓棧。直至從右到左掃描完畢整個后綴表達式，這時操作數棧中應該只有一個元素，該元素的值則為后綴表達式的計算結果。
上面的過程使用數據結構棧來實現，具體代碼如下:
- '''
- @Author：Runsen
- @WeChat：RunsenLiu
- @微信公眾號：Python之王
- @CSDN：https://blog.csdn.net/weixin_44510615
- @Github：https://github.com/MaoliRUNsen
- @Date：2020/12/17
- '''
- import re
- class Stack():
- def __init__(self):
- self.items = []
- def push(self, item):
- return self.items.append(item)
- def pop(self):
- return self.items.pop()
- def size(self):
- return len(self.items)
- def peek(self):
- return self.items[len(self.items) - 1]
- def display(self):
- print(self.items)
- def infix_to_postfix (s):
- prec = {
- '*': 3,
- '/': 3,
- '+': 2,
- '-': 2,
- '(': 1,
- ')': 4
- }
- a = re.findall('[1-9]\d*|[\+\-\*\/\(\)]', input('請輸入中綴表達式：'))
- postfix = []
- for x in a:
- if re.match('[0-9]', x):
- # 操作數，直接輸出
- postfix.append(x)
- else:
- # 如果是“(”，壓入棧中
- if x == '(':
- s.push(x)
- elif x == ')':
- while True:
- i = s.pop()
- if i == '(':
- break
- else:
- postfix.append(i)
- else:
- if s.size() > 0 and prec[x] <= prec[s.peek()]:
- postfix.append(s.pop())
- s.push(x)
- for _ in range(s.size()):
- postfix.append(s.pop())
- return postfix
- def cal_postfix (s, postfix):
- for x in postfix:
- if re.match('[0-9]', x):
- s.push(x)
- else:
- a1 = int(s.pop())
- a2 = int(s.pop())
- if x == '*':
- a = a1 * a2
- elif x == '/':
- a = a2 / a1
- elif x == '+':
- a = a1 + a2
- else:
- a = a2 - a1
- s.push(a)
- return s.pop()
- if __name__ == '__main__':
- s = Stack()
- postfix = infix_to_postfix(s)
- print('后綴表達式：', postfix)
- postfix_val = cal_postfix (s, postfix)
- print('后綴表達式計算結果：', postfix_val)
- 請輸入中綴表達式：2*3/(2-1)+3*(4-1)
- ['2', '3', '*', '2', '1', '-', '/', '3', '4', '1', '-']
- 后綴表達式： ['2', '3', '*', '2', '1', '-', '/', '3', '4', '1', '-', '*', '+']
- 后綴表達式計算結果： 15
- 請輸入中綴表達式：9+(3-1*2)*3+10/2
- 后綴表達式： ['9', '3', '1', '2', '*', '-', '3', '*', '10', '2', '/', '+', '+']
- 后綴表達式計算結果： 17
其實此題是Leetcode第150題，逆波蘭表達式求值。
根據 逆波蘭表示法，求表達式的值。
有效的運算符包括 +, -, *, / 。每個運算對象可以是整數，也可以是另一個逆波蘭表達式。
- 示例 1：
- 輸入: ["2", "1", "+", "3", "*"]
- 輸出: 9
- 解釋: 該算式轉化為常見的中綴算術表達式為：((2 + 1) * 3) = 9
- 示例 2：
- 輸入: ["4", "13", "5", "/", "+"]
- 輸出: 6
- 解釋: 該算式轉化為常見的中綴算術表達式為：(4 + (13 / 5)) = 6
前綴表達式轉中綴表達式
從右往左開始，取出一個操作符和操作符右邊的兩個數進行計算，并將計算的結果放過去，直到計算結束。以前綴表達式+/*23-21*3-41為例，將其轉換為中綴表達式：
(1)取出-、4、1，計算并將結果放回得到+/*23-21*3(4-1);
(2)取出*、3、(4-1)，計算并將結果放回得到+/*23-21(3*(4-1));
(3)取出-、2、1，計算并將結果放回得到+/*23(2-1)(3*(4-1));
(3)取出*、2、3，計算并將結果放回得到+/(2*3)(2-1)(3*(4-1));
(4)取出/、(2*3)、(2-1)，計算并將結果放回得到+((2*3)/(2-1))(3*(4-1));
(5)取出+、((2*3)/(2-1))、(3*(4-1))，計算將結果放回得到((2*3)/(2-1))+(3*(4-1))，計算結束，顯然計算結果為15。
后綴表達式轉中綴表達式從左向右開始，取出一個操作符和操作符左邊的兩個數進行計算，并將計算的結果放過去，直到計算結束，以后綴表達式23*21-/341-*+為例，將其轉換為中綴表達式：(1)取出2、3、*，計算并將結果放回得到(2*3)21-/341-*+;
(2)取出2，1，-，計算并將結果放回得到(2*3)(2-1)/341-*+;
(3)取出(2*3)、(2-1)、/，計算并將結果放回得到((2*3)/(2-1))341-*+;
(4)取出4，1，-，計算并將結果放回得到((2*3)/(2-1)) 3(4-1)*+;
(5)取出3，(4-1)，*，計算并將結果放回得到((2*3)/(2-1)) 3*(4-1)+;
(6)取出((2*3)/(2-1))，3*(4-1)，+，計算并將結果放回得到((2*3)/(2-1)) + 3*(4-1)，顯然計算結果為15。
本文已收錄 GitHub: https://github.com/MaoliRUNsen/runsenlearnpy100
