[C/C++] 백준 #2504 괄호의 값(스택)

괄호의 짝맞춤은 처음 언어를 배우면서 스택을 이용한 활용 사례로 많이 나오는 편입니다.  복합괄호 형태로 나오게 되는데요.  복합괄호가 아니라면 굳이 스택을 사용하지 않아도 됩니다.

 

brackets' value

 

이 문제는 단순한 괄호 짝 맞추기보다 어려운 문제입니다.

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

2504번: 괄호의 값

저는 일단 스택을 두가지 용도로 사용했습니다.  현재까지 계산된 결과를 저장하는 용도와 짝을 맞추는 용도로 썼습니다.

계산될 결과의 경우에는 양수값을 사용하였고, 짝을 맞추는 용도로는 -1과 -2값을 사용했습니다.

 

1) 괄호 열기가 들어오면 괄호 종류에 따라서 -1 또는 -2를 스택에 넣는다.

2) 괄호 닫기가 들어오면 스택의 값이 양수이면 그 값을 사용하고 아니면 1을 이용한다.

3) 스택에 추가 양수값이 있으면 해당값들을 더한다.

4) 괄호의 짝이 맞으면, 종류에 따라서 x2 또는 x3을 한다.

5) 결과를 스택에 저장한다.

 

제가 작성한 소스입니다.

//------------------------------------------------
//    baekjoon #2504
//        - by Aubrey Choi
//        - created at 2019-10-10
//------------------------------------------------
#include <stdio.h>

int main()
{
    int st[30], sp=0, t, i;
    char s[32];
    scanf("%s", s);
    for(i=0;s[i];i++)
    {
        if(s[i]=='(') st[sp++]=-1; else if(s[i]=='[') st[sp++]=-2;
        else if(s[i]==')' || s[i]==']')
        {
            if(sp==0) break;
            if(st[sp-1]>0) t=st[--sp]; else t=1;
            while(sp > 0 && st[sp-1]>0) t+=st[--sp];
            if(sp==0) break;
            if(s[i]==')'&&st[sp-1]==-1) t*=2, sp--;
            else if(s[i]==']'&&st[sp-1]==-2) t*=3, sp--;
            else break;
            st[sp++] = t;
        }
    }
    for(i=0, t=0;i<sp;t+=st[i++]) if(st[i]<0) sp=0;
    if(sp==0) puts("0"); else printf("%d\n", t);
}