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.

括号匹配的问题，使用栈解决。（注意，访问栈元素时要先判断栈是否为空）

C++实现代码如下：

#include<iostream>
#include<string>
#include<stack>
using namespace std;

class Solution {
public:
    bool isValid(string s) {
        size_t index=0;
        stack<char> ss;
        while(index<s.length())
        {
            char c;
            switch(s[index])
            {
            case '(' :
            case '[' :
            case '{' :
                ss.push(s[index]);
                break;
            case ')' :
                if(ss.empty())
                    return false;
                c=ss.top();
                if(c!='(')
                    return false;
                ss.pop();
                break;
            case ']' :
                if(ss.empty())
                    return false;
                c=ss.top();
                if(c!='[')
                    return false;
                ss.pop();
                break;
            case '}' :
                if(ss.empty())
                    return false;
                c=ss.top();
                if(c!='{')
                    return false;
                ss.pop();
                break;
            default:
                return false;
            }
            index++;
        }
        if(index==s.length()&&ss.empty())
            return true;
        return false;
    }
};

int main()
{
    string str="]";
    Solution s;
    cout<<s.isValid(str)<<endl;
}

运行结果：

#include<string>
#include<iostream>
#include<stack>
using namespace std;

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

int main()
{
    Solution s;
    string str="((()))";
    cout<<s.isValid(str)<<endl;
}