有效的括号

栈的解法（非哈希表解法）

#include<iostream>
#include<stack>
#include<string>
using namespace std;
class Solution {
public:
    bool isValid(string s) 
    {
        //获取字符串的个数
        int n = s.length();
        if (n == 0)
            return false;
        //如果字符串的个数是奇数，那么不可能完全匹配
        if (n % 2 != 0)
        {
            return false;
        }
        //初始化栈
        stack<char> st;
        //对字符串中每个字符都进行判断，如果产生失配就返回false
        for (int i = 0; i < n; i++)
        {
            //如果为下面的字符，则入栈，等待合适匹配字符
            if (s[i] == '('||s[i]=='['||s[i]=='{')
            {
                st.push(s[i]);
            }
            //如果不是上面三种字符中的一个，就弹出栈顶元素，判断是否匹配
            else
            {
                //弹出前，判断栈是否为空，如果为空，就表示失配
                if (st.empty())
                {
                    return false;
                }
                //不然弹出栈顶元素，进行匹配操作
                char temp = st.top();
                st.pop();
                //判断是否匹配可以用字典，可以用哈希表，
      /*          我这里查了一下asc码，发现()值为40 / 41，[]值为91 / 93，{}值为123 / 125，
                    并且使用asc码也能解决右括号在前的离谱情况，
                    因为右括号码值是一定大于左括号的，
                    只要不满足 栈顶元素加1或加2等于入栈元素 就不能抵消。*/
                if (s[i] == ')' && temp + 1 != s[i])
                    return false;
                if (s[i] == ']' && temp + 2 != s[i])
                    return false;
                if (s[i] == '}' && temp + 2 != s[i])
                    return false;
            }
        }
        //如果遍历完，栈不为空，表示失配
        if (!st.empty())
        {
            return false;
        }
        else 
        {
            return true;
        }
    }
};
void test()
{
    Solution s;
    string s1 = "()";
    bool ret=s.isValid(s1);
    if (ret)
    {
        cout << "true" << endl;
    }
    else {
        cout << "false" << endl;
    }
}
int main()
{
    test();
    system("pause");
    return 0;