六十三、棧在括號(hào)匹配和表達(dá)式求值中的應(yīng)用

「@Author：Runsen」

?

編程的本質(zhì)來(lái)源于算法，而算法的本質(zhì)來(lái)源于數(shù)學(xué)，編程只不過(guò)將數(shù)學(xué)題進(jìn)行代碼化。「---- Runsen」

?

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

括號(hào)匹配

這是Leetcode第20題，也是一道單調(diào)棧的簡(jiǎn)單題。

給定一個(gè)只包括'('，')'，'{'，'}'，'['，']'的字符串，判斷字符串是否有效。

有效字符串需滿足：

• 左括號(hào)必須用相同類(lèi)型的右括號(hào)閉合。
• 左括號(hào)必須以正確的順序閉合。
• 注意空字符串可被認(rèn)為是有效字符串。

輸入: "{[]}"輸出: true

單調(diào)棧關(guān)鍵在于如何入棧和出棧。

用棧保存為匹配的左括號(hào)，從左到右一次掃描字符串，當(dāng)掃描到左括號(hào)時(shí)，則將其壓入棧中；當(dāng)掃描到右括號(hào)時(shí)，從棧頂取出一個(gè)左括號(hào)，如果能匹配上，則繼續(xù)掃描剩下的字符串。如果掃描過(guò)程中，遇到不能配對(duì)的右括號(hào)，或者棧中沒(méi)有數(shù)據(jù)，則說(shuō)明為非法格式。

當(dāng)所有的括號(hào)都掃描完成之后，如果棧為空，則說(shuō)明字符串為合法格式；否則，說(shuō)明未匹配的左括號(hào)為非法格式。

def?isValid(s):
????"""
????:type?s:?str
????:rtype:?bool
????"""
????stack?=?[]
????paren_map?={')':'(',']':'[','}':'{'}
????for?c?in?s:
????????if?c?not?in?paren_map:
????????????stack.append(c)
????????elif?not?stack?or?paren_map[c]?!=stack.pop():
????????????return?False
????return?not?stack
s?=?input('輸入括號(hào)字符:')
print(isValid(s))

在此題中，也可以利用python種的replace函數(shù)將成對(duì)的可匹配括號(hào)用空字符代替 ，之后依次進(jìn)行 ，若是有效的括號(hào) ，必然經(jīng)過(guò)有限次循環(huán)后 ，字符串為空 ，則最后判斷字符串是否為空即可。思路簡(jiǎn)單，實(shí)現(xiàn)也很容易：

def?isValid(s):
????"""
????:type?s:?str
????:rtype:?bool
????"""
????n?=?len(s)
????if?n?==?0:?return?True
????while?'()'?in?s?or?'{}'?in?s?or?'[]'?in?s:
????????s?=?s.replace('{}','').replace('[]','').replace('()Val','')
????return?s?==?''

數(shù)學(xué)表達(dá)式

首先，我們來(lái)看一下數(shù)學(xué)表達(dá)式的三種形式：前綴表達(dá)式，中綴表達(dá)式，后綴表達(dá)式。

中綴表達(dá)式（Infix Expression）就是我們平時(shí)常用的書(shū)寫(xiě)方式，帶有括號(hào)。

前綴表達(dá)式（Prefix Expression）要求運(yùn)算符出現(xiàn)在運(yùn)算數(shù)字的前面。

后綴表達(dá)式（Postfix Expression）要求運(yùn)算符出現(xiàn)在運(yùn)算數(shù)字的后面，一般這兩種表達(dá)式不出現(xiàn)括號(hào)。后綴表達(dá)式，又稱(chēng)逆波蘭式。

數(shù)學(xué)表達(dá)式的三種形式示例如下：

中綴表達(dá)式操作符是以中綴形式處于操作數(shù)的中間（例：3 + 4），中綴表達(dá)式是人們常用的算術(shù)表示方法。與前綴表達(dá)式（例：+ 1 2）或后綴表達(dá)式（例：1 2 +）相比，中綴表達(dá)式不容易被計(jì)算機(jī)解析，但仍被許多程序語(yǔ)言使用，因?yàn)樗先藗兊钠毡橛梅ā?/p>

下面問(wèn)題轉(zhuǎn)為為：如何利用棧實(shí)現(xiàn)中綴表達(dá)式求值，比如：34+13*9+44-12/3=191

思路：利用兩個(gè)棧，其中一個(gè)用來(lái)保存操作數(shù)，另一個(gè)用來(lái)保存運(yùn)算符。

我們從左向右遍歷表達(dá)式，當(dāng)遇到數(shù)字，我們就直接壓入操作數(shù)棧；當(dāng)遇到運(yùn)算符，就與運(yùn)算符棧的棧頂元素進(jìn)行比較。

若比運(yùn)算符棧頂元素優(yōu)先級(jí)高，就將當(dāng)前運(yùn)算符壓入棧，若比運(yùn)算符棧頂元素的優(yōu)先級(jí)低或者相同，從運(yùn)算符棧中取出棧頂運(yùn)算符，從操作數(shù)棧頂取出2個(gè)操作數(shù)，然后進(jìn)行計(jì)算，把計(jì)算完的結(jié)果壓入操作數(shù)棧，繼續(xù)比較。

