開門見山，假設我們有一大串的由'{', '}', '[', ']', '(', ')' 這些括號構成比如像這樣的"{[}][()"符號串，我們肉眼當然能看出它是非法的，那么如何使用代碼來判斷是否合法呢？
其實我們可以借助堆疊來判斷這些符號串是否非法 ：
1.首先我們我需要建立符號的一對一映射,如下所示：
1 map<char, char> mp = {{')', '('}, {'}', '{'}, {']', '['}}; // 映射括號
2.我們對字串進行遍歷
1.如果能通過映射的鍵找到當前字符str[i]，我們就從堆疊頂彈出一個元素并獲取該元素，當然，如果是堆疊為空的清空的話，我們就為這個字符隨便賦個值，比如說賦值為 '@'，我們假記該變數為top_element，接下來我們看看是否能從當前字符str[i]映射所對應的值與top_element是否相同，若不同，則可以判斷該符號串為非法的，
2.若果找不到該字符str[i]映射的鍵，則先將其加入堆疊中，
3. 回圈結束 ，若堆疊為空則表示當前字串合法，若不為空，則表示當前字串非法
4. 可能光用語言描述不能只管表達，下面我們來看圖示，假設我們輸入了"()"字串，其具體程序如下:
5. 好了看完圖，接下來我們C++的代碼來描述一下該程序:
#include <iostream> #include <stack> #include <string> #include <map> using namespace std; class Solution { public: bool isValid(string s) { if (s == "") // 如果時空字串也合法 return true; if (s.size() == 1) // 只有一個字符肯定非法 return false; stack<char> st; map<char, char> mp = {{')', '('}, {'}', '{'}, {']', '['}}; // 映射括號 for (int i = 0; i < s.size(); i++) { if (mp.find(s[i]) != mp.end()) // 查找mp是否映射了該符號 { char top_ele = (st.size() == 0) ? '#' : st.top(); // 獲取堆疊頂元素，若為空則隨便設定一個字符 if (top_ele != '#') // 堆疊不為空則彈出元素 st.pop(); if (top_ele != mp.find(s[i])->second) // 如果這個元素被彈出的元素和mp對應映射的值不一樣，則直接回傳false return false; } else { st.push(s[i]); //壓入堆疊中 } } return st.size() == 0; // 如果堆疊為空則表示合法 } };
6. 注意代碼中map是直接用list初始化的，所以這段代碼必須在c++11下上的版本中才可以運行，
好了以上就是這次分享的全部內容了，如有錯誤還望斧正，我們下次見，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/73563.html
標籤：其他
上一篇：finalshell連接超時
下一篇：資料結構（一）—鏈表