[BOJ알고리즘, C++]#2504_괄호의 값, 스택, stack

#1. 문제

https://www.acmicpc.net/problem/2504

 

---

 

#2. 풀이

 

1. stack

[Basic C++] #64_stack

stack 컨테이너는 C++의 STL에서 제공하는 순차 컨테이너로, 후입 선출 방식으로 동작합니다. stack 컨테이너는 데이터 목록의 한쪽 끝에서만 접근/삽입/삭제 작업을 허용합니다.

 

2. 괄호 안에 있는 괄호, 바깥에 있는 괄호 구분

1. 먼저, 괄호 매칭을 확인하기 위해 stack 컨테이너를 활용합니다.
2. 문자열을 순화합니다.
3. 여는 괄호일 경우 stack 컨테이너에 삽입해줍니다.
4. 닫는 괄호일 경우, 두 가지로 나누어집니다.
5. 하나는 stack의 top()이 이에 매칭되는 여는 괄호일 경우, 스택에서 제거하고 대응되는 숫자 2 혹은 3을  삽입해 줍니다.
6. 다른 하나는, stack의 top()이 숫자일 경우, 여는 괄호가 나올 때까지 숫자들을 pop()해주고 누적합을 계산, 마지막으로 여는 괄호를 만나면 역시 pop() 해주고, 대응되는 숫자 2 혹은 3을 누적합에 곱해주어 결과 값에 더해줍니다. 

 

---

 

#3. 코드

#include <iostream>
#include <stack>
#include <string>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    string str;
    cin >> str;

    stack<int> s;
    bool isValid = true;

    for (char c : str) {
        if (c == '(' || c == '[') {
            s.push(c == '(' ? -2 : -3);  // 열린 괄호를 음수로 표시
        } else if (c == ')' || c == ']') {
            int sum = 0;
            while (!s.empty() && s.top() > 0) {
                sum += s.top();
                s.pop();
            }

            if (s.empty() || (c == ')' && s.top() != -2) || (c == ']' && s.top() != -3)) {
                isValid = false;
                break;
            }

            int multiplier = -s.top();
            s.pop();

            s.push(sum == 0 ? multiplier : sum * multiplier);
        } else {
            isValid = false;
            break;
        }
    }

    int result = 0;
    while (!s.empty()) {
        if (s.top() < 0) {
            isValid = false;
            break;
        }
        result += s.top();
        s.pop();
    }

    if (isValid) {
        cout << result << '\n';
    } else {
        cout << "0\n";
    }

    return 0;
}

 

---