[백준] 2504번 괄호의 값 (C++)

문제

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

 

이 문제는 아래의 규칙에 따라 ( , ) , [ , ] 로 이루어진 입력의 결과 값을 출력하는 문제이다.

 

규칙

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

이때, 올바르지 않은 괄호열일 경우 반드시 0을 출력한다.

풀이

이 문제를 실제 수식 연산처럼 풀이하기엔 괄호가 겹쳐있거나 했을 때, 변수가 많아 어려웠다.

ex) "(()[[]])([])" ▶ 2 * (2 + 3 * 3) + 2 * 3 = 28

 

그래서 실제 연산이 아닌 분배 법칙을 이용하여 이 문제를 풀이했다.

 

위 식을 분배 법칙으로 바꿔본다면 (2 * 2 +  6 * 3) + 2 * 3 ▶ 4 + 18 + 6 = 28 이므로 원하는 답이 나오게 된다.

 

이를 스택을 이용하여 풀이해봤다.

#include <bits/stdc++.h>

using namespace std;

int GetClose(char top, char push)
{
	if(top == '(' && push == ')') return 2;
	if(top == '[' && push == ']') return 3;
	return -1;
}
int GetOpen(char push)
{
	if(push == '(') return 2;
	return 3;
}
bool IsPlus(char prev, char cur)
{
	return  (prev == '(' && cur == ')') || (prev == '[' && cur == ']');
}

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

	string input;
	cin >> input;

	stack<char> stack;
	stack.push('0');
	int sum = 0, num = 1;
	for(int i = 0; i < input.length(); i++)
	{
		char c = input[i];
		if(c == '(' || c == '[')
		{
			num *= GetOpen(c);
			stack.push(c);
		}
		else
		{
			int val = GetClose(stack.top(), c);
			if(val == -1)
			{
				cout << 0;
				return  0;
			}
			if(IsPlus(input[i -1], c)) sum += num;
			num /= val;
			stack.pop();
		}
	}

	sum = stack.size() != 1 ? 0 : sum;
	cout << sum;
	return 0;
}