[1541]잃어버린 괄호

잃어버린 괄호 성공

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

2 초

128 MB

57352

29722

23616

51.429%

문제

세준이는 양수와 +, -, 그리고 괄호를 가지고 식을 만들었다. 그리고 나서 세준이는 괄호를 모두 지웠다.

그리고 나서 세준이는 괄호를 적절히 쳐서 이 식의 값을 최소로 만들려고 한다.

괄호를 적절히 쳐서 이 식의 값을 최소로 만드는 프로그램을 작성하시오.

입력

첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 많이 연속되는 숫자는 없다. 수는 0으로 시작할 수 있다. 입력으로 주어지는 식의 길이는 50보다 작거나 같다.

출력

첫째 줄에 정답을 출력한다.

예제 입력 1 

55-50+40

예제 출력 1 

-35

예제 입력 2 

10+20+30+40

예제 출력 2 

100

예제 입력 3 

00009-00009

예제 출력 3 

0

#include<stack>
#include<string>
#include<vector>
#include<iostream>
 
 
int main()
{
    std::stack<int> stack;
    std::string string;
    std::vector<int> nums;
    std::vector<char> _operators;
    std::cin >> string;
 
    int nums_index = 0;
 
    for (auto _ch : string)
    {
        if (0 <= _ch - '0' && _ch - '0' < 10)
        {
            stack.push(_ch - '0');
        }
        else
        {
            nums.push_back(0);
            int digit = 1;
            while (stack.size())
            {
                nums[nums_index] += stack.top() * digit;
                digit *= 10;
                stack.pop();
            }
            nums_index++;
            
            _operators.push_back(_ch);
        }
    }
 
    nums.push_back(0);
    int digit = 1;
    while (stack.size())
    {
        nums[nums_index] += stack.top() * digit;
        digit *= 10;
        stack.pop();
    }
    nums_index++;
 
    int sum = 0;
    bool minus_on = false;
    for (nums_index = 1; nums_index < nums.size(); nums_index++)
    {
 
        if (_operators[nums_index - 1] == '-')
        {
            minus_on = true;
        }
 
        if (minus_on)
        {
            sum -= nums[nums_index];
        }
        else
        {
            sum += nums[nums_index];
        }
    }
    sum += nums[0];
    std::cout << sum;
}

sollution

1. 어떻게 괄호를 묶을지 생각했다.

- 연산자를 처음 만난 뒤는 모두 괄호로 묶는 게 좋겠다는 생각이 들었다.

어차피 - 뒤는 모두 괄호로 묶을 수 있기 때문이다. 

 

2. 어떻게 연산자와 숫자를 분리할지 생각했다.

nums 변수와 _operators 변수를 따로 만들고 for문 돌리면 된다.

 

3.  두 자리 이상의 숫자를 어떻게 인식할지 생각했다.

스택에 넣고 다음 연산자를 만나거나 문자열의 끝을 만나면 nums에 반복문으로 계속 *10하며 더해준다.

 

4. 이제 구현할 차례. 아무 생각 없이 했다. 어떻게 했는지 생각도 안난다(...)