[LeetCode, 리트코드] Valid Parentheses

1. Problem

주어진 문자열은  '(', ')', '{', '}', '[', ']' 으로 이루어져 있다. 입력된 문자열이 유효한지를 판단하는 함수를 작성하라. 

주어진 문자열은 서로가 짝이 맞게 대칭적으로 이루어져야 유효하다. 예로들어 ( 는 결국에는 ) 와 매칭이 되어야하고 { 는 }와 매칭되어야 한다.

2. Solution

 

스택을 쓰면 풀 수 있는 간단한 문제다. 더 쉽게 푸는 방법은 왼쪽편에 해당하는 것들이 스택에 들어올려 할 때 오히려 이것을 오른쪽편에 해당하는 것으로 치환해서 넣는 것이다. 이런 방식으로 하면 연산이 훨씬 더 쉬워진다.

3. Code

class Solution {
public:
    bool isValid(string s) {
        if(s.size() == 0)
            return true;
        
        stack<char> st;
        for(char c : s){
            if(c == '('){
                st.push(')');   
            }
            else if(c == '{'){
                st.push('}');
            }
            else if(c == '['){
                st.push(']');
            }
            else {
                if(st.size() == 0 || st.top() != c)
                    return false;
                else
                    st.pop();
            }
        }
        
        return st.size() == 0 ? true : false;
    }
};