[바킹독의 실전 알고리즘] 0x08강 - 스택의 활용(수식의 괄호 쌍)

1. 수식의 괄호 쌍이란?

 

스택은 여러 문제 유형에서 활용이 됨. 대표적으로 수식의 괄호 쌍, 전위/중위/후위 표기법, DFS(깊이 우선 탐색), Flood Fill이 있음. 이 중 전위/중위/후위 표기법은 코테에서는 너무 지엽적인 부분이므로 해당 강의에서는 다루지 않을 예정!

 

수식의 괄호 쌍의 정의

 

주어진 괄호 문자열이 올바르게 매치가 되는 지 판단하는 문제.

 

2. 문제 해결을 위한 관찰 

 

'올바르게 매칭'를 한다는 것은 각 괄호가 짝이 맞을 때를 의미함. 하지만 하나의 괄호만 사용이 된다면 단순히 여는 괄호의 갯수 = 닫는 괄호 갯수이면 되겠지만, 여러 종류의 괄호가 사용이 된다면 닫힌 괄호가 들어왔을 때 가장 최근에 들어온 여는 괄호와 종류가 같아야 한다는 조건을 붙여야 함.

 

정리하자면! 

문자열을 앞에서부터 일어나갈 때, 닫는 괄호는 남아있는 괄호 중에서 가장 최근에 들어온 여는 괄호와 짝을 지어 없애버리는 명령이라고 생각해도 된다.🤩

차근차근 쌓고

닫힌 괄호가 나왔고 가장 뒤에 있는 열린 괄호와 종류가 같다면 뿅 삭제하면 됨

 

3. 문제 해결 방법

 

스택의 FILO 성질을 이용하면 이를 구현할 수 있음. 자세한 해결 방법은 아래와 같음. 

 

 

4. 연습 문제

 

백준 4949번 문제가 수식의 괄호 쌍 문제 예시!

(왜인지 모르겠지만 내 코드는 계속 에러가 나므로 추후 맞게 된다면 추가해보도록 하겠다.. ㅎㅎ..)

#include <bits/stdc++.h>
using namespace std;

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  while(true){
    string a;
    getline(cin, a);
    if(a == ".") break;
    stack<char> s;
    bool isValid = true;
    for(auto c : a){
      if(c == '(' || c == '[') s.push(c);
      else if(c == ')'){
        if(s.empty() || s.top() != '('){
          isValid = false;
          break;
        }
        s.pop();
      }
      else if(c == ']'){
        if(s.empty() || s.top() != '['){
          isValid = false;
          break;
        }
        s.pop();
      }
    }
    if(!s.empty()) isValid = false;
    if(isValid) cout << "yes\n";
    else cout << "no\n";
  }
}