您好,登錄后才能下訂單哦!
這篇文章主要講解了“如何理解棧在括號(hào)匹配和表達(dá)式求值中的應(yīng)用”,文中的講解內(nèi)容簡(jiǎn)單清晰,易于學(xué)習(xí)與理解,下面請(qǐng)大家跟著小編的思路慢慢深入,一起來研究和學(xué)習(xí)“如何理解棧在括號(hào)匹配和表達(dá)式求值中的應(yīng)用”吧!
編程的本質(zhì)來源于算法,而算法的本質(zhì)來源于數(shù)學(xué),編程只不過將數(shù)學(xué)題進(jìn)行代碼化。
算法,一門既不容易入門,也不容易精通的學(xué)問。
括號(hào)匹配這是Leetcode第20題,也是一道單調(diào)棧的簡(jiǎn)單題。
給定一個(gè)只包括'(',')','{','}','[',']'的字符串,判斷字符串是否有效。
有效字符串需滿足:
左括號(hào)必須用相同類型的右括號(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ù)掃描剩下的字符串。如果掃描過程中,遇到不能配對(duì)的右括號(hào),或者棧中沒有數(shù)據(jù),則說明為非法格式。
當(dāng)所有的括號(hào)都掃描完成之后,如果棧為空,則說明字符串為合法格式;否則,說明未匹配的左括號(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)過有限次循環(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á)
式首先,我們來看一下數(shù)學(xué)表達(dá)式的三種形式:前綴表達(dá)式,中綴表達(dá)式,后綴表達(dá)式。
中綴表達(dá)式(Infix Expression)就是我們平時(shí)常用的書寫方式,帶有括號(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á)式,又稱逆波蘭式。
數(shù)學(xué)表達(dá)式的三種形式示例如下:
中綴表達(dá)式操作符是以中綴形式處于操作數(shù)的中間(例:3 + 4),中綴表達(dá)式是人們常用的算術(shù)表示方法。與前綴表達(dá)式(例:+ 1 2)或后綴表達(dá)式(例:1 2 +)相比,中綴表達(dá)式不容易被計(jì)算機(jī)解析,但仍被許多程序語言使用,因?yàn)樗先藗兊钠毡橛梅ā?/p>
下面問題轉(zhuǎn)為為:如何利用棧實(shí)現(xiàn)中綴表達(dá)式求值,比如:34+13*9+44-12/3=191思路:利用兩個(gè)棧,其中一個(gè)用來保存操作數(shù),另一個(gè)用來保存運(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)行隔開 ''' 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ù)來求值 # 注意彈出操作數(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']。
后來嘗將9+(3-1*2)*3+10/2分隔為['9', '+', '(', '3', '-', '1', '*', '2', ')', '*', '3', '+', '10', '/', '2']。
后來想到了正則表達(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á)式求值中等偏難算法題基本完成。
感謝各位的閱讀,以上就是“如何理解棧在括號(hào)匹配和表達(dá)式求值中的應(yīng)用”的內(nèi)容了,經(jīng)過本文的學(xué)習(xí)后,相信大家對(duì)如何理解棧在括號(hào)匹配和表達(dá)式求值中的應(yīng)用這一問題有了更深刻的體會(huì),具體使用情況還需要大家實(shí)踐驗(yàn)證。這里是億速云,小編將為大家推送更多相關(guān)知識(shí)點(diǎn)的文章,歡迎關(guān)注!
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng),如果涉及侵權(quán)請(qǐng)聯(lián)系站長(zhǎng)郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。