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

2504번: 괄호의 값

스택 자료구조 문제.

구현력을 필요로 하는 노가다 문제이다.

 

문제 분석

스택 하나에 입력들을 넣어놨다가, 괄호가 닫히는 경우를 처리해주면 된다.

나같은 경우에는 다음과 같이 처리했다.

• 현재 입력이 '(' 또는 '['인 경우
  -> 그냥 스택에 넣어준다.
  
  
• 현재 입력이 ')' 또는 ']'인 경우
  -> 만일 스택의 위에 있는 게 숫자들일 경우, 다 더해준 후 *2 / *3을 해준다.
  스택의 위에 있는 게 '(' / '[' 일 경우 '(' / '['를 빼내고 2를 넣어준다.
  이 때, 숫자들을 다 뺐을 때나 바로 최상위에서 문자를 확인할 경우,
  맞지 않는 조건인지(반대 문자는 아닌지) 확인해 주어야 한다.
• 또한 마지막에 스택 안을 확인해서 숫자만 다 더해주면 되는데,
  문자가 있는 경우에는 올바르지 못한 입력임을 처리해 주어야 한다.

 

또한 숫자의 범위가 1~9가 아니므로, 따로 처리해 주도록 해야 한다.

 

/*
* 백준 2504번 괄호의 값
* https://www.acmicpc.net/problem/2504
* 구현 / 자료구조 - 스택
*/
#include <iostream>
#include <stack>

using namespace std;

struct CalcStructure {
	int num;
	char c;
};

stack<CalcStructure> calcStack;
bool isInvalid;
int result = 0;

int main() {
	string input;
	cin >> input;

	for (int i = 0; i < input.length(); i++) {

		if (input[i] == '(') {
			calcStack.push({ -1, '(' });
		}
		else if (input[i] == ')') {
			if (calcStack.empty()) {
				isInvalid = true;
				break;
			}
			else {
				if (!calcStack.empty() && calcStack.top().num != -1) {
					int num = 0;
					while (!calcStack.empty() && calcStack.top().num != -1) {
						num += calcStack.top().num;
						calcStack.pop();
					}
					if (!calcStack.empty() && calcStack.top().c == '(') {
						num *= 2;
						calcStack.pop();
						calcStack.push({ num, '-' });
					}
					else {
						isInvalid = true;
						break;
					}
				}
				else {
					if (!calcStack.empty() && calcStack.top().c == '(') {
						calcStack.pop();
						calcStack.push({ 2, '-' });
					}
					else {
						isInvalid = true;
						break;
					}
				}
			}
		}
		else if (input[i] == '[') {
			calcStack.push({ -1, '[' });
		}
		else if (input[i] == ']') {
			if (calcStack.empty()) {
				isInvalid = true;
				break;
			}
			else {
				if (!calcStack.empty() && calcStack.top().num != -1) {
					int num = 0;
					while (!calcStack.empty() && calcStack.top().num != -1) {
						num += calcStack.top().num;
						calcStack.pop();
					}
					if (!calcStack.empty() && calcStack.top().c == '[') {
						num *= 3;
						calcStack.pop();
						calcStack.push({ num, '-' });
					}
					else {
						isInvalid = true;
						break;
					}
				}
				else {
					if (!calcStack.empty() && calcStack.top().c == '[') {
						calcStack.pop();
						calcStack.push({ 3, '-' });
					}
					else {
						isInvalid = true;
						break;
					}
				}
			}
		}
		else {
			isInvalid = true;
			break;
		}
	}

	while (!calcStack.empty()) {
		if (calcStack.top().num != -1) result += calcStack.top().num;
		else {
			isInvalid = true;
			break;
		}
		calcStack.pop();
	}

	if (isInvalid) {
		cout << 0;
	} else if (!isInvalid) {
		cout << result;
	}

	return 0;
}

 

분기 처리를 해야할 부분이 많아서 게시판을 많이 찾아서 해결할 수 있었다.