引言

在編程中，括號(hào)匹配是一個(gè)常見問題，尤其是在處理數(shù)學(xué)表達(dá)式、編譯器解析等任務(wù)時(shí)。棧（Stack）是一種非常適合處理此類問題的數(shù)據(jù)結(jié)構(gòu)，因?yàn)闂＞哂?ldquo;后進(jìn)先出（LIFO）”的特性，能夠精確地管理括號(hào)的匹配問題。

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

問題描述

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

例如：

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

代碼講解

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

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

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

代碼解析

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

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

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

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

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

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

棧的狀態(tài)表示

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

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

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

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

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

測(cè)試

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

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

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

總結(jié)

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

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

最新評(píng)論