[BOJ/C++] 2504 괄호의 값

문제

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

풀이

헤매다가 풀이 찾아봄ㅜ

( ( ) [[ ]] )
이 문자열은 2x(2+3x3)=22로 계산되는데, 이는 결국 (2x2)+(2x3x3)과 같음 => 분배법칙 이용

( : num에 2 or 3 곱한 뒤, 스택에 push
) : num에 2 or 3 나눈 뒤, 스택에서 pop
🥊 ( ( ) [[ ]] ) 빨간색으로 표시된 괄호처럼 바로 열고 닫고하는 형태일 경우, num을 나눠주기 전에 ans에 더해줌

Case 분류
1. case '('
num에 2를 곱하고 스택에 '(' 를 push 한다.

2. case ')'
  1) 스택이 비어있거나 스택 top이 '(' 가 아닌 경우
   올바르지 못한 괄호열이므로 0을 출력하고 return한다.

  2) 이전 문자열이 '(' 일 경우
   괄호 값이 '('이므로 계산된 num 값을 sum에 더한 후 num을 2로 나눈다. 스택을 pop 한다.

  3) 이전 문자열이 '(' 가 아닐 경우 
   제일 안쪽 괄호, 즉 '( )' 형태가 아니므로 이미 sum에 값이 더해져 있는 상태이다. 따라서 sum에 값을 더하지 않고 num을 2로 나눈다.
   그 후 스택을 pop 한다.

3. case'[' , ']'
1,2 번 케이스와 유사하게 처리한다.

코드

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

using namespace std;

int main() {
	string str;
	stack<char> s;
	int num = 1;
	int ans = 0;

	cin >> str;
	for (int i = 0; i < str.size(); i++) {
		if (str[i] == '(') {
			num *= 2;
			s.push(str[i]);
		}
		else if (str[i] == '[') {
			num *= 3;
			s.push(str[i]);
		}
		else if (str[i] == ')') {
			if (s.empty() || s.top() != '(') {
				cout << 0;
				return 0;
			}
			if (str[i - 1] == '(')
				ans += num;
			s.pop();
			num /= 2;
		}
		else { //str[i]==']'
			if (s.empty() || s.top() != '[') {
				cout << 0;
				return 0;
			}
			if (str[i - 1] == '[')
				ans += num;
			s.pop();
			num /= 3;
		}
	}

	if (s.empty())
		cout << ans;
	else
		cout << 0;


	return 0;
}