[바킹독 알고리즘]0x08강 - 스택의 활용

0x00 수식의 괄호 쌍이란?

 

괄호를 빼놓고 봐도 위에껀 올바른 수식의 괄호 쌍이고 밑에껀 그렇지 않다는게 딱 눈에 들어올 것이다.

 

이와 같이 수식의 괄호 쌍이란, 주어진 괄호 문자열이 올바른지 판단하는 문제이다.

 

 

 

 

 

 

 

0x01 문제 해결을 위한 관찰

올바르게 문자열을 읽을때

 

 

 

 

 

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

 

문자열을 다 읽었고 남아있는 괄호가 없는 것으로 보아 모든게 다 짝이 잘 맞았다는걸 알 수 있다. 이처럼 올바른 괄호 쌍일 경우 여는 괄호를 읽을 때 마다 저장하다가 닫는 괄호를 읽을 때 가장 최근에 들어온, 즉 가장 끝에 있는 여는 괄호와 짝을 이루게 해주고 pop을 하면 올바른 괄호 쌍인지 확인할 수 있다.

 

 

 

 

올바르지 않은 괄호 쌍

짝이 맞지 않는 경우

닫는 괄호가 부족한 경우

여는 괄호가 부족한 경우

 

 

 

 

결론

 

앞에서 본대로 여는 괄호가 나오면 저장해뒀다가 닫는 괄호가 나오면 짝이 맞는지 확인한 후에 가장 최근에 들어온 여는 괄호를 제거하고 이런 식으로 진행을 하면 된다.

 

그리고 이 과정을 잘 생각해보면 가장 최근의 것이 가장 먼저 나오게 된다. 즉 FILO인거고 스택 자료구조를 이용해서 구현을 할 수가 있다. 그래서 과정을 구체적으로 정리해보면 이런 식이다.

 

여는 괄호가 나오면 스택에 추가하고, 닫는 괄호가 나오면 스택이 비어있거나 스택의 top이 짝이 맞지 않는 괄호인지를 먼저 확인한다. 여기서 걸리면 올바르지 않은 괄호 쌍인 거고, 짝이 맞는 괄호라면 pop을 해준다. 모든 과정을 끝낸 후에 스택이 비어있는지도 확인을 해줘야 한다.

 

 

 

 

 

 

 

0x03 연습문제

BOJ 4949번:균형잡힌 세상

 

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

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