如何理解前綴，后綴，中綴表達(dá)式轉(zhuǎn)化求值問題

這篇文章主要講解了“如何理解前綴，后綴，中綴表達(dá)式轉(zhuǎn)化求值問題”，文中的講解內(nèi)容簡單清晰，易于學(xué)習(xí)與理解，下面請大家跟著小編的思路慢慢深入，一起來研究和學(xué)習(xí)“如何理解前綴，后綴，中綴表達(dá)式轉(zhuǎn)化求值問題”吧！

創(chuàng)新互聯(lián)-專業(yè)網(wǎng)站定制、快速模板網(wǎng)站建設(shè)、高性價(jià)比香格里拉網(wǎng)站開發(fā)、企業(yè)建站全套包干低至880元,成熟完善的模板庫,直接使用。一站式香格里拉網(wǎng)站制作公司更省心,省錢,快速模板網(wǎng)站建設(shè)找我們，業(yè)務(wù)覆蓋香格里拉地區(qū)。費(fèi)用合理售后完善，十多年實(shí)體公司更值得信賴。

算法，一門既不容易入門，也不容易精通的學(xué)問。

上次介紹如何利用棧實(shí)現(xiàn)中綴表達(dá)式求值，如果我是出題官，當(dāng)然要考前綴，后綴，中綴表達(dá)式相互轉(zhuǎn)換，然后就變成了利用棧實(shí)現(xiàn)前綴和后綴表達(dá)式求值。

前綴，后綴，中綴表達(dá)式相互轉(zhuǎn)換及其運(yùn)算，可以說是計(jì)算機(jī)考研的一個(gè)重點(diǎn)。

首先看下面所示表格：

• 注意：前序表達(dá)式和后序表達(dá)式是沒有擴(kuò)號

中綴表達(dá)式轉(zhuǎn)前綴表達(dá)式求值

中綴表達(dá)式轉(zhuǎn)前綴表達(dá)式的規(guī)則：

1、反轉(zhuǎn)輸入字符串，如“2*3/(2-1)+3*(4-1)” 反轉(zhuǎn)后為“ )1-4(*3+)1-2(/3*2”， 2、從字符串中取出下一個(gè)字符   2.1.如果是操作數(shù)，直接輸出   2.2.如果是“)”，壓入棧中   2.3.如果是運(yùn)算符但不是“(”，“)”,則不斷循環(huán)進(jìn)行以下處理     2.3.1.如果棧為空，則此運(yùn)算符進(jìn)棧，結(jié)束此步驟     2.3.2.如果棧頂是“)”,則此運(yùn)算符進(jìn)棧，結(jié)束此步驟     2.3.2.如果此運(yùn)算符與棧頂優(yōu)先級相同或者更高，此運(yùn)算符進(jìn)棧，結(jié)束此步驟     2.3.4.否則，運(yùn)算符連續(xù)出棧，直到滿足上述三個(gè)條件之一，然后此運(yùn)算符進(jìn)棧   2.4、如果是“(”，則運(yùn)算符連續(xù)出棧，直到遇見“)”為止,將“)”出棧且丟棄之 3、如果還有更多的字符串，則轉(zhuǎn)到第2步 4、不在有未處理的字符串了，輸出棧中剩余元素 5、再次反轉(zhuǎn)字符串得到最終結(jié)果

經(jīng)過上面的步驟，得到的輸出既是轉(zhuǎn)換得到的前綴表達(dá)式。

前綴表達(dá)式的計(jì)算方法：對前綴表達(dá)式從后向前掃描，設(shè)定一個(gè)操作數(shù)棧，如果是操作數(shù)，則將其直接入棧，如果是操作符，則從棧中彈出操作符對應(yīng)的操作數(shù)進(jìn)行運(yùn)算，并將計(jì)算結(jié)果壓棧。直至從右到左掃描完畢整個(gè)前綴表達(dá)式，這時(shí)操作數(shù)棧中應(yīng)該只有一個(gè)元素，該元素的值則為前綴表達(dá)式的計(jì)算結(jié)果。

上面的過程使用數(shù)據(jù)結(jié)構(gòu)棧來實(shí)現(xiàn)，具體代碼如下

