#16638: 괄호 추가하기 2(나중에 다시 풀어보기)

백준 16638번: 괄호 추가하기 2

문제:

길이가 N인 수식이 있다. 수식은 0보다 크거나 같고, 9보다 작거나 같은 정수와 연산자(+, -, ×)로 이루어져 있다. 곱하기의 연산자 우선순위가 더하기와 빼기보다 높기 때문에, 곱하기를 먼저 계산 해야 한다. 수식을 계산할 때는 왼쪽에서부터 순서대로 계산해야 한다. 예를 들어, 3+8×7-9×2의 결과는 41이다.

수식에 괄호를 추가하면, 괄호 안에 들어있는 식은 먼저 계산해야 한다. 단, 괄호 안에는 연산자가 하나만 들어 있어야 한다. 예를 들어, 3+8×7-9×2에 괄호를 (3+8)×7-(9×2)와 같이 추가했으면, 식의 결과는 59가 된다. 하지만, 중첩된 괄호는 사용할 수 없다. 즉, 3+((8×7)-9)×2, 3+((8×7)-(9×2))은 모두 괄호 안에 괄호가 있기 때문에, 올바른 식이 아니다.

수식이 주어졌을 때, 괄호를 적절히 추가해 만들 수 있는 식의 결과의 최댓값을 구하는 프로그램을 작성하시오. 추가하는 괄호 개수의 제한은 없으며, 추가하지 않아도 된다.

입력:

첫째 줄에 수식의 길이 N(1 ≤ N ≤ 19)가 주어진다. 둘째 줄에는 수식이 주어진다. 수식에 포함된 정수는 모두 0보다 크거나 같고, 9보다 작거나 같다. 문자열은 정수로 시작하고, 연산자와 정수가 번갈아가면서 나온다. 연산자는 +, -, * 중 하나이다. 여기서 *는 곱하기 연산을 나타내는 × 연산이다. 항상 올바른 수식만 주어지기 때문에, N은 홀수이다.

풀이:

문제가 너무 어려워서 답을 봐도 이해를 못 하겠다. 기초를 다지고 나중에 다시 풀어봐야겠다

코드:

#include <iostream>
#include <string>
#include <algorithm>
#include <stack>
#include <cstring>
#include <climits>
#include <map>
using namespace std;

const int MAX = 20;

int N;
int result = INT_MIN;
string s;
map<char, int> priority;
char parenthesis[MAX];

void setPriority(void)
{
	priority['('] = 2;
	priority['*'] = 1;
	priority['+'] = 0;
	priority['-'] = 0;
}

bool isNotParenthesis(int idx)
{
	return (parenthesis[idx] != '(' && parenthesis[idx] != ')');
}

bool isOperand(char c)
{
	return (c >= '0' && c <= '9');
}

int calculate(int a, int b, char op)
{
	switch (op)
	{
	case '+':
		return a + b;
	case '-':
		return a - b;
	case '*':
		return a * b;
	}
}

int calculatePostfix(string tempS)
{
	stack<int> postfixStack;

	for (int i = 0; i < tempS.size(); i++)
	{
		if (isOperand(tempS[i]))
		{
			postfixStack.push(tempS[i] - '0');

			continue;
		}

		if (postfixStack.size() >= 2)
		{
			int second = postfixStack.top();
			postfixStack.pop();
			int first = postfixStack.top();
			postfixStack.pop();

			int temp = calculate(first, second, tempS[i]);
			postfixStack.push(temp);
		}
	}

	return postfixStack.top();
}

int postfixResult()
{
	string tempS;
	stack<char> st;

	for (int i = 0; i < N; i++)
	{
		if (isOperand(s[i]))
		{
			tempS += s[i];
		}

		switch (parenthesis[i])
		{
		case '(':
			st.push('(');

			break;
		case ')':
			while (st.empty() == false && st.top() != '(')
			{
				tempS += st.top();

				st.pop();
			}

			st.pop();

			break;
		default:
			if (isOperand(s[i]))
			{
				break;
			}

			while (st.empty() == false && priority[st.top()] >= priority[s[i]]){
				if (st.top() == '('){
					break;
				}

				tempS += st.top();
				st.pop();
			}
			st.push(s[i]);
			break;
		}
	}

	while (st.empty() == false){
		tempS += st.top();
		st.pop();
	}
	return calculatePostfix(tempS);
}

void func(int idx){
	if (idx >= N){
		result = max(result, postfixResult());
		return;
	}

	for (int i = idx; i < N; i += 2){
		if (i >= N - 2){
			func(i + 1);
			continue;
		}

		if (isNotParenthesis(i) && isNotParenthesis(i + 2)){
			parenthesis[i] = '(';
			parenthesis[i + 2] = ')';
			func(i + 2);
			parenthesis[i] = ' ';
			parenthesis[i + 2] = ' ';
		}
	}
}

int main(void)
{
	cin >> N;
	cin >> s;

	setPriority();

	func(0);

	cout << result << "\n";

	return 0;
}