스택의 활용(수식의 괄호 쌍)

1. 문제 해결 방식

출처:https://blog.encrypted.gg/936

여는 괄호와 닫는 괄호의 쌍이 일치해야 된다. 

세번째의 경우 쌍은 일치하지만 닫는 괄호과 먼저 나왔기 때문에 닫는 괄호가 먼저 나오는 경우는 배제

 

출처:https://blog.encrypted.gg/936

괄호의 쌍은 일치하지만 종류가 다르기 때문에 위의 방식으로 풀면 해결하지 못함

가장 안쪽의 괄호부터 붙어있는 여는괄호와 닫는괄호를 지우는 방식으로 해결이 가능한데 배열로 구현할 경우 짝을 찾과 제거하는 과정에서 모든 원소가 한 칸씩 이동하기 때문에 O(n*n)이고, 연결 리스트로 구현할 경우는 제거가 일어나도 주소값만 연결해주면 되기 때문에 O(n)이다. 

 

출처:https://blog.encrypted.gg/936

이 문제를 스택을 이용하면 더 쉽게 풀 수 있는데 맨 마지막에 들어온 괄호가 닫는 괄호인 경우 가장 최근에 들어온 여는 괄호와 종류가 일치하면 그 괄호를 pop하는 방식

 

이러한 명제를 참이라고 가정하고 이에 대한 반증이 있는지 찾아보자

닫는 괄호가 나왔는데 가장 최근에 들어온 여는 괄호의 종류가 다르므로 명제는 참이 된다.

 

중괄호의 짝은 일치하지만 여는 소괄호의 짝이 없으므로 명제는 참이 됨

 

이전까지의 모든 괄호의 짝이 맞춰지고 맨 마지막에 닫는 괄호가 들어왔는데 짝이 없으므로 이것도 명제는 참이 된다.

 

출처:https://blog.encrypted.gg/936

 

2. 백준 4949

#include <iostream>
#include <string>
using namespace std;

class Stack {    
    wchar_t stack[100];
    int head;    

public:
    void setHead(int val) {
        this->head = val;
    }

public:
    void push(wchar_t val) {
        stack[head++] = val;
    }

    void pop() {
        --head;
    }

    wchar_t top() {
        return stack[head - 1];
    }

    int empty() {
        if (head == 0) return 1;
        else return 0;
    }

    // 입력된 문자열의 괄호 체크   
    int bracketChk(wchar_t val) {
        int result = 1;

        if (val == '(' || val == '[') {
            push(val);            
        }
        else if (val == ')') {            
            if (!empty() && top() == '(') {
                pop();                                
            }
            else {
                result = 0;
            }
        }
        else if (val == ']') {
            if (!empty() && top() == '[') {
                pop();
            }
            else {
                result = 0;
            }
        }        
        
        return result;
    }
};


int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);    

    Stack stack;            
    while (true) {
        string line;
        getline(cin, line); // 공백이 포함된 문자열 입력받기

        if (line == ".") {
            break;
        }
        
        stack.setHead(0);
        bool isVaild = true;
        for (int i = 0; i < line.length(); i++) {
            int result = stack.bracketChk(line[i]); 
            if (result == 0) {                
                isVaild = false;
                break;
            }            
        }  

        // 스택에 괄호가 남아있는 경우 쌍이 없다는 뜻
        if (!stack.empty()) {
            isVaild = false;
        }

        if (isVaild) {
            cout << "yes\n";
        }
        else {
            cout << "no\n";
        }
        
    }

    return 0;
}