[BOJ] 1541 잃어버린 괄호

Link https://www.acmicpc.net/problem/1541

Note

양수, +, -로 구성된 식에 적절한 괄호를 추가해 결과 값을 최소로 만드는 경우의 값을 출력한다.

-가 등장하는 순간 그 뒤에 + 식을 전부 괄호로 묶으면 괄호 안의 결과 값을 빼는 모습이 된다.
즉 -가 등장하기 전 까지의 합과, 등장한 후의 합을 빼면 그 결과 값은 항상 최소값이 된다.
굳이 어려운 점을 따지자면 문자열을 입력받아 연산자와 피연산자를 나누는게 어려운부분..?

알고리즘

1. 문자열을 입력받는다.
2. 문자열의 0번 인덱스부터 문자열의 길이만큼 반복한다.
   1. 현재 위치의 문자 값이 숫자인 경우 연산자를 만나기 전 까지 숫자로 바꾸며, 10진법에 맞는 형태의 계산 결과를 띈다.
   2. 현재 위치의 문자가 + 이면서, -가 발견되지 않았다면 앞 계산결과에 더한 후, 계산 결과로 저장한다.
   3. 현재 위치의 문자가 + 이지만, -가 발견이 됬었다면, 발견 이후의 계산 결과에 2 - 1 과정을 통해 구해진 값을 더한다.
   4. -가 발견이 되면, - 발견 플래그를 세운다.
3. 2에서 구한 발견 이전의 값에서 발견 이후의 값을 뺀 결과를 출력한다.

소스코드

#include <iostream>
#include <stack>
#include <cstring>

using namespace std;

const int MAX = 50;
char input[MAX+1];

int main()
{
	cin >> input;

	stack<int> opnd;
	bool foundMinus = false;

	int digit = 0;
	char oper = '+';
	for (int i = 0; true; i++)
	{
		if (input[i] == 0)
		{
			if (foundMinus)
				digit *= -1;

			opnd.push(digit);

			while (opnd.size() > 1)
			{
				int opnd1 = opnd.top(); opnd.pop();
				int opnd2 = opnd.top(); opnd.pop();

				opnd.push(opnd1 + opnd2);
			}
			break;
		}
		else if ('0' <= input[i] && input[i] <= '9')
			digit = (digit * 10) + (input[i] - '0');
		else
		{
			oper = input[i];

			if (foundMinus)
				digit *= -1;

			if (oper == '-')
				foundMinus = true;

			opnd.push(digit);
			digit = 0;
		}
	}

	cout << opnd.top(); 

	return 0;
}

2019-03-08 02:37:16에 Tistory에서 작성되었습니다.