python 括弧檢測是否匹配？

01-29

檢測括弧是否正確原題如下：
判斷一個四則運算的括弧是否匹配，例如 3 * {3 +[(2 -3) * (4+5)]} 的括弧是匹配的，而 3 * {3+ [4 - 6}] 的括弧是不匹配的。
我把所有括弧都提取出來到一個列表,然後判斷（）的位置,截取字元串判斷長度的餘數感覺有點不行啊網上查詢了一下發現C都是用棧來實現的但是pyhton的棧不知道怎麼做好有老司機指點一下嗎？

謝邀，這是一道送分題，直接用一個棧(python中可以用List)就可以解決，下面這個例子時間和空間複雜度都是O(n)

# -*- coding: utf8 -*- # 符號表 SYMBOLS = {}:{, ]:[, ):(} SYMBOLS_L, SYMBOLS_R = SYMBOLS.values(), SYMBOLS.keys()


def check(s):

    arr = []

    for c in s:

        if c in SYMBOLS_L:

            # 左符號入棧

            arr.append(c)

        elif c in SYMBOLS_R:

            # 右符號要麼出棧，要麼匹配失敗

            if arr and arr[-1] == SYMBOLS[c]:

                arr.pop()

            else:

                return False
    return not arr

print(check("3 * {3 +[(2 -3) * (4+5)]}")) print(check("3 * {3+ [4 - 6}]"))

Python的list包含了所有棧和雙向隊列的功能，可以用append（後插）、pop（後取）、insert（前插）、pop(0)（前取）來實現。對於隊列來說還有一個deque類型相當於鏈表。都是有對應實現的。

我們說說另一個問題，跟堆棧有關的演算法一般都是跟遞歸結構密切相關的，完全也可以用遞歸來實現，一般來說跟使用棧是等價的，看一下相應的遞歸演算法也許有利於理解棧的作用：

def match_brackets(s, i):


    try to match brackets in string s from position i.

    return next start position if succeeded, raise ValueError if failed
    if s[i] == (:

        end_bracket = )

    elif s[i] == [:

        end_bracket = ]

    elif s[i] == {:

        end_bracket = }

    elif s[i] == &<:
        end_bracket = &>   # Introduce this for start-end match

    else:

        raise ValueError(Not match)

    i += 1

    while True:

        if s[i] == end_bracket:

            return i + 1

        else:

            i = match_brackets(s, i)
def is_match(s):

    try:

        s = .join(c for c in s if c in ((,[,{,},],)))

        match_brackets(&< + s + &>, 0)

    except ValueError:

        return False

    else:

        return True

is_match([^[](){}]*) is_match(3 * {3+ [4 - 6}])

過程調用和棧密切相關，進行一次遞歸調用就是一次進棧，進行一次返回就是一次出棧，過程中使用的臨時變數就是棧中存儲的數據，因此也不難將這個遞歸程序改寫成使用棧的程序了

用list的pop()，差不多就能完成你的需求了。

我第一次聽說棧也被嚇了一條，後來一聽概念就很容易懂了，就是一個「先進後出，後進先出」的業務邏輯，類似手槍彈夾：

第一顆被裝到彈夾裡面的子彈，是最後一顆打出來的。

python裡面的list本身就有棧的功能，append可以在尾部增加一個元素，pop可以從尾部取一個元素出來。

結合你的題目，你只需要依次循環字元串表達式：
1、發現一個左括弧，就append記錄下來。
2、發現一個右括弧，就先判斷一下最後一個是否屬於對應的括弧類型
如果是就pop移除最後一個；
如果不符合，當然就報錯了。

寫了個示例給你，不推薦你直接使用，希望你能看懂自己寫一遍：

a=3 * {3+ [4 - 6]}


def test(strexp):
    check = []

    i = 0

    err = 0
    for r in strexp:

        if r=={ or r==[ or r==(:

            check.append(r)

        if r==} or r==] or r==):

            if len(check)==0:

                err = 1

                break

            if (check[-1]=={ and r==}) or (check[-1]==[ and r==]) or (check[-1]==( and r==)):

                check.pop()

            else:

                err = 1

                break

        i += 1
    if err == 1:

        space =   * i

        print(

錯誤：

{}

{}↑ 這個括弧不合法..format(strexp,space))

    else:

        print({},表達式合法。.format(strexp))

test(a)

運行效果如下：

寫過一個Python的lisp解釋器，括弧匹配的原理就是遞歸堆棧，如果讀到最後沒有釋放就說明括弧不匹配，時間複雜度為O(n)。