引言

在編程中，括號匹配是一個常見問題，尤其是在處理數(shù)學(xué)表達式、編譯器解析等任務(wù)時。棧（Stack）是一種非常適合處理此類問題的數(shù)據(jù)結(jié)構(gòu)，因為棧具有“后進先出（LIFO）”的特性，能夠精確地管理括號的匹配問題。

本文將通過 C++ 代碼，詳細(xì)講解如何使用棧來實現(xiàn)括號匹配，它的原理是什么、邏輯結(jié)構(gòu)實現(xiàn)是怎樣的，并通過符號表示棧的狀態(tài)，幫助你理解棧的應(yīng)用。

問題描述

給定一個字符串，包含三種類型的括號：(, ), [, ]。我們需要判斷字符串中的括號是否正確配對。如果每個左括號都有對應(yīng)的右括號，并且括號的配對順序是正確的，則返回 true；否則返回 false。

例如：

• 輸入："[()]"，輸出：true
• 輸入："[(])"，輸出：false

代碼講解

#include "bits/stdc++.h"
using namespace std;

bool search(string str) {
    stack<char> s; // 創(chuàng)建一個棧來存儲左括號
    for(char c : str) { // 遍歷字符串中的每個字符
        if(c == '[' || c == '(') { // 如果是左括號，壓棧
            s.push(c);
        } else if(s.empty()) { // 如果是右括號，但棧為空，說明沒有匹配的左括號
            return false;
        } else if(c == ']' && s.top() == '[') { // 如果是右括號，且棧頂是左括號
            s.pop(); // 匹配成功，彈出棧頂元素
        } else if(c == ')' && s.top() == '(') { // 如果是右括號，且棧頂是左括號
            s.pop(); // 匹配成功，彈出棧頂元素
        } else {
            return false; // 如果右括號與棧頂不匹配，返回 false
        }
    }
    return s.empty(); // 如果棧為空，則所有括號匹配成功，返回 true；否則返回 false
}

int main() {
    cout << search("[])" ) << endl; // 測試輸入
    return 0;
}

代碼解析

1. 棧初始化
   在search函數(shù)開始時，我們創(chuàng)建了一個字符類型的棧 s，用于存儲遇到的左括號 '(' 和 '['。

2. 遍歷字符串
   我們通過 for (char c : str) 遍歷字符串中的每個字符。

3. 左括號處理
   如果當(dāng)前字符是左括號 '(' 或 '['，我們就將它壓入棧中。

4. 右括號處理
   如果當(dāng)前字符是右括號 ')' 或 ']'，我們首先檢查棧是否為空：

   • 如果棧為空，說明沒有匹配的左括號，因此返回 false。
   • 否則，我們檢查棧頂元素是否是對應(yīng)的左括號。如果匹配，則彈出棧頂元素，表示這對括號已經(jīng)匹配成功。
   • 如果不匹配，則返回 false，說明括號順序有誤。

5. 檢查棧是否為空
   遍歷結(jié)束后，如果棧為空，說明所有的括號都匹配成功了。否則，返回 false，表示還有未匹配的左括號。

棧的狀態(tài)表示

為了便于理解棧的變化，我們使用符號表示當(dāng)前棧的狀態(tài)。棧的元素從棧底到棧頂按順序排列。

示例 1：輸入 "[()]"

1. 初始狀態(tài)：棧為空：[]
2. 處理字符 '['，將其壓棧：['[']
3. 處理字符 '('，將其壓棧：['[', '(']
4. 處理字符 ')'，棧頂是 '('，匹配成功，彈出棧頂：['[']
5. 處理字符 ']'，棧頂是 '['，匹配成功，彈出棧頂：[]
6. 最終棧為空，所有括號匹配成功，返回 true。

示例 2：輸入 "[(])"

1. 初始狀態(tài)：棧為空：[]
2. 處理字符 '['，將其壓棧：['[']
3. 處理字符 '('，將其壓棧：['[', '(']
4. 處理字符 ')'，棧頂是 '('，匹配成功，彈出棧頂：['[']
5. 處理字符 ']'，棧頂是 '['，匹配成功，彈出棧頂：[]
6. 最終棧為空，所有括號匹配成功，返回 true，但實際上，括號順序錯誤，程序應(yīng)該返回 false。

測試

cout << search("[])" ) << endl; // 測試輸入

對于輸入 "[])"，程序的執(zhí)行過程如下：

1. 初始狀態(tài)：棧為空：[]
2. 處理字符 '['，將其壓棧：['[']
3. 處理字符 ']'，棧頂是 '['，匹配成功，彈出棧頂：[]
4. 處理字符 ')'，棧為空，表示沒有匹配的左括號，返回 false。

總結(jié)

通過這段代碼和符號化的棧狀態(tài)表示，可以清晰的了解棧在括號匹配中的應(yīng)用。棧的“后進先出”特性使得它非常適合解決括號配對問題。在實際編程中，棧還可以用于其他多種場景，比如函數(shù)調(diào)用管理、深度優(yōu)先搜索等。

以上就是C++使用棧實現(xiàn)括號匹配的代碼詳解的詳細(xì)內(nèi)容，更多關(guān)于C++棧實現(xiàn)括號匹配的資料請關(guān)注腳本之家其它相關(guān)文章！

最新評論