LeetCode : 20. Valid Parentheses

Stack을 사용하여 유효한 여부를 판단하기만 하면 된다.

 

[메인 로직]

닫는 괄호가 나오면, Stack의 top에 같은 종류의 여는 괄호가 나오지 않으면 invalid하다.

 

class Solution {
public:
    stack<char> S;
    bool check = true;
    
    bool isValid(string s) {
        for(int i=0; i<s.size(); i++){
            if(s[i]=='(' || s[i]=='{' || s[i]=='['){ // 열린 괄호
                S.push(s[i]);
            }else{ // 닫힌 괄호
                if(S.empty()){
                    check = false;
                    break;
                }
                
                if(s[i]==')'){
                    if(S.top()!='('){
                        check = false;
                        break;
                    }
                    S.pop();
                }else if(s[i]=='}'){
                    if(S.top()!='{'){
                        check = false;
                        break;
                    }
                    S.pop();
                }else{
                    if(S.top()!='['){
                        check = false;
                        break;
                    }
                    S.pop();
                }
            }
        }
        
        if(!S.empty()){
            check = false;
        }
        
        return check;
    }
};