''' @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('請輸入中綴表達(dá)式：'))     prefix = []      for x in a[::-1]:         if re.match('[0-9]', x):             #操作數(shù)，直接輸出             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):     # 思路：對前綴表達(dá)式從后向前掃描，設(shè)定一個(gè)操作數(shù)棧，如果是操作數(shù)，則將其直接入棧，如果是操作符，則從棧中彈出操作符對應(yīng)的操作數(shù)進(jìn)行運(yùn)算，并將計(jì)算結(jié)果壓棧。     # 直至從右到左掃描完畢整個(gè)前綴表達(dá)式，這時(shí)操作數(shù)棧中應(yīng)該只有一個(gè)元素，該元素的值則為前綴表達(dá)式的計(jì)算結(jié)果。     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('前綴表達(dá)式：', prefix)     prefix_val = cal_prefix(s, prefix)     print('前綴表達(dá)式計(jì)算結(jié)果：', prefix_val)  請輸入中綴表達(dá)式：2*3/(2-1)+3*(4-1) 前綴表達(dá)式： ['+', '*', '2', '/', '3', '-', '2', '1', '*', '3', '-', '4', '1'] 前綴表達(dá)式計(jì)算結(jié)果： 15 請輸入中綴表達(dá)式：9+(3-1*2)*3+10/2 前綴表達(dá)式： ['+', '+', '9', '*', '-', '3', '*', '1', '2', '3', '/', '10', '2'] 前綴表達(dá)式計(jì)算結(jié)果： 17

中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式求值

中綴表達(dá)式轉(zhuǎn)后綴表達(dá)式的規(guī)則：

1.遇到操作數(shù)，直接輸出;

2.棧為空時(shí)，遇到運(yùn)算符，入棧;

3.遇到左括號，將其入棧;

4.遇到右括號，執(zhí)行出棧操作，并將出棧的元素輸出，直到彈出棧的是左括號，左括號不輸出;

5.遇到其他運(yùn)算符’+”-”*”/’時(shí)，彈出所有優(yōu)先級大于或等于該運(yùn)算符的棧頂元素，然后將該運(yùn)算符入棧;

6.最終將棧中的元素依次出棧，輸出。

經(jīng)過上面的步驟，得到的輸出既是轉(zhuǎn)換得到的后綴表達(dá)式。

后綴表達(dá)式的計(jì)算方法：對后綴表達(dá)式從前向后掃描，設(shè)定一個(gè)操作數(shù)棧，如果是操作數(shù)，則將其直接入棧，如果是操作符，則從棧中彈出操作符對應(yīng)的操作數(shù)進(jìn)行運(yùn)算，并將計(jì)算結(jié)果壓棧。直至從右到左掃描完畢整個(gè)后綴表達(dá)式，這時(shí)操作數(shù)棧中應(yīng)該只有一個(gè)元素，該元素的值則為后綴表達(dá)式的計(jì)算結(jié)果。

上面的過程使用數(shù)據(jù)結(jié)構(gòu)棧來實(shí)現(xiàn)，具體代碼如下:

''' @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('請輸入中綴表達(dá)式：'))     postfix = []      for x in a:         if re.match('[0-9]', x):             # 操作數(shù)，直接輸出             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('后綴表達(dá)式：', postfix)     postfix_val = cal_postfix (s, postfix)     print('后綴表達(dá)式計(jì)算結(jié)果：', postfix_val)   請輸入中綴表達(dá)式：2*3/(2-1)+3*(4-1) ['2', '3', '*', '2', '1', '-', '/', '3', '4', '1', '-'] 后綴表達(dá)式： ['2', '3', '*', '2', '1', '-', '/', '3', '4', '1', '-', '*', '+'] 后綴表達(dá)式計(jì)算結(jié)果： 15 請輸入中綴表達(dá)式：9+(3-1*2)*3+10/2 后綴表達(dá)式： ['9', '3', '1', '2', '*', '-', '3', '*', '10', '2', '/', '+', '+'] 后綴表達(dá)式計(jì)算結(jié)果： 17

其實(shí)此題是Leetcode第150題，逆波蘭表達(dá)式求值。

根據(jù) 逆波蘭表示法，求表達(dá)式的值。

