'괄호의 값 스택'에 해당되는 글 1건

BOJ 괄호의 값 - 2504

www.acmicpc.net/problem/2504

괄호와 관련해서 원래 스택의 기본 문제가 짝이 지어지느냐 마느냐인데, 이 문제는 연산까지 더해집니다. 괄호는 (, ), [, ]를 사용하며 A와 B는 이미 연산된 수를 의미합니다. 연산의 규칙은 다음과 같습니다. 

1. () = 2

2. [] = 3

3. (A) = 2*A

4. [A] = 3*A

5 AB = A+B

스택을 이용하면서 연산까지 같이 하면서 집어넣어줘야합니다. 어떻게 할 수 있을까요? 입력 예를 보면서 어떻게 풀어나갈지 생각해봅시다.

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

큰 틀은 아래와 같은데요. 

1. 우리가 여는 괄호를 만나면 우선 스택에 집어넣습니다.

2. 닫는 괄호가 나오면 매칭되는 괄호가 나올때까지 이전에 계산한 수를 모두 더합니다. 그리고 여는 괄호가 '('이냐, '[' 이냐에 따라서 2를 곱하거나 3을 곱해서 다시 스택에 집어넣습니다.

3. 모든 괄호를 전부 만났다면 스택에 있는 모든 수를 더합니다.

이제 그림을 통해서 보도록 하겠습니다. 우선 처음 ( ( 는 여는 괄호이므로 전부 스택이 집어 넣습니다. 이 후 최초로 닫는 괄호 )가 나오니 연산해서 다음 데이터를 집어넣을 차례입니다.

여는 괄호 (를 만날때까지 스택에 있는 모든 수를 더하지만 아직 더할 수는 없습니다. 그래서 ()에 해당하는 2를 집어넣습니다. 하지만 여기서는 음수로 집어넣지요. 다음 '[', '[' 역시 여는 괄호이기 때문에 스택에 집어넣습니다.

그 후 닫는 괄호 ']'가 나오니까 여는 괄호가 나올때까지 있는 수를 모두 더하고 3을 곱한 수를 넣어야하지만 없으므로 []에 해당하는 -3을 집어넣습니다. 그리고 다시 닫는 괄호 ]이 나오네요. 이때 이제 그 전에 더할 수 -3이 있지요. 

그래서 -3을 더하고 난 후 [X]에 해당하는 3을 곱해줍니다. -9가 되겠네요. 이 값을 다시 스택에 집어넣습니다. 다시 닫는 괄호 )가 나오면 앞에 있던 방법으로 모두 더한후 (X)에 해당하는 연산을 하면 -22가 스택에 들어가게 됩니다.

남아있는 ([])는 아래와 같이 연산됩니다. 

이제 괄호의 식이 전부 끝났죠? 그러면 스택에 남아있는 모든 수를 더하고 -1을 곱하면 그게 답입니다. 아래는 위의 풀이를 코드로 구현한 것입니다. 큰 틀은 이렇습니다. N은 문자열의 길이입니다. 여는 괄호가 나오면 모두 스택에 집어넣습니다. 닫는 괄호가 나오면 getNextSum()을 통해서 스택에 있는 모든 수를 더하고 난 이후 맞는 괄호에 해당하는 수를 곱한 값을 받아옵니다. 이후 이 값을 스택에 다시 집어넣죠.

stack<int> st;

int main() {
	char str[31];
	scanf(" %s", str);

	int N = strlen(str);
	for (int i = 0; i < N; i++) {
		char next = str[i];
		switch (next) {
			case '(':
			case '[':
				st.push(next);
				break;

			case ')':
			case ']':
			{
				int s = getNextSum(next);
				if (s == IMPOSSIBLE) {
					printf("0\n");
					return 0;
				}
				st.push(s);
				break;
			}
		}
	}
    
    //...//
 }

getNextSum() 함수는 아래와 같이 구현이 되었습니다. 만약 next에 해당하는 데이터가 문자(양수)라면 여는 괄호를 찾고 음수이면 그 수를 더합니다. 여기서 왜 숫자를 음수로 집어넣는지 이해가 가나요? 문자 자체도 ascii 코드로 숫자로 표시될 수 있기 때문에 문자와 숫자를 구분하기 위해서 음수로 집어넣었던 것입니다.

만약 아무런 값도 들어있지 않다면 (), []이기 때문에 -2나 -3을 출력해주면 되고 값이 있다면 모두 음수로 더해서 2, 3을 곱한 값을 출력해주면 됩니다. 이때 식은 (X) 이거나 [X] 에 해당합니다.

이때 매칭이 되지 않는 괄호는 impossibleOpen이라고 하며 스택을 돌다가 이 괄호가 걸리게 되면 IMPOSSIBLE이라는 -1을 반환합니다. 

#define IMPOSSIBLE -1
int getNextSum(char next) {
	int sum = 0;
	char open = next == ')' ? '(' : '[';
	char impossibleOpen = next == ')' ? '[' : '(';

	while (!st.empty()) {
		int prev = st.top();
		st.pop();
		if (prev == open) 
			return sum == 0 ? (next == ')' ? -2 : -3) : (next == ')' ? sum * (-2) : sum * (-3));
		
		if (prev == impossibleOpen)  return IMPOSSIBLE;
		
		sum -= prev;
	}
	
	return IMPOSSIBLE;
}

마지막 과정에는 스택에 괄호가 있는지 없는 지 검사한 후 괄호가 있으면 이 괄호식은 매칭이 되지 않는 식이므로 0을 출력하고 종료하면 되고, 그렇지 않고 숫자만 있는 상태면 모두 더해서 출력해주면 됩니다.

	int ans = 0;
	while (!st.empty()) {
		if (st.top() == '[' || st.top() == ']' || st.top() == '(' || st.top() == ')') {
			printf("0\n");
			return 0;
		}
		ans -= st.top();
		st.pop();
	}

	printf("%d\n", ans);

전체코드입니다.

#include <cstdio>
#include <stack>
#include <string.h>
using namespace std;

stack<int> st;
#define IMPOSSIBLE -1
int getNextSum(char next) {
	int sum = 0;
	char open = next == ')' ? '(' : '[';
	char impossibleOpen = next == ')' ? '[' : '(';

	while (!st.empty()) {
		int prev = st.top();
		st.pop();
		if (prev == open) 
			return sum == 0 ? (next == ')' ? -2 : -3) : (next == ')' ? sum * (-2) : sum * (-3));
		
		if (prev == impossibleOpen)  return IMPOSSIBLE;
		
		sum -= prev;
	}
	
	return IMPOSSIBLE;
}

int main() {
	char str[31];
	scanf(" %s", str);

	int N = strlen(str);
	for (int i = 0; i < N; i++) {
		char next = str[i];
		switch (next) {
			case '(':
			case '[':
				st.push(next);
				break;

			case ')':
			case ']':
			{
				int s = getNextSum(next);
				if (s == IMPOSSIBLE) {
					printf("0\n");
					return 0;
				}
				st.push(s);
				break;
			}
		}
	}

	int ans = 0;
	while (!st.empty()) {
		if (st.top() == '[' || st.top() == ']' || st.top() == '(' || st.top() == ')') {
			printf("0\n");
			return 0;
		}
		ans -= st.top();
		st.pop();
	}

	printf("%d\n", ans);

}