筆試題33. LeetCode OJ (20)

看到這個題的時候我們是否會記起點什麼呢？是不是很熟悉的感覺呢，沒錯就是括號匹配問題。我們知道後會立馬想起一個數據結構---棧。

(1).我們需要借助一個棧來保存括號的左邊部分找到右邊的部分時，找出棧頂元素，若兩者匹配，則刪除棧頂元素，繼續下一輪遍歷。

(2).如果當前元素是括號的右邊部分，但是卻不合棧頂元素匹配，則說明整個匹配失敗。

(3).需要注意的是，棧空的情況。最後是通過棧是否為空來判斷是否全部匹配，但是若找到右邊括號的時候，棧是空的，那麼我們也是可以直接返回false的。

代碼如下：

class Solution {
public:
    bool isValid(string s) 
    {
        int len=s.size();
        if(len == 0 )
        {
            return true;
        }
        //定義一個棧結構來實現判斷
        stack S;
        int begin = 0;
        while(begin < len)
        {
            if(s[begin] == '(' || s[begin] == '{' || s[begin] == '[')
            {
                S.push(s[begin]);
            }
            else if(s[begin] == ')' || s[begin] == '}' || s[begin] == ']' )
            {
                if(S.empty())
                { //此時棧空可以說明不匹配
                    return false;
                }
                char tmpch = S.top();
                if (s[begin] == ')' && tmpch == '('
					|| s[begin] == '}' && tmpch == '{'
					|| s[begin] == ']' && tmpch == '[')
                {
                    S.pop();
                }
                else
                {
                    return false;
                }
            }
            else
            {
                return false;
            }
            
            ++begin;
        }
        
        if(S.empty())
        {//全部匹配了棧才會為空
            return true;
        }
        return false;
    }
};