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

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

反饋

學習數(shù)據(jù)結(jié)構(gòu)，可以說是學習編程非常重要的一部分。因為每個程序都需要使用數(shù)據(jù)，學習數(shù)據(jù)結(jié)構(gòu)有利于我們組織、管理和存儲數(shù)據(jù)。下面，和大家分享 Python 語言中常用的數(shù)據(jù)結(jié)構(gòu)之一的堆棧結(jié)構(gòu)，并嘗試解決括號平衡的問題。

一、概述

首先，簡單地介紹一下什么是堆棧（Stack）？

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

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

這個特性就好比我們往箱子里放磚頭，先放進去的就在下面，后放進去的在上面。當我們要取出磚頭，就會把最上面的磚頭，也就最后放入箱子的磚頭取出來。

大致的示意圖如下：

DownloadFile

放磚頭和取磚頭的行為在堆棧中也有相應的兩個術語，分別是：入棧（push）和出棧（pop）。

二、平衡括號

接下來，就和大家說一說學習堆棧數(shù)據(jù)結(jié)構(gòu)，通常會遇到的一個問題，平衡括號。

什么是平衡括號呢？當你給出的一個式子里，每個左括號往后找都能找到一個右括號，兩兩成雙，直到?jīng)]有剩余的，就可以說是括號平衡。如果，你先碰到了右括號，但是前面并沒有左括號來跟它匹配，那么這個式子就稱不上是括號平衡。

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

下面就分享一下關于這個問題，我的解題思路，以及詳細代碼。

解題思路：

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

（2）將要判斷的式子進行遍歷。

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

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

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

詳細代碼：

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()))