백준 - 괄호의 값 (C++)

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

2504번: 괄호의 값

문제설명

괄호가 나오는 문제이다. 괄호가 나오는 문제는 왠만하면 스택을 사용하고, 여기서는 temp 변수가 핵심이다.

 

알고리즘

1. 열린 괄호가 나오면 stack에 push하고 괄호 모양에 따라 temp에 특정 값을 곱해준다. 분배 법칙이라 생각하면 이해하기 쉽다.

2. 닫힌 괄호가 나오면 바로전에 닫힌 괄호에 맞는 열린괄호가 있으면 result에 값을 더해주고 조건이 틀리면 break 한다. 또한, temp를 괄호 모양에 따라 특정 값을 나눠준다.

 

ex) (()[[]]) -> 2 * 2 + 2* 3 * 3 

주의사항

1. temp의 기능을 생각하기 어렵다. 생각해내기만 하면 쉬운 문제

구현

#define _CRT_SECURE_NO_WARNINGS 
#include<iostream>
#include<algorithm>
#include<limits>
#include<string>
#include<vector>
#include<stack>
using namespace std;

int main() {
	string str;
	cin >> str;
	stack<char> s;
	int temp = 1;
	int result = 0;
	bool flag = false;
	for (int i = 0; i < str.size(); i++)
	{
		if (str[i] == '(')
		{
			temp *= 2;
			s.push(str[i]);
		}
		else if (str[i] == '[')
		{
			temp *= 3;
			s.push(str[i]);
		}

		if (str[i] == ')')
		{
			if (str[i - 1] == '(')
			{
				result += temp;
			}

			if(s.empty() || s.top() == '[')
			{
				flag = true;
				break;
			}
			s.pop();
			temp /= 2;
		}
		else if (str[i] == ']')
		{
			if (str[i-1]== '[')
			{
				result += temp;
			}

			if (s.empty() || s.top() == '(')
			{
				flag = true;
				break;
			}
			s.pop();
			temp /= 3;
		}
	}

	if (!s.empty())
		flag = true;


	if (flag)
		cout << "0";
	else
		cout << result;

}