日本综合一区二区|亚洲中文天堂综合|日韩欧美自拍一区|男女精品天堂一区|欧美自拍第6页亚洲成人精品一区|亚洲黄色天堂一区二区成人|超碰91偷拍第一页|日韩av夜夜嗨中文字幕|久久蜜综合视频官网|精美人妻一区二区三区

RELATEED CONSULTING
相關(guān)咨詢
選擇下列產(chǎn)品馬上在線溝通
服務(wù)時(shí)間:8:30-17:00
你可能遇到了下面的問題
關(guān)閉右側(cè)工具欄

新聞中心

這里有您想知道的互聯(lián)網(wǎng)營銷解決方案
淺析前綴,后綴,中綴表達(dá)式轉(zhuǎn)化求值問題

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

10年積累的成都網(wǎng)站建設(shè)、網(wǎng)站制作經(jīng)驗(yàn),可以快速應(yīng)對客戶對網(wǎng)站的新想法和需求。提供各種問題對應(yīng)的解決方案。讓選擇我們的客戶得到更好、更有力的網(wǎng)絡(luò)服務(wù)。我雖然不認(rèn)識你,你也不認(rèn)識我。但先網(wǎng)站設(shè)計(jì)后付款的網(wǎng)站建設(shè)流程,更有常寧免費(fèi)網(wǎng)站建設(shè)讓你可以放心的選擇與我們合作。

上次介紹如何利用棧實(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ò)號

