六十四、前綴，后綴，中綴表達式轉化求值問題

「@Author：Runsen」

?

編程的本質來源于算法，而算法的本質來源于數(shù)學，編程只不過將數(shù)學題進行代碼化。「---- Runsen」

?

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

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

前綴，后綴，中綴表達式相互轉換及其運算，可以說是計算機考研的一個重點。

首先看下面所示表格：

?

注意：前序表達式和后序表達式是沒有擴號

?

這篇文章有對應的圖解：https://mp.weixin.qq.com/s/NRbFXZAXEUeXhKKYY7CReg

中綴表達式轉前綴表達式求值

中綴表達式轉前綴表達式的規(guī)則：

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

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

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

上面的過程使用數(shù)據(jù)結構棧來實現(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('請輸入中綴表達式：'))
????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):
????#?思路：對前綴表達式從后向前掃描，設定一個操作數(shù)棧，如果是操作數(shù)，則將其直接入棧，如果是操作符，則從棧中彈出操作符對應的操作數(shù)進行運算，并將計算結果壓棧。
????#?直至從右到左掃描完畢整個前綴表達式，這時操作數(shù)棧中應該只有一個元素，該元素的值則為前綴表達式的計算結果。
????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

中綴表達式轉換為后綴表達式求值

中綴表達式轉后綴表達式的規(guī)則：

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

2.棧為空時，遇到運算符，入棧；

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

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

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

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

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

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

上面的過程使用數(shù)據(jù)結構棧來實現(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('請輸入中綴表達式：'))
????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('后綴表達式：',?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題，逆波蘭表達式求值。

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

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

示例 1：

輸入:?["2",?"1",?"+",?"3",?"*"]
輸出:?9
解釋:?該算式轉化為常見的中綴算術表達式為：((2 + 1)?* 3)?= 9
示例 2：

輸入:?["4",?"13",?"5",?"/",?"+"]
輸出:?6
解釋:?該算式轉化為常見的中綴算術表達式為：(4 +?(13 / 5))?= 6

前綴表達式轉中綴表達式

從右往左開始，取出一個操作符和操作符右邊的兩個數(shù)進行計算，并將計算的結果放過去，直到計算結束。以前綴表達式+/*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。

后綴表達式轉中綴表達式

從左向右開始，取出一個操作符和操作符左邊的兩個數(shù)進行計算，并將計算的結果放過去，直到計算結束，以后綴表達式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，傳送門~^[1] ，里面更有大廠面試完整考點，歡迎 Star。

?

Reference