使用Python堆棧數(shù)據(jù)結(jié)構(gòu)處理括號(hào)平衡問(wèn)題

漫步云海澗 2021-10-21 15:24:17 瀏覽數(shù) (3416)

反饋

學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)，可以說(shuō)是學(xué)習(xí)編程非常重要的一部分。因?yàn)槊總€(gè)程序都需要使用數(shù)據(jù)，學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)有利于我們組織、管理和存儲(chǔ)數(shù)據(jù)。下面，和大家分享 Python 語(yǔ)言中常用的數(shù)據(jù)結(jié)構(gòu)之一的堆棧結(jié)構(gòu)，并嘗試解決括號(hào)平衡的問(wèn)題。

一、概述

首先，簡(jiǎn)單地介紹一下什么是堆棧（Stack）？

堆棧數(shù)據(jù)結(jié)構(gòu)可以說(shuō)是比較簡(jiǎn)單的幾種數(shù)據(jù)結(jié)構(gòu)其中一個(gè)，按照特定的順序來(lái)添加或者刪除元素。

堆棧數(shù)據(jù)結(jié)構(gòu)有一個(gè)特性：LIFO，也就是常說(shuō)的后進(jìn)先出。

這個(gè)特性就好比我們往箱子里放磚頭，先放進(jìn)去的就在下面，后放進(jìn)去的在上面。當(dāng)我們要取出磚頭，就會(huì)把最上面的磚頭，也就最后放入箱子的磚頭取出來(lái)。

大致的示意圖如下：

DownloadFile

放磚頭和取磚頭的行為在堆棧中也有相應(yīng)的兩個(gè)術(shù)語(yǔ)，分別是：入棧（push）和出棧（pop）。

二、平衡括號(hào)

接下來(lái)，就和大家說(shuō)一說(shuō)學(xué)習(xí)堆棧數(shù)據(jù)結(jié)構(gòu)，通常會(huì)遇到的一個(gè)問(wèn)題，平衡括號(hào)。

什么是平衡括號(hào)呢？當(dāng)你給出的一個(gè)式子里，每個(gè)左括號(hào)往后找都能找到一個(gè)右括號(hào)，兩兩成雙，直到?jīng)]有剩余的，就可以說(shuō)是括號(hào)平衡。如果，你先碰到了右括號(hào)，但是前面并沒(méi)有左括號(hào)來(lái)跟它匹配，那么這個(gè)式子就稱(chēng)不上是括號(hào)平衡。

一般在 Python 中實(shí)現(xiàn)堆棧數(shù)據(jù)結(jié)構(gòu)，往往會(huì)使用列表。

下面就分享一下關(guān)于這個(gè)問(wèn)題，我的解題思路，以及詳細(xì)代碼。

解題思路：

（1）要實(shí)現(xiàn)堆棧結(jié)構(gòu)，首先就要?jiǎng)?chuàng)建一個(gè)列表來(lái)裝載數(shù)據(jù)。

（2）將要判斷的式子進(jìn)行遍歷。

（3）如果遍歷到的是左括號(hào)的，那么就使用 insert 方法，從首位加入；如果是右括號(hào)，則進(jìn)行下一步判斷。

（4）如果列表里面是空的，那么直接返回一個(gè) False；如果不為空，則使用 pop 方法，從首位移除一個(gè)。

（5）循環(huán)遍歷結(jié)束后，再進(jìn)行一層判斷。如果列表為空，則返回True；否則，返回False。

詳細(xì)代碼：

def balanced(expression):
    items = []
    for i in expression:
        if i == "(":
            items.insert(0, i)
        elif i == ")":
            if items == []:
                return False
            else:
                items.pop(0)
        else:
            continue

    if items == []:
        return True
    else:
        return False
print(balanced(input()))