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.
解题思路：
由于"()","[()]","{{({[]})}}"都会通过，即出现')]}'这种字符就需要判断前面字符是否是对应的字符，如果用指针的话，实现起来相当复杂，考虑到这种情况和栈的后进先出颇为相似，因此采用stack类
JAVA实现如下：
static public boolean isValid(String s) {
Stack<Integer> stack = new Stack<Integer>();
for (int i = 0; i < s.length(); i++) {
int pos = "()[]{}".indexOf(s.charAt(i));
if (pos % 2 !=0) {
if (stack.isEmpty() || stack.pop() != pos - 1)
return false;
} else
stack.push(pos);
}
return stack.isEmpty();
}
C++
class Solution {
public:
bool isValid(string s) {
stack<char> stk;
for (int i = ; i < s.length(); i++) {
if (s[i] == '(' || s[i] == '[' || s[i] == '{')
stk.push(s[i]);
else {
if (stk.empty())
return false;
if (stk.top() == '(' && s[i] == ')')
stk.pop();
else if (stk.top() == '[' && s[i] == ']')
stk.pop();
else if (stk.top() == '{' && s[i] == '}')
stk.pop();
else
return false;
}
}
return stk.empty();
}
};