Problem:###
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.
Solution:###
Very classic stack problem.
If meet any left parentheses, push it into stack.
If meet any right parentheses, check whether the top of the stack is the proper left parentheses. If valid, pop it. If not valid, return false.
Finally check whether the stack is empty. If it's not empty, then it's also invalid.
class Solution {
public:
bool isValid(string s) {
bool result = true;
if(s.size() == 0) return true;
stack<char> p;
for(int i = 0;i < s.size();i++)
{
if(s[i] == '(' || s[i] == '[' || s[i] == '{')
p.push(s[i]);
else
{
if (p.empty())
return false;
if (s[i] == ')' && p.top() == '(') p.pop();
else if (s[i] == ']' && p.top() == '[') p.pop();
else if (s[i] == '}' && p.top() == '{') p.pop();
else
return false;
}
}
if (!p.empty()) //important!!!!!!!
return false;
return result;
}
};
