【Valid Parentheses】cpp

题目：

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.

代码：

class Solution {
public:
    bool isValid(string s) {
            std::stack<char> result;
            for ( size_t i = 0; i < s.length(); ++i )
            {
                if ( s[i]=='(' || s[i]=='[' || s[i]=='{' ) 
                {
                    result.push(s[i]);
                    continue;
                }
                if ( result.empty() ) return false;
                char top = result.top();
                if ( s[i]==')' && top!='(' ) return false;
                if ( s[i]==']' && top!='[' ) return false;
                if ( s[i]=='}' && top!='{') return false;
                result.pop();
            }
            return result.empty();
    }
};

tips：

口诀：左号进栈，右号出栈；出栈判断是否正确。

===========================================

第二次过这道题，凭感觉写了一份代码，稍微冗长一些；修改了一次AC了。

class Solution {
public:
    bool isValid(string s) {
            stack<char> sta;
            int i = 0;
            while ( i<s.size() )
            {
                if ( s[i]=='(' || s[i]=='[' || s[i]=='{' )
                {
                    sta.push(s[i]);
                }
                else if ( s[i]==')' || s[i]==']' || s[i]=='}' )
                {
                    if ( sta.empty() ) return false;
                    if ( s[i]==')' )
                    {
                        if ( sta.top()=='(' )
                        {
                            sta.pop();
                        }
                        else
                        {
                            return false;
                        }
                    }
                    else if ( s[i]==']' )
                    {
                        if ( sta.top()=='[' )
                        {
                            sta.pop();
                        }
                        else
                        {
                            return false;
                        }
                    }
                    else
                    {
                        if ( sta.top()=='{' )
                        {
                            sta.pop();
                        }
                        else
                        {
                            return false;
                        }
                    }
                }
                else
                {
                    return false;
                }
                ++i;
            }
            return sta.empty();
    }
};

有个地方不要遗漏：如果是右号，要判断一下stack是否为空。