建站
咨詢
售后
建站咨詢
新聞中心
編程的本質(zhì)來源于算法，而算法的本質(zhì)來源于數(shù)學(xué)，編程只不過將數(shù)學(xué)題進(jìn)行代碼化。
網(wǎng)站設(shè)計制作、成都網(wǎng)站制作的關(guān)注點(diǎn)不是能為您做些什么網(wǎng)站，而是怎么做網(wǎng)站，有沒有做好網(wǎng)站，給成都創(chuàng)新互聯(lián)一個展示的機(jī)會來證明自己，這并不會花費(fèi)您太多時間，或許會給您帶來新的靈感和驚喜。面向用戶友好，注重用戶體驗(yàn)，一切以用戶為中心。
算法，一門既不容易入門，也不容易精通的學(xué)問。
括號匹配這是Leetcode第20題，也是一道單調(diào)棧的簡單題。
給定一個只包括'('，')'，'{'，'}'，'['，']'的字符串，判斷字符串是否有效。
有效字符串需滿足：
- 左括號必須用相同類型的右括號閉合。
- 左括號必須以正確的順序閉合。
- 注意空字符串可被認(rèn)為是有效字符串。
輸入: "{[]}"輸出: true單調(diào)棧關(guān)鍵在于如何入棧和出棧。
用棧保存為匹配的左括號，從左到右一次掃描字符串，當(dāng)掃描到左括號時，則將其壓入棧中;當(dāng)掃描到右括號時，從棧頂取出一個左括號，如果能匹配上，則繼續(xù)掃描剩下的字符串。如果掃描過程中，遇到不能配對的右括號，或者棧中沒有數(shù)據(jù)，則說明為非法格式。
當(dāng)所有的括號都掃描完成之后，如果棧為空，則說明字符串為合法格式;否則，說明未匹配的左括號為非法格式。
- 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('輸入括號字符:')
- print(isValid(s))
在此題中，也可以利用python種的replace函數(shù)將成對的可匹配括號用空字符代替 ，之后依次進(jìn)行 ，若是有效的括號 ，必然經(jīng)過有限次循環(huá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)就是我們平時常用的書寫方式，帶有括號。
- 前綴表達(dá)式(Prefix Expression)要求運(yùn)算符出現(xiàn)在運(yùn)算數(shù)字的前面。
- 后綴表達(dá)式(Postfix Expression)要求運(yùn)算符出現(xiàn)在運(yùn)算數(shù)字的后面，一般這兩種表達(dá)式不出現(xiàn)括號。后綴表達(dá)式，又稱逆波蘭式。
數(shù)學(xué)表達(dá)式的三種形式示例如下：
中綴表達(dá)式操作符是以中綴形式處于操作數(shù)的中間(例：3 + 4)，中綴表達(dá)式是人們常用的算術(shù)表示方法。與前綴表達(dá)式(例：+ 1 2)或后綴表達(dá)式(例：1 2 +)相比，中綴表達(dá)式不容易被計算機(jī)解析，但仍被許多程序語言使用，因?yàn)樗先藗兊钠毡橛梅ā?/p>
下面問題轉(zhuǎn)為為：如何利用棧實(shí)現(xiàn)中綴表達(dá)式求值，比如：34+13*9+44-12/3=191思路：利用兩個棧，其中一個用來保存操作數(shù)，另一個用來保存運(yùn)算符。
我們從左向右遍歷表達(dá)式，當(dāng)遇到數(shù)字，我們就直接壓入操作數(shù)棧;當(dāng)遇到運(yùn)算符，就與運(yùn)算符棧的棧頂元素進(jìn)行比較。
若比運(yùn)算符棧頂元素優(yōu)先級高，就將當(dāng)前運(yùn)算符壓入棧，若比運(yùn)算符棧頂元素的優(yōu)先級低或者相同，從運(yùn)算符棧中取出棧頂運(yùn)算符，從操作數(shù)棧頂取出2個操作數(shù)，然后進(jìn)行計算，把計算完的結(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)先級字典
- 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))
- # 左括號進(jìn)運(yùn)算符棧
- elif token == '(':
- operator_stack.append(token)
- # 碰到右括號，就要把棧頂?shù)淖罄ㄌ柹厦娴倪\(yùn)算符都彈出求值
- elif token == ')':
- top = operator_stack.pop()
- while top != '(':
- # 每彈出一個運(yùn)算符，就要彈出兩個操作數(shù)來求值
- # 注意彈出操作數(shù)的順序是反著的，先彈出的數(shù)是op2
- op2 = operand_stack.pop()
- op1 = operand_stack.pop()
- # 求出的值要壓回操作數(shù)棧
- # 這里用到的函數(shù)get_value在下面有定義
- operand_stack.append(get_value(top,op1,op2))
- # 彈出下一個棧頂運(yùn)算符
- top = operator_stack.pop()
- # 碰到運(yùn)算符，就要把棧頂優(yōu)先級不低于它的都彈出求值
- 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))
- # 最后棧里只剩下一個數(shù)字，這個數(shù)字就是整個表達(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
- # 用一個例子試試，得出了結(jié)果 17.0
- print(infix_evaluator('9 + ( 3 - 1 * 2 ) * 3 + 10 / 2'))
- 17.0
上述程序只是使用四則運(yùn)算表達(dá)式進(jìn)行學(xué)習(xí)計算，但是輸入需要加空格進(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á)式求值中等偏難算法題基本完成。
本文已收錄 GitHub: https://github.com/MaoliRUNsen/runsenlearnpy100
文章題目：聊聊棧在括號匹配和表達(dá)式求值中的應(yīng)用
URL標(biāo)題：http://m.5511xx.com/article/cdjhigc.html
