LeetCode 20. Valid Parentheses

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.
解析：
给定一个字符串，考察字符串中的括号是否左右匹配。此题目直接考察数据结构中栈的思想，遇到”(“,”[“,”{“则入栈，遇到”)”,”]”,”}”则判断栈顶元素跟当前元素是否匹配，如果匹配则出栈，最终栈中元素为空则表示字符串符合要求。注意字符串为空的判断和栈为空的判断。这个题目思路不复杂，直接上代码吧。
[cc lang=”C++”]
class Solution {
public:
bool isValid(string s) {
bool flag = false;
if(s.empty())
return false;
stack specal_char;
int length = s.length();
for(int index =0; index < length; index ++) { char item = s[index]; if(item == '(' || item == '[' || item=='{') { specal_char.push(item); }else if(item == ')' || item == ']' || item == '}') { if(!specal_char.empty() && (item == ')' && specal_char.top() == '(' || item == ']' && specal_char.top() == '[' || item == '}' && specal_char.top() == '{')) { specal_char.pop(); }else { specal_char.push(item); } } } if(specal_char.size() == 0) { flag = true; } return flag; } }; [/cc]