**一. 題目描述** Given a string containing just the characters ’(’, ’)’, ’{’, ’}’, ’[’ and ’]’, determine if the input string is valid.? The brackets must close in the correct order, ”()” and ”()[]” are all valid but ”(]” and ”([)]” are not. **二. 題目分析** 輸入一串括號字符串，僅僅包含 (]} 這三種括號。判斷輸入的括號字符串是不是合法的，合法的輸出true，不合法輸出false。要求”()”、”[]”、”{}”必須成對使用，或者是像”({[]})”這種層層嵌套但保持對稱的，也屬于合法。 這一題是典型的使用壓棧的方式解決的問題，解題思路如下： 1. 計數 i = 0 2. 根據字符指針取出括號字符串的當前字符，如果當前字符為空，跳到5 3. 如果當前字符是左括號( (]}這三種 )，直接壓入棧 4. 如果當前字符是右括號( )]}這三種 )，從棧中彈出一個元素，彈出的元素如果和當前字符匹配，i++，回到2；否則，返回false 5. 如果棧為空，返回true；否則返回false。 **三. 示例代碼** ~~~ #include <iostream> #include <stack> #include <string> using namespace std; class Solution { public: bool isValid(string const& s) { if (s.size() == 0) return false; stack<char> temp; for (size_t i = 0; i < s.size(); ++i) { if (s[i] == ')' || s[i] == ']' || s[i] == '}') { if (temp.empty()) return false; else { char k = temp.top(); temp.pop(); if ((k == '(' && s[i] != ')') || (k == '[' && s[i] != ']') || (k == '{' && s[i] != '}')) return false; } } else if (s[i] == '(' || s[i] == '[' || s[i] == '{') temp.push(s[i]); else return false; } return temp.empty(); // 只有當最后棧為空時才說明輸入字符串是有效的 } }; ~~~ 簡單的測試代碼： ~~~ #include "ValidParentheses.h" int main() { cout << "Please input a string (only the characters '(’, ’)’, ’{’, ’}’, ’[’ and ’]’): " << endl; string input; cin >> input; Solution s; bool result = s.isValid(input); cout.setf(ios::boolalpha); cout << "The result is: " << result << endl; system("pause"); return 0; } ~~~   **四. 小結** 這道題需要對括號字符串的每個字符都遍歷一遍，因此時間復雜度是O(n)。