백준 2504 괄호의 값

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

 

서론

상당히 까다로웠던 문제.

후위표기식으로 접근했으나 나로서는 해결할 수 없는 반례로 실패했다. 이후 계산 결과를 스택에 바로 넣고 푸는 방법을 다른 분의 풀이에서 확인 후 해결했다.

항상 느끼는거지만 처음부터 반례를 생각하지 않으면 결국에는 코드가 지저분해진다.

 

풀이

1. 입력문자열의 가장 왼쪽 괄호부터 하나씩 읽음

1.1 읽은 문자열이 왼쪽괄호인 경우 스택에 푸시

1.2 읽은 문자열이 오른쪽괄호인 경우

    스택의 탑이 짝이 맞는 왼쪽괄호인 경우 팝하고 괄호의 값(숫자)을 푸시

    스택안에 짝이 맞는 왼쪽 괄호보다 위에 숫자가 하나 있을 시 숫자와 괄호를 팝하고 숫자와 괄호를 곱한 후 푸시

    스택안에 짝이 맞는 왼쪽 괄호보다 위에 숫자가 여러 개 있을 시 팝한 숫자들을 더한 후 괄호를 팝하고 더해진 숫자와 괄호를 곱한 후 푸시

3. 입력문자열을 다 읽었으면 스택에 있는 수들을 덧셈

4. 입력문자열의 오류처리

 

예제 : (()[[]])([])

* 이해를 돕기 위해 스택에 삽입할 필요가 없는 경우도 삽입하여 실제 코드와는 약간의 차이가 있습니다.

 

Stack 1

(
(	(
(	(	)
(	2
(	2	[
(	2	[	[
(	2	[	[	]
(	2	[	3
(	2	[	3	]
(	2	9
(	11
(	11	)
22
22	(
22	(	[
22	(	[	]
22	(	3
22	(	3	)
22	6
28

 

전체코드

//c++

#pragma warning(disable : 4996)

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

// ( : -1, ) : -2, [ : -3, ] : -4
using namespace std;

int inputStr[31];
int strIdx;
int result;
int flag;
stack<int>s;

void input() {
	char tmp[31];
	int i = 0;
	scanf("%s", &tmp);
	while (tmp[i] != NULL) {
		if (tmp[i] == '(') inputStr[i] = -1;
		else if (tmp[i] == ')') inputStr[i] = -2;
		else if (tmp[i] == '[') inputStr[i] = -3;
		else if (tmp[i] == ']') inputStr[i] = -4;
		i++;
	}
}

void calculation() {
	stack<int>tmpS;
	while (inputStr[strIdx] != NULL) {
		if (inputStr[strIdx] == -1 || inputStr[strIdx] == -3) s.push(inputStr[strIdx]);
		else if (s.size() == 0) break;
		else {
			if (s.top() == -1 && inputStr[strIdx] == -2) {
				s.pop();
				s.push(2);
			}
			else if (s.top() == -3 && inputStr[strIdx] == -4) {
				s.pop();
				s.push(3);
			}
			else {
				while (s.top() != -1 && s.top() != -3) {
					tmpS.push(s.top());
					s.pop();
					if (s.size() == 0) {
						flag = -1;
						break;
					}
				}
				if (s.size() != 0) {
					if (s.top() == -1 && inputStr[strIdx] == -4) break;
					else if (s.top() == -3 && inputStr[strIdx] == -2) break;
					s.pop();
				}
				if (tmpS.size() == 1) {
					if (inputStr[strIdx] == -2) s.push(tmpS.top() * 2);
					else if (inputStr[strIdx] == -4) s.push(tmpS.top() * 3);
					tmpS.pop();
				}
				else {
					int tmp = 0;
					while (!tmpS.empty()) {
						tmp += tmpS.top();
						tmpS.pop();
					}
					if (inputStr[strIdx] == -2) s.push(tmp * 2);
					else if (inputStr[strIdx] == -4) s.push(tmp * 3);
				}
			}
		}
		strIdx++;
	}
	
	while (!s.empty()) {
		if (flag == -1) {
			result = 0;
			break;
		}
		
		else if (s.top() == -1 || s.top() == -2 || s.top() == -3 || s.top() == -4) {
			result = 0;
			break;
		}
		
		result += s.top();
		s.pop();
	}
}

int main() {
	input();
	calculation();
	cout << result;
}