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

이번 게시글에서는 스택을 사용해 수식의 괄호 쌍이 올바르게 짝지어져 있는지 판별하는 문제를 해결하고자 한다. 

 

문제 해결을 위한 관찰

idea) 문자열을 앞에서부터 읽어나갈 때, 닫는 괄호는 남아있는 괄호 중에서 가장 최근에 들어온 여는 괄호와 짝을 지어 없애버리는 명령이라고 생각하자. 그리고 다음 그림을 보고 괄호 문제의 풀이법을 떠올려보자.

여는 괄호를 만나면 스택에 삽입하고, 닫는 괄호를 만나면 가장 최근에 들어온 여는 괄호를 삭제한다. 괄호가 담긴 문자열을 모두 읽었을 때, 스택에 남아있는 괄호가 없다면 모든 괄호가 짝을 이뤘다고 판단할 수 있다.

 

올바르지 않은 괄호 쌍을 가지는 경우는 다음과 같다:

1. 여는 괄호와 닫는 괄호의 짝이 맞지 않는 경우

2. 괄호 쌍의 수가 맞지 않는 경우

3. 닫는 괄호가 여는 괄호보다 먼저 등장하는 경우

 

문제 해결 방법

pseudo code)

1. 여는 괄호가 나오면 스택에 추가

2. 닫는 괄호가 나왔을 경우:

     i) 스택이 비어있으면 올바르지 않은 괄호 쌍임.

     ii) 스택의 top이 짝이 맞지 않는 괄호일 경우 올바르지 않은 괄호 쌍임.

     iii) 스택의 top이 짝이 맞는 괄호일 경우 pop 연산 수행.

3. 모든 과정을 끝낸 후 스택에 괄호가 남아있으면 올바르지 않은 괄호 쌍, 남아있지 않다면 올바른 괄호 쌍임.

 

구현 - BOJ 4949번

C++ code)

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

int main() {
    cin.tie(0);
    ios::sync_with_stdio(0);
    while (true) {
        string S;
        getline(cin, S); //C++에서 공백이 포함된 string을 입력받을 땐 getline을 사용한다.
        if (S == ".") break;

        stack<char> st; //STL stack 사용
        bool val = true; //맞는/틀린 문자열인지 판별하는 변수. true로 초기화.
        for (auto c : S) {
            if (c == '(' || c == '[') st.push(c); //여는 괄호이면 스택 st에 push한다.
            else if (c == ')') {
                if (st.empty() || st.top() != '(') {
                    val = false; //괄호가 맞지 않는 경우
                    break; //break문은 가장 가까운 do, while, for문을 한 번 탈출한다.
                }
                st.pop(); //괄호가 맞으면, val값은 초기화한 그대로 계속 true이다.
            }
            else if (c == ']') {
                if (st.empty() || st.top() != '[') {
                    val = false;
                    break;
                }
                st.pop();
            }
        }
        if (!st.empty()) val = false; //문자열을 모두 읽었는데 스택에 아직 값이 남아있으면 괄호쌍 틀림.
        if (val) cout << "yes\n"; //val값이 true이면 "yes" 출력
        else cout << "no\n";
    }
}