[LeetCode/easy] Valid-Parentheses (C++)

leetcode.com/problems/valid-parentheses/

Valid Parentheses - LeetCode

스택을 이용하여 괄호의 유효성을 판단하는 문제, 백준과 프로그래머스에서 많이 나온 유형입니다. (다른 점은 괄호의 종료가 소괄호, 중괄호, 대괄호 총 3가지라는 점) 아래의 세가지를 고려해주면 쉽게 해결할 수 있습니다.

 

1. 스택이 비어있는데 닫는 괄호가 오는 경우 : false
2. 스택에 값이 남아 있는 경우 : false
3. 여는 괄호와 닫는 괄호의 수가 다른 경우 : false

4. 나머지 : true

 

class Solution {
public:
    bool isValid(string s) {
        stack<int> st;
        int open = 0, close = 0;
        bool flag = true;
        
        for(auto c : s) {
            if(c == '(' || c == '{' || c == '[') {
                st.push(c);
                open++;
            } else if(c == ')' || c == '}' || c == ']') {
                close++;
                if(st.empty()) {
                    flag = false;
                    break;
                } else {
                    if(c == ')' && st.top() == '(') st.pop();
                    else if(c == '}' && st.top() == '{') st.pop();
                    else if(c == ']' && st.top() == '[') st.pop();
                }
            }
        }

        if(!flag || !st.empty() || open != close) return false;
        return true;
    }
};