有效的運(yùn)算符包括 +, -, *, / 。每個(gè)運(yùn)算對象可以是整數(shù)，也可以是另一個(gè)逆波蘭表達(dá)式。

示例 1：  輸入: ["2", "1", "+", "3", "*"] 輸出: 9 解釋: 該算式轉(zhuǎn)化為常見的中綴算術(shù)表達(dá)式為：((2 + 1) * 3) = 9 示例 2：  輸入: ["4", "13", "5", "/", "+"] 輸出: 6 解釋: 該算式轉(zhuǎn)化為常見的中綴算術(shù)表達(dá)式為：(4 + (13 / 5)) = 6

前綴表達(dá)式轉(zhuǎn)中綴表達(dá)式

從右往左開始，取出一個(gè)操作符和操作符右邊的兩個(gè)數(shù)進(jìn)行計(jì)算，并將計(jì)算的結(jié)果放過去，直到計(jì)算結(jié)束。以前綴表達(dá)式+/*23-21*3-41為例，將其轉(zhuǎn)換為中綴表達(dá)式：

(1)取出-、4、1，計(jì)算并將結(jié)果放回得到+/*23-21*3(4-1);

(2)取出*、3、(4-1)，計(jì)算并將結(jié)果放回得到+/*23-21(3*(4-1));

(3)取出-、2、1，計(jì)算并將結(jié)果放回得到+/*23(2-1)(3*(4-1));

(3)取出*、2、3，計(jì)算并將結(jié)果放回得到+/(2*3)(2-1)(3*(4-1));

(4)取出/、(2*3)、(2-1)，計(jì)算并將結(jié)果放回得到+((2*3)/(2-1))(3*(4-1));

(5)取出+、((2*3)/(2-1))、(3*(4-1))，計(jì)算將結(jié)果放回得到((2*3)/(2-1))+(3*(4-1))，計(jì)算結(jié)束，顯然計(jì)算結(jié)果為15。

后綴表達(dá)式轉(zhuǎn)中綴表達(dá)式從左向右開始，取出一個(gè)操作符和操作符左邊的兩個(gè)數(shù)進(jìn)行計(jì)算，并將計(jì)算的結(jié)果放過去，直到計(jì)算結(jié)束，以后綴表達(dá)式23*21-/341-*+為例，將其轉(zhuǎn)換為中綴表達(dá)式：(1)取出2、3、*，計(jì)算并將結(jié)果放回得到(2*3)21-/341-*+;

(2)取出2，1，-，計(jì)算并將結(jié)果放回得到(2*3)(2-1)/341-*+;

(3)取出(2*3)、(2-1)、/，計(jì)算并將結(jié)果放回得到((2*3)/(2-1))341-*+;

(4)取出4，1，-，計(jì)算并將結(jié)果放回得到((2*3)/(2-1)) 3(4-1)*+;

(5)取出3，(4-1)，*，計(jì)算并將結(jié)果放回得到((2*3)/(2-1)) 3*(4-1)+;

(6)取出((2*3)/(2-1))，3*(4-1)，+，計(jì)算并將結(jié)果放回得到((2*3)/(2-1)) + 3*(4-1)，顯然計(jì)算結(jié)果為15。

感謝各位的閱讀，以上就是“如何理解前綴，后綴，中綴表達(dá)式轉(zhuǎn)化求值問題”的內(nèi)容了，經(jīng)過本文的學(xué)習(xí)后，相信大家對如何理解前綴，后綴，中綴表達(dá)式轉(zhuǎn)化求值問題這一問題有了更深刻的體會，具體使用情況還需要大家實(shí)踐驗(yàn)證。這里是創(chuàng)新互聯(lián)，小編將為大家推送更多相關(guān)知識點(diǎn)的文章，歡迎關(guān)注！

標(biāo)題名稱：如何理解前綴，后綴，中綴表達(dá)式轉(zhuǎn)化求值問題
標(biāo)題鏈接：http://www.muchs.cn/article12/ihiodc.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供關(guān)鍵詞優(yōu)化、虛擬主機(jī)、外貿(mào)建站、做網(wǎng)站、軟件開發(fā)、建站公司

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源： 創(chuàng)新互聯(lián)