Q：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.
这道题是括号匹配问题，考察的是栈的基本使用。
我定义了一个括弧的优先级表，若当前字符优先级大于栈顶字符（1），则弹出栈顶字符；若当前字符优先级小于栈顶字符（0），则当前字符入栈。最后观察栈是否为空，若为空，则括弧配对，否则不配对。优先级表如下图：
下面贴上代码：
?
#include#include using namespace std; class Solution { public: int replace(char c){ if (c == '(') return 0; if (c == ')') return 1; if (c == '[') return 2; if (c == ']') return 3; if (c == '{') return 4; if (c == '}') return 5; } bool isValid(string s) { if (s.length() == 0 || s.length() == 1) return false; int ch[6][6] = { { 0, 1, 0, 0, 0, 0 }, { 0, 0, 0, 0, 0, 0 }, { 0, 0, 0, 1, 0, 0 }, { 0, 0, 0, 0, 0, 0 }, { 0, 0, 0, 0, 0, 1 }, { 0, 0, 0, 0, 0, 0 } }; stack ss; for (int i = 0; i < s.length(); i++){ if (ss.empty()){ ss.push(s[i]); continue; } char c = ss.top(); if (ch[replace(c)][replace(s[i])]) ss.pop(); else ss.push(s[i]); } if (ss.empty()) return true; else return false; } }; int main() { Solution s; cout << s.isValid("()[]{}()") << endl; cout << s.isValid("(([]{}))") << endl; cout << s.isValid("([]}") << endl; return 0; }
?