[BOJ]백준 2504번: 괄호의값/Stack

www.acmicpc.net/problem/2504

2504번: 괄호의 값

valid parentheses string(vps)를 활용하면서, 스택을 활용하는 전형적인 문제

여는괄호가 나오면 그대로 push하고, 닫는 괄호가 나올 때 pop한 뒤 다시 연산해서 스택에 push한다

 

정확히는, 위의 그림처럼

1. 여는 괄호가 나오면 기호를 구분해서 push( '('는 0, '['는 1)한다.

2. 닫는 괄호가 나오면 해당 괄호와 일치하는 여는 괄호가 나올 때 까지(중간 과정에 숫자가 있다면 숫자를 계속 더해서 저장) pop한 뒤, 중간 계산값에 *2 / *3을 해서 다시 push하면 된다.

 

마지막에는 스택에 남아있는 모든 값을 더해서 print하면 끝

나는 vps검사는 따로 해주었다

#include <iostream>
#include <string>
#include <stack>
using namespace std;
stack<int> s;
int ans;
string str;
bool vps() {
	stack<char> s;
	for (char c : str) {
		switch (c) {
		case '(':
		case '[':
			s.push(c);
			break;
		case ')':
		case ']':
			char t = c == ')' ? '(' : '[';
			if (s.empty())return false;
			char top = s.top(); s.pop();

			if (top != t)return false;
		}
	}
	if (s.empty())return true;
	return false;
}
int main() {
	cin >> str;
	if (!vps()) {
		cout << 0;
		return 0;
	}
	for (char c : str) {
		int num = 0;
		switch(c) {
			case '(':
				s.push(0);
				break;
			case '[':
				s.push(1);
				break;
			case ')':
				while (s.top() != 0) {
					num += s.top();
					s.pop();
				}
				s.pop();
				if (num)
					s.push(2 * num);
				else s.push(2);
				break;
			case ']':
				while (s.top() != 1) {
					num += s.top();
					s.pop();
				}
				s.pop();
				if (num)
					s.push(3 * num);
				else s.push(3);
				break;
		}
	}
	while (!s.empty()) {
		ans += s.top();
		s.pop();
	}
	cout << ans;
	return 0;
}