알고리즘 & BOJ 2504 괄호의값(C++)

1378 : 괄호의 값

제한시간: 1000 ms    메모리제한: 64 MB
해결횟수: 300 회    시도횟수: 937 회   

4개의 기호 ‘(’, ‘)’, ‘[’, ‘]’를 이용해서 만들어지는 괄호열 중에서 올바른 괄호열이란 다음과 같이 정의된다. 

(1) 한 쌍의 괄호로만 이루어진 ‘()’와 ‘[]’는 올바른 괄호열이다. 
(2) 만일 X가 올바른 괄호열이면 ‘(X)’이나 ‘[X]’도 모두 올바른 괄호열이 된다. 
(3) X와 Y 모두 올바른 괄호열이라면 이들을 결합한 XY도 올바른 괄호열이 된다. 

예를 들어 ‘(()[[]])’나 ‘(())[][]’ 는 올바른 괄호열이지만 ‘([)]’ 나 ‘(()()[]’ 은 모두 올바른 괄호열이 아니다. 우리는 어떤 올바른 괄호열 X에 대하여 그 괄호열의 값(괄호값)을 아래와 같이 정의하고 값(X)로 표시한다.

(1) ‘()’ 인 괄호열의 값은 2이다. 
(2) ‘[]’ 인 괄호열의 값은 3이다. 
(3) ‘(X)’ 의 괄호값은 2×값(X) 으로 계산된다. 
(4) ‘[X]’ 의 괄호값은 3×값(X) 으로 계산된다. 
(5) 올바른 괄호열 X와 Y가 결합된 XY의 괄호값은 값(XY) = 값(X)+값(Y) 로 계산된다.

예를 들어 ‘(()[[]])([])’ 의 괄호값을 구해보자. ‘()[[]]’ 의 괄호값이 2+3×3=11 이므로 ‘(()[[ ]])’의 괄호값은 2×11=22 이다. 그리고 ‘([])’의 값은 2×3=6 이므로 전체 괄호열의 값은 22+6 = 28 이다.

여러분이 풀어야 할 문제는 주어진 괄호열을 읽고 그 괄호값을 앞에서 정의한대로 계산하여 출력하는 것이다.

 

첫 째 줄에 괄호열을 나타내는 문자열(스트링)이 주어진다. 단, 그 길이는 1 이상, 30 이하이다.

첫째 줄에 그 괄호열의 값을 나타내는 정수를 출력한다. 만일 입력이 올바르지 못한 괄호열이면 반드시 0을 출력해야 한다.

[Copy] (()[[]])([])

[Copy] 28

[Copy] [][]((])

[Copy] 0

출처 : KOI 본선 2008 초4/중2

/**************************************************************
    Problem: 1378
    User: a132034
    Language: C++
    Result: Success
    Time:0 ms
    Memory:1740 kb
****************************************************************/
 
 
#include    <cstdio>
#include    <string>
#include    <iostream>
#pragma warning(disable:4996)
 
struct S
{
    int n;
    char p;
};
S st[33];
int top = 1;
int main()
{
    std::string s;
    std::cin >> s;
    int res;
 
    for (int i = 0; i < s.length(); ++i)
    {
        res = 0;
        if (s[i] == '(' || s[i] == '[')
            st[top++].p = s[i];
        else
        {
            if (s[i] == ')')
            {
                while (top > 1)
                {
                    top--;
                    if (st[top].p != 'n' && st[top].p != '(') //숫자도 아니고 (도 아닌 경우 
                    {
                        printf("0");
                        return 0;
                    }
                    if (st[top].p == '(')
                    {
                        st[top].p = 'n';
                        if (res == 0) res = 1;
                        st[top++].n = res * 2;
                        break;
                    }
                    res += st[top].n;
                }
            }
            else if (s[i] == ']')
            {
                while (top > 1)
                {
                    top--;
                    if (st[top].p != 'n' && st[top].p != '[') //숫자도 아니고 [도 아닌 경우 
                    {
                        printf("0");
                        return 0;
                    }
                    if (st[top].p == '[')
                    {
                        st[top].p = 'n';
                        if (res == 0) res = 1;
                        st[top++].n = res * 3;
                        break;
                    }
                    res += st[top].n;
                }
            }
        }
    }
    int result = 0;
    for (int i = 1; i < top; ++i)
    {
        if (st[i].p != 'n')
        {
            printf("0"); 
            return 0;
        }
        result += st[i].n;
    }
    printf("%d", result);
 
    return 0;
}

BOJ 링크

괄호문제는 뭔가 언제부터인지 보자마자 스택을 이용해야겠다 하는 생각이 떠오른다. 

반복학습의 무서움인가... 

()와 []밖에 없으므로 코드가 그렇게 길지도 않다. 

열리는 괄호가 나오면 스택에 넣고 닫히는 괄호가 나오면 스택에서 확인해 본다. 

만약 짝이 안맞는다면 0을 출력하고 프로그램 종료. 아니라면 괄호에 맞추어 3이나 2를 곱해주고 더해주며 res 변수에 저장한다.