[[358578]]

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

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

括號匹配這是Leetcode第20題，也是一道單調(diào)棧的簡單題。

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

有效字符串需滿足：

• 左括號必須用相同類型的右括號閉合。
• 左括號必須以正確的順序閉合。
• 注意空字符串可被認為是有效字符串。

輸入: "{[]}"輸出: true單調(diào)棧關鍵在于如何入棧和出棧。

用棧保存為匹配的左括號，從左到右一次掃描字符串，當掃描到左括號時，則將其壓入棧中;當掃描到右括號時，從棧頂取出一個左括號，如果能匹配上，則繼續(xù)掃描剩下的字符串。如果掃描過程中，遇到不能配對的右括號，或者棧中沒有數(shù)據(jù)，則說明為非法格式。

當所有的括號都掃描完成之后，如果棧為空，則說明字符串為合法格式;否則，說明未匹配的左括號為非法格式。

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īng)過有限次循環(huán)后 ，字符串為空 ，則最后判斷字符串是否為空即可。思路簡單，實現(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ù)學表達

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

• 中綴表達式(Infix Expression)就是我們平時常用的書寫方式，帶有括號。
• 前綴表達式(Prefix Expression)要求運算符出現(xiàn)在運算數(shù)字的前面。
• 后綴表達式(Postfix Expression)要求運算符出現(xiàn)在運算數(shù)字的后面，一般這兩種表達式不出現(xiàn)括號。后綴表達式，又稱逆波蘭式。

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

中綴表達式操作符是以中綴形式處于操作數(shù)的中間(例：3 + 4)，中綴表達式是人們常用的算術表示方法。與前綴表達式(例：+ 1 2)或后綴表達式(例：1 2 +)相比，中綴表達式不容易被計算機解析，但仍被許多程序語言使用，因為它符合人們的普遍用法。

下面問題轉(zhuǎn)為為：如何利用棧實現(xiàn)中綴表達式求值，比如：34+13*9+44-12/3=191思路：利用兩個棧，其中一個用來保存操作數(shù)，另一個用來保存運算符。

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

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

def infix_evaluator(infix_expression : str) -> int : 
    '''這是中綴表達式求值的函數(shù) 
    :參數(shù) infix_expression:中綴表達式 需要用空格進行隔開 
    ''' 
    token_list = infix_expression.split() 
    print(token_list) 
    # 運算符優(yōu)先級字典 
    pre_dict = {'*':3,'/':3,'+':2,'-':2, '(':1} 
    # 運算符棧 
    operator_stack = [] 
    # 操作數(shù)棧 
    operand_stack = [] 
    for token in token_list: 
        # 數(shù)字進操作數(shù)棧 
        print(token) 
        # 10或者-10的情況 
        if token.isdecimal() or token[1:].isdecimal():  
            operand_stack.append(int(token)) 
        # 左括號進運算符棧 
        elif token == '(': 
            operator_stack.append(token) 
        # 碰到右括號，就要把棧頂?shù)淖罄ㄌ柹厦娴倪\算符都彈出求值 
        elif token == ')': 
            top = operator_stack.pop() 
            while top != '(': 
                # 每彈出一個運算符，就要彈出兩個操作數(shù)來求值 
                # 注意彈出操作數(shù)的順序是反著的，先彈出的數(shù)是op2 
                op2 = operand_stack.pop() 
                op1 = operand_stack.pop() 
                # 求出的值要壓回操作數(shù)棧 
                # 這里用到的函數(shù)get_value在下面有定義 
                operand_stack.append(get_value(top,op1,op2)) 
                # 彈出下一個棧頂運算符 
                top = operator_stack.pop() 
        # 碰到運算符，就要把棧頂優(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)) 
            # 別忘了最后讓當前運算符進棧 
            operator_stack.append(token) 
    # 表達式遍歷完成后，棧里剩下的操作符也都要求值    
    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ù)字就是整個表達式最終的結(jié)果 
    print(operand_stack) 
    print(operator_stack) 
    return operand_stack[0] 
  
def get_value(operator : str, op1 : int, op2 : int): 
    '''這是四則運算函數(shù) 
    :參數(shù) operator:運算符 
    :參數(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 

上述程序只是使用四則運算表達式進行學習計算，但是輸入需要加空格進行分隔，比如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']。

后來想到了正則表達式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'] 

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

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