백준 1541: 잃어버린 괄호/수학

문제

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

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

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

입력

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

출력

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

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <map>
#include <queue>
#include <algorithm>
#include <string>
using namespace std;

const int MAX=51;
string cal;
char opt[MAX];
int num[MAX]={0};

bool isMinus;

int main() {
    cin >> cal; // 식
    
    int num_idx=0, opt_idx=0, ans=0;
    isMinus=false;

    for(int i=0;i<cal.length()+1;i++){
        if (cal[i] == '-' || cal[i] == '+' ) {
            opt[opt_idx] = cal[i];
            num_idx++;
            opt_idx++;
        }
        else if (cal[i] == '\0') {
            num_idx++;
        } 
        else{
            num[num_idx] = num[num_idx] * 10 + (cal[i] - '0');
        }
    }

    ans += num[0];


    for(int i=0;i<opt_idx;i++){
        if(opt[i]=='-'){
            isMinus=true;
        }
        if(isMinus){
            ans -= num[i+1];
        }
        else{
            ans += num[i+1];
        }
    }
    cout << ans;
    return 0;
}

string 변수를 만들고 거기에 식을 받은 뒤, (C++은 그냥 cin으로 받아줄 수 있다. 이밖에도 getline(cin, 변수이름)으로 받을 수 있다. 그 뒤, 연산자 인덱스 따로, 숫자 인덱스 따로 만들어서 -나 + 연산자일 경우 연산자 배열에 넣어주고 숫자일 경우 숫자 배열에 넣어 주었고 특히, 마지막 문자열의 마지막 부분인 '\0' 조건문 또한 추가해줘서 총 숫자의 개수를 정확히 해주었다. 이때, 배열.length()에서 +1을 해주어야한다.

중간에 -가 있는 경우 결국 최솟값은 뒷 부분 모든 부분이 -가 된다.

예) 50+10-20+15-30+10 ⇒ 50+10-(20+15)-(30+10) = 50+10-20-15-30-10