LeetCode 20: valid parenthese
在数据结构OJ上AC过原题
某人找不到那个OJ的网址了...

思路

运用栈stack来实现 stack简直为其而生
但是当时的stack是我自己实现的，STL的stack操作其实不是很熟练，这道题就顺便把STL库的stack过一下。

实现

class Solution {
public:
    bool isValid(string s) {
        stack<char> p_match;
        //printf("%d\n",s.size());
        for(int i = 0; i < s.size(); ++i)
        {//printf("for%c\n",s[i]);
            if(s[i] == '(' || s[i] == '[' || s[i] == '{')
            {
                p_match.push(s[i]);
                //printf("%c\n",s[i]);
            }
            else{
                if(p_match.empty()) return false;
                char temp = p_match.top();
                //printf("%c\n",temp);
                //printf("%c\n",s[i]);
                switch(temp){
                    case '(':
                        if(s[i] != ')') return false;
                        break;
                    case '[':
                        if(s[i] != ']') return false;
                        break;
                    case '{':
                        if(s[i] != '}') return false;
                        break;
                }
                p_match.pop();
            }
        }
        if(!p_match.empty()) return false;
        return true;
    }
};

改进

可以先判断size是否是偶数！！这样就少了最后的!empty()。
for里面的empty()不能少因为可能(]]左括号数量少于右括号数量啊，不可以想当然

bug

1. 当时写的时候确实是太久没写了惭愧...把pop()和top()操作都傻傻分不清orz，不过没事，我估计我不会再搞错了哈哈哈
2. 我还把switch给忘了捡起来了捡起来了