def?infix_evaluator(infix_expression?:?str)?->?int?:
????'''這是中綴表達(dá)式求值的函數(shù)
????:參數(shù)?infix_expression:中綴表達(dá)式?需要用空格進(jìn)行隔開(kāi)
????'''
????token_list?=?infix_expression.split()
????print(token_list)
????#?運(yùn)算符優(yōu)先級(jí)字典
????pre_dict?=?{'*':3,'/':3,'+':2,'-':2,?'(':1}
????#?運(yùn)算符棧
????operator_stack?=?[]
????#?操作數(shù)棧
????operand_stack?=?[]
????for?token?in?token_list:
????????#?數(shù)字進(jìn)操作數(shù)棧
????????print(token)
????????#?10或者-10的情況
????????if?token.isdecimal()?or?token[1:].isdecimal():?
????????????operand_stack.append(int(token))
????????#?左括號(hào)進(jìn)運(yùn)算符棧
????????elif?token?==?'(':
????????????operator_stack.append(token)
????????#?碰到右括號(hào)，就要把棧頂?shù)淖罄ㄌ?hào)上面的運(yùn)算符都彈出求值
????????elif?token?==?')':
????????????top?=?operator_stack.pop()
????????????while?top?!=?'(':
????????????????#?每彈出一個(gè)運(yùn)算符，就要彈出兩個(gè)操作數(shù)來(lái)求值
????????????????#?注意彈出操作數(shù)的順序是反著的，先彈出的數(shù)是op2
????????????????op2?=?operand_stack.pop()
????????????????op1?=?operand_stack.pop()
????????????????#?求出的值要壓回操作數(shù)棧
????????????????#?這里用到的函數(shù)get_value在下面有定義
????????????????operand_stack.append(get_value(top,op1,op2))
????????????????#?彈出下一個(gè)棧頂運(yùn)算符
????????????????top?=?operator_stack.pop()
????????#?碰到運(yùn)算符，就要把棧頂優(yōu)先級(jí)不低于它的都彈出求值
????????elif?token?in?'+-*/':
????????????while?operator_stack?and?pre_dict[operator_stack[-1]]?>=?pre_dict[token]:
????????????????top?=?operator_stack.pop()
????????????????op2?=?operand_stack.pop()
????????????????op1?=?operand_stack.pop()
????????????????operand_stack.append(get_value(top,op1,op2))
????????????#?別忘了最后讓當(dāng)前運(yùn)算符進(jìn)棧
????????????operator_stack.append(token)
????#?表達(dá)式遍歷完成后，棧里剩下的操作符也都要求值???
????while?operator_stack:
????????top?=?operator_stack.pop()
????????op2?=?operand_stack.pop()
????????op1?=?operand_stack.pop()
????????operand_stack.append(get_value(top,op1,op2))
????#?最后棧里只剩下一個(gè)數(shù)字，這個(gè)數(shù)字就是整個(gè)表達(dá)式最終的結(jié)果
????print(operand_stack)
????print(operator_stack)
????return?operand_stack[0]
?
def?get_value(operator?:?str,?op1?:?int,?op2?:?int):
????'''這是四則運(yùn)算函數(shù)
????:參數(shù)?operator:運(yùn)算符
????:參數(shù)?op1:左邊的操作數(shù)
????:參數(shù)?op2:右邊的操作數(shù)
????'''
????if?operator?==?'+':
????????return?op1?+?op2
????elif?operator?==?'-':
????????return?op1?-?op2
????elif?operator?==?'*':
????????return?op1?*?op2
????elif?operator?==?'/':
????????return?op1?/?op2
?
#?用一個(gè)例子試試，得出了結(jié)果??17.0
print(infix_evaluator('9?+?(?3?-?1?*?2?)?*?3?+?10?/?2'))

17.0

上述程序只是使用四則運(yùn)算表達(dá)式進(jìn)行學(xué)習(xí)計(jì)算，但是輸入需要加空格進(jìn)行分隔，比如9 + ( 3 - 1 * 2 ) * 3 + 10 / 2分隔為['9', '+', '(', '3', '-', '1', '*', '2', ')', '*', '3', '+', '10', '/', '2']。

后來(lái)嘗將9+(3-1*2)*3+10/2分隔為['9', '+', '(', '3', '-', '1', '*', '2', ')', '*', '3', '+', '10', '/', '2']。

后來(lái)想到了正則表達(dá)式1-9]\d*|[\+\-\*\/\(\)]。

import?re
s?=?'9+(3-1*2)*3+10/2'
print(re.findall('[1-9]\d*|[\+\-\*\/\(\)]',s))

['9',?'+',?'(',?'3',?'-',?'1',?'*',?'2',?')',?'*',?'3',?'+',?'10',?'/',?'2']

因此利用棧實(shí)現(xiàn)中綴表達(dá)式求值中等偏難算法題基本完成。

?

本文已收錄 GitHub，傳送門(mén)~^[1] ，里面更有大廠面試完整考點(diǎn)，歡迎 Star。

?

Reference