這篇文章有對應(yīng)的圖解:https://mp.weixin.qq.com/s/NRbFXZAXEUeXhKKYY7CReg

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

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

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

 
 
 
 
  1. ''' 
  2. @Author:Runsen 
  3. @WeChat:RunsenLiu  
  4. @微信公眾號:Python之王 
  5. @CSDN:https://blog.csdn.net/weixin_44510615 
  6. @Github:https://github.com/MaoliRUNsen 
  7. @Date:2020/12/17 
  8. ''' 
  9. import re 
  10.  
  11. class Stack(): 
  12.     def __init__(self): 
  13.         self.items = [] 
  14.  
  15.     def push(self, item): 
  16.         return self.items.append(item) 
  17.  
  18.     def pop(self): 
  19.         return self.items.pop() 
  20.  
  21.     def size(self): 
  22.         return len(self.items) 
  23.  
  24.     def peek(self): 
  25.         return self.items[len(self.items) - 1] 
  26.  
  27.     def display(self): 
  28.         print(self.items) 
  29.  
  30. def infix_to_prefix(s): 
  31.     prec = { 
  32.         '*': 3, 
  33.         '/': 3, 
  34.         '+': 2, 
  35.         '-': 2, 
  36.         '(': 4, 
  37.         ')': 1 
  38.     } 
  39.  
  40.     a = re.findall('[1-9]\d*|[\+\-\*\/\(\)]', input('請輸入中綴表達(dá)式:')) 
  41.     prefix = [] 
  42.  
  43.     for x in a[::-1]: 
  44.         if re.match('[0-9]', x): 
  45.             #操作數(shù),直接輸出 
  46.             prefix.append(x) 
  47.         else: 
  48.             #如果是“)”,壓入棧中 
  49.             if x == ')': 
  50.                 s.push(x) 
  51.             elif x == '(': 
  52.                 while True: 
  53.                     i = s.pop() 
  54.                     if i == ')': 
  55.                         break 
  56.                     else: 
  57.                         prefix.append(i) 
  58.             else: 
  59.                 if s.size() > 0 and prec[x] <= prec[s.peek()]: 
  60.                     prefix.append(s.pop()) 
  61.                 s.push(x) 
  62.     for _ in range(s.size()): 
  63.         prefix.append(s.pop()) 
  64.     return prefix[::-1] 
  65.      
  66. def cal_prefix(s, prefix): 
  67.     # 思路:對前綴表達(dá)式從后向前掃描,設(shè)定一個(gè)操作數(shù)棧,如果是操作數(shù),則將其直接入棧,如果是操作符,則從棧中彈出操作符對應(yīng)的操作數(shù)進(jìn)行運(yùn)算,并將計(jì)算結(jié)果壓棧。 
  68.     # 直至從右到左掃描完畢整個(gè)前綴表達(dá)式,這時(shí)操作數(shù)棧中應(yīng)該只有一個(gè)元素,該元素的值則為前綴表達(dá)式的計(jì)算結(jié)果。 
  69.     for x in prefix[::-1]: 
  70.         if re.match('[0-9]', x): 
  71.             s.push(x) 
  72.         else: 
  73.             a2 = int(s.pop()) 
  74.             a1 = int(s.pop()) 
  75.             if x == '*': 
  76.                 a = a1 * a2 
  77.             elif x == '/': 
  78.                 a = a2 / a1 
  79.             elif x == '+': 
  80.                 a = a1 + a2 
  81.             else: 
  82.                 a = a2 - a1 
  83.             s.push(a) 
  84.     return s.pop() 
  85.  
  86. if __name__ == '__main__': 
  87.     s = Stack() 
  88.     prefix = infix_to_prefix(s) 
  89.     print('前綴表達(dá)式:', prefix) 
  90.     prefix_val = cal_prefix(s, prefix) 
  91.     print('前綴表達(dá)式計(jì)算結(jié)果:', prefix_val) 
  92.  
  93. 請輸入中綴表達(dá)式:2*3/(2-1)+3*(4-1) 
  94. 前綴表達(dá)式: ['+', '*', '2', '/', '3', '-', '2', '1', '*', '3', '-', '4', '1'] 
  95. 前綴表達(dá)式計(jì)算結(jié)果: 15 
  96. 請輸入中綴表達(dá)式:9+(3-1*2)*3+10/2 
  97. 前綴表達(dá)式: ['+', '+', '9', '*', '-', '3', '*', '1', '2', '3', '/', '10', '2'] 
  98. 前綴表達(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),具體代碼如下:

 
 
 
 
  1. ''' 
  2. @Author:Runsen 
  3. @WeChat:RunsenLiu 
  4. @微信公眾號:Python之王 
  5. @CSDN:https://blog.csdn.net/weixin_44510615 
  6. @Github:https://github.com/MaoliRUNsen 
  7. @Date:2020/12/17 
  8. ''' 
  9. import re 
  10.  
  11. class Stack(): 
  12.     def __init__(self): 
  13.         self.items = [] 
  14.  
  15.     def push(self, item): 
  16.         return self.items.append(item) 
  17.  
  18.     def pop(self): 
  19.         return self.items.pop() 
  20.  
  21.     def size(self): 
  22.         return len(self.items) 
  23.  
  24.     def peek(self): 
  25.         return self.items[len(self.items) - 1] 
  26.  
  27.     def display(self): 
  28.         print(self.items) 
  29.  
  30.  
  31. def infix_to_postfix (s): 
  32.     prec = { 
  33.         '*': 3, 
  34.         '/': 3, 
  35.         '+': 2, 
  36.         '-': 2, 
  37.         '(': 1, 
  38.         ')': 4 
  39.     } 
  40.  
  41.     a = re.findall('[1-9]\d*|[\+\-\*\/\(\)]', input('請輸入中綴表達(dá)式:')) 
  42.     postfix = [] 
  43.  
  44.     for x in a: 
  45.         if re.match('[0-9]', x): 
  46.             # 操作數(shù),直接輸出 
  47.             postfix.append(x) 
  48.         else: 
  49.             # 如果是“(”,壓入棧中 
  50.             if x == '(': 
  51.                 s.push(x) 
  52.             elif x == ')': 
  53.                 while True: 
  54.                     i = s.pop() 
  55.                     if i == '(': 
  56.                         break 
  57.                     else: 
  58.                         postfix.append(i) 
  59.             else: 
  60.                 if s.size() > 0 and prec[x] <= prec[s.peek()]: 
  61.                     postfix.append(s.pop()) 
  62.                 s.push(x) 
  63.     for _ in range(s.size()): 
  64.         postfix.append(s.pop()) 
  65.     return postfix 
  66.  
  67.  
  68. def cal_postfix (s, postfix): 
  69.     for x in postfix: 
  70.         if re.match('[0-9]', x): 
  71.             s.push(x) 
  72.         else: 
  73.             a1 = int(s.pop()) 
  74.             a2 = int(s.pop()) 
  75.             if x == '*': 
  76.                 a = a1 * a2 
  77.             elif x == '/': 
  78.                 a = a2 / a1 
  79.             elif x == '+': 
  80.                 a = a1 + a2 
  81.             else: 
  82.                 a = a2 - a1 
  83.             s.push(a) 
  84.     return s.pop() 
  85.  
  86.  
  87. if __name__ == '__main__': 
  88.     s = Stack() 
  89.     postfix = infix_to_postfix(s) 
  90.     print('后綴表達(dá)式:', postfix) 
  91.     postfix_val = cal_postfix (s, postfix) 
  92.     print('后綴表達(dá)式計(jì)算結(jié)果:', postfix_val) 
  93.  
  94.  
  95. 請輸入中綴表達(dá)式:2*3/(2-1)+3*(4-1) 
  96. ['2', '3', '*', '2', '1', '-', '/', '3', '4', '1', '-'] 
  97. 后綴表達(dá)式: ['2', '3', '*', '2', '1', '-', '/', '3', '4', '1', '-', '*', '+'] 
  98. 后綴表達(dá)式計(jì)算結(jié)果: 15 
  99. 請輸入中綴表達(dá)式:9+(3-1*2)*3+10/2 
  100. 后綴表達(dá)式: ['9', '3', '1', '2', '*', '-', '3', '*', '10', '2', '/', '+', '+'] 
  101. 后綴表達(dá)式計(jì)算結(jié)果: 17 

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

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

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

 
 
 
 
  1. 示例 1: 
  2.  
  3. 輸入: ["2", "1", "+", "3", "*"] 
  4. 輸出: 9 
  5. 解釋: 該算式轉(zhuǎn)化為常見的中綴算術(shù)表達(dá)式為:((2 + 1) * 3) = 9 
  6. 示例 2: 
  7.  
  8. 輸入: ["4", "13", "5", "/", "+"] 
  9. 輸出: 6 
  10. 解釋: 該算式轉(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。

本文已收錄 GitHub: https://github.com/MaoliRUNsen/runsenlearnpy100


網(wǎng)站題目:淺析前綴,后綴,中綴表達(dá)式轉(zhuǎn)化求值問題
本文鏈接:http://www.dlmjj.cn/article/cdcsdoc.html