題目：括號涉及小括號()，中括號[]，大括號{},我們要求給定的字符串中時候括號是匹配的。[] ([ )]這樣不合法，{}[ ] {( {[ ]} )}是合法的。

解題思路:
核心是最近匹配，使用棧,消去法。如果合法，最后棧為空，因為兩兩配對成功，消除pop().

• 如果是左邊括號就進(jìn)棧。
• 如果是右邊括號：先判斷棧是否為空，然后查看棧頂元素pop()是否是匹配的左邊括號。如果是，彈出pop().

三種括號代碼雷同。

核心代碼如下：

switch (brackets[i]){case '(':S.push(brackets[i]);//左括號入棧break;case ')'://右括號看棧頂元素是否匹配if (S.empty() || S.top() != '(')//短路表達(dá)式return false;S.pop();break;}

完整運行代碼（學(xué)習(xí)時）：

// validator_brackets.cpp : 此文件包含 "main" 函數(shù)。程序執(zhí)行將在此處開始并結(jié)束。 #include "pch.h" #include <iostream> #include<stack> #include<string> using namespace std; //括號匹配 bool validator(const string &brackets) {stack<char> S;for (size_t i = 0; i < brackets.size(); ++i){cout << brackets[i] << " ";switch (brackets[i]){case '(':S.push(brackets[i]);break;case ')':if (S.empty() || S.top() != '(')//距離最近，并且使用短路表達(dá)式return false;S.pop();break;case '[':S.push(brackets[i]);break;case ']':if (S.empty() || S.top() != '[')return false;S.pop();break;case '{':S.push(brackets[i]);break;case '}':if (S.empty() || S.top() != '{')return false;S.pop();break;default: return false;//輸入有誤的情況}}return S.empty();//如果是空（匹配成功），返回真；如果非空，返回false；}int main() {std::cout << "Hello World!\n"; string brackets="(){[()]}";//cin >> brackets;cout << (validator(brackets) ? "括號成功匹配" : "括號不匹配或者輸入有誤") << endl;}

學(xué)習(xí)：

• 短路表達(dá)式
  if (S.empty() || S.top() != ‘[’) 如果棧S為空，直接跳過if語句，后面的S.top()!=’['不用看。

• bool函數(shù)返回值的學(xué)習(xí)，結(jié)合棧的特性
  return S.empty();//如果是空（匹配成功），返回真；如果非空，返回false；

• 條件運算符
  cout << (validator(brackets) ? “括號成功匹配” : “括號不匹配或者輸入有誤”) << endl;

【注意】
下面的代碼是有缺陷的：
區(qū)別在于： if(!S.empty()&&S.top()==’(’)的使用。
這種會檢測不出來’]'單個右側(cè)括號的情況。

class Solution { public:bool isValid(string s) {stack<char> S;if(s.size()==0)return true;else{for(size_t i=0;i<s.size();++i){switch(s[i]){case '(':S.push(s[i]);break;case ')':if(!S.empty()&&S.top()=='(')S.pop();break;case '[':S.push(s[i]);break;case ']':if(!S.empty()&&S.top()=='[')S.pop();break;case '{':S.push(s[i]);break;case '}':if(!S.empty()&&S.top()=='{')S.pop();break;}}return S.empty();}} };

Leetcode上AC代碼（做題時）:

class Solution { public:bool isValid(string s) {stack<char> S;if(s.size()==0)return true;else{for(size_t i=0;i<s.size();++i){switch(s[i]){case '(':S.push(s[i]);break;case ')':if(S.empty()||S.top()!='(')return false;S.pop();break;case '[':S.push(s[i]);break;case ']':if(S.empty()||S.top()!='[')return false;S.pop();break;case '{':S.push(s[i]);break;case '}':if(S.empty()||S.top()!='{')return false;S.pop();break;default: return false;}}return S.empty();}} };

【總結(jié)】
邏輯需要嚴(yán)謹(jǐn)，考慮問題需要全面。之前就沒有考慮空串的情況，沒有考慮單個右側(cè)括號的處理。

刷題刷少了。

總結(jié)

以上是生活随笔為你收集整理的栈的应用_括号匹配的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。