Permalink
Switch branches/tags
Nothing to show
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
50 lines (47 sloc) 1.12 KB
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:
//用栈作辅助来模拟这个过程
//注意简化的部分,比如s.length()为0或者为奇数个时肯定不满足条件,还有当当前字符不在指定字符范围内时也可直接返回false
char symCharacter(char c)
{
switch(c)
{
case '(':
return ')';
case '[':
return ']';
case '{':
return '}';
default: //用返回'0'来标记当前字符无效
return '0';
}
}
bool isValid(string s)
{
stack<char> pstack;
if(s.length() == 0 || s.length() % 2 != 0)
return false;
for(int i = 0; i < s.length(); i++)
{
if(pstack.empty())
pstack.push(s[i]);
else
{
char c = pstack.top();
char t = symCharacter(c);
if(t== s[i])
pstack.pop();
else if(t == '0')
return false;
else
pstack.push(s[i]);
}
}
if(pstack.empty())
return true;
else
return false;
}