[Leetcode] 20. Valid Parentheses - C++

 

왼쪽 오른쪽 괄호가 짝이 맞는지를 검사하는 문제이다.

• 접근 방법
  1. 주어진 괄호 문자열의 현재 인덱스의 문자가 왼쪽 괄호`([{` 인지 확인
     • 맞다면 스택에 넣는다
     • 아니라면 2번으로
  2. 현재 스택이 비어있는지 확인
     • 비어있다면 false 얼리 리턴 -> `)}]` 이 먼저 왔으므로 짝이 맞지 않음
     • 비어있지 않다면 3번으로
  3. 현재 인덱스의 문자가 오른쪽 괄호`)]}` 인지 확인
     • 맞다면 스택의 top 문자가 짝이 맞는 왼쪽 괄호인지 체크
       • 맞다면 top 문자를 꺼내기(pop) -> 짝이 맞는 괄호
     • 아니라면 false 얼리 리턴 -> 짝이 맞지 않는 괄호
  4. 1~3번을 반복한 뒤 스택이 비어있는지 여부를 리턴

 

위 방법을 코드로 구현하면 아래와 같다.

 

#include <stack>

class Solution {
public:
    bool isValid(string s) {
        stack<char> stack;
        for(char ch: s) {
            if (ch == '(' || ch == '[' || ch == '{') {
                stack.push(ch);
            }
            else {
                if (stack.empty()) {
                    return false;
                }
                if ((ch == '}' && stack.top() == '{') ||
                    (ch == ')' && stack.top() == '(') ||
                    (ch == ']' && stack.top() == '[')) {
                    stack.pop();
                }
                else {
                    return false;
                }
            }
        }
        return stack.empty();
    }
};

 

새롭게 알게 된 것: c++ 라이브러리에 기본적으로 stack 자료구조가 구현되어 있다 (짱 편함!)