スタックとキュー:Validate Parenthesis

Validate Parenthesis
前言:現在のノードの解決はバックドライブノードに依存するという特性がある.
現在のノードでは、バックドライブノードが認識されないと、意味のある解は得られません.
このような問題はstack(またはstackに等しいいくつかの一時変数)によって行うことができる.
解決:現在のノードをスタックに入れてから、依存するすべてのノードの値まで後続ノードの値を見ます.
ノードがすべてそろっている場合は、スタックからノードの解をポップアップします.ある時、この過程を繰り返す必要さえある.
:依存する後続ノードが完全になるまで、現在のノードの計算結果をスタックに再入力します.
例を見てみましょう
Validate Parenthesis
Given a string containing just the characters'(',')','{','}','[',']',
determine if the input string is a valid parentheses string.
For example "(([]))"is valid,but "(]"or "(("is not.

bool isLeftPartheses(char c)
{
    return c == '(' || c == '{' || c == '[';
}

bool isMatchPartheses(char c, char s)
{
    switch(c)
    {
        case ')':
            return s == '(';
        case ']':
            return s == '[';
        case '}':
            return s == '{';
        default:
            return false;
    }
    
    return false;
}


bool isValidatePartheses(string str)
{
    stack cst;
    for(int i = 0;i < str.size();i++)
    {
        if(isLeftPartheses(str[i]))
        {
            cst.push(str[i]);
        }else{
            
            if(cst.empty() || !isMatchPartheses(str[i],cst.top()))
            {
                return false;
            }
            cst.pop();
        }   
    }
    
    //      true，                
    return cst.empty();
}