Boj 2504) 괄호의 값

문제

백준 2504

설명

주어진 조건에 맞는 덧셈과 곱셈을 Stack 으로 구현할 수 있는가가 중요한 문제.

• 곱셈은 자기가 닫은 괄호 내에 적용됨
• 덧셈은 자기가 닫은 괄호 간에 적용됨

우리는 2개의 Stack 만 유지하면 됨.

• parentheses 를 저장할 Stack
• 게산한 값을 저장할 Stack
  • 괄호과 닫힐 때 우리는 Stack 의 두 값을 확인해야함.
  • 바로 Top() 은 곱셈을 위해
    • 텅 빈 경우가 예외적인 경우로 위 코드처럼 각 괄호에 맞는 값으로 대체됨.
  • 그 위의 또다른 Top() 은 덧셈을 위해

시간 복잡도

O(N)

코드

stack<int>  var_stack;
stack<char> char_stack;

void Push(char c)
{
	char_stack.push(c);
	var_stack.push(0); // local
}

void Pop(int v)
{
	int cur = var_stack.top();
	var_stack.pop();

	if (cur == 0) cur = v;
	else cur *= v;
	
	int local = var_stack.top();
	var_stack.pop();
	local += cur;
	var_stack.push(local);
	
	char_stack.pop();
}

int main()
{
	fastio;

	var_stack.push(0); // this stack value be a return value.
	
	string str;
	cin >> str;
	
	for (auto c : str)
	{
		if (c == '(' || c == '[')
			Push(c);
		else {
			if (char_stack.empty()
				|| (c == ']' && char_stack.top() != '[')
				|| (c == ')' && char_stack.top() != '('))
			{
				cout << 0; 
				return 0;
			}
	
			Pop(c == ']' ? 3 : 2);
		}
	}
	
	if (var_stack.size() > 1) cout << 0;  // '(', '[' is more than `)`, `]`.
	else cout << var_stack.top();
}