leetcode Valid Parentheses

题目链接

valid-parentheses/

题目描述(Description)

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.

有效的括号

给一个字符串只包含'(', ')', '{', '}', '[' ']'，判断这个字符串时候合法。

括号必须按照规律匹配，如"()" "()[]{}" 都是合法的，但是"(]" 和 "([)]"不合法.

分析(Analysis)

用一个栈模拟，遇到左括号则压入栈，遇到右括号则与栈顶进行匹配，如果失配则返回false，如果匹配就弹出。如果没有右括号，返回false。最后，如果栈不为空，则说明还有左括号没有匹配，返回false，如果栈不为空，则说明所有括号都已经匹配返回true，最终返回st.empty()即可。

代码(Code)

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