valid-parentheses

 

CREATED TIME: Dec 24, 2019 1:20 AM UPDATED TIME: Dec 25, 2019 11:33 PM 난이도: Easy

  • 2019-12-24

올바른 괄호 채크 문제. 간단히 stack으로 풀 수 있음.

https://leetcode.com/problems/valid-parentheses/

#include <stack>

class Solution {
public:
    bool is_valid_pair(char a, char b){
        if(a == '(' && b == ')'){
            return true;
        }else if(a == '{' && b == '}'){
            return true;
        }else if(a == '[' && b == ']'){
            return true;
        }else{
            return false;
        }
    }
    bool isValid(string s) {
        int len = s.length();
        stack<char> st1, st2;
        for(int i=0; i<len; i++){
            st1.push(s[i]);
        }
        
        while(!st1.empty()){
            char top = st1.top();
            if (st2.empty()){
                st2.push(top);
                st1.pop();
            }else{
                char st2_top = st2.top();
                if (is_valid_pair(top, st2_top)){
                    st1.pop();
                    st2.pop();
                }else{
                    st2.push(top);
                    st1.pop();
                }
            }
        }
        
        return st2.empty();
    }
};