[백준 16638] 괄호 추가하기 2

보자마자 자료구조 때 배운 스택을 이용한 계산기 만드는 과제가 생각났다.

그 방식을 적용하여 풀었다. 

자료구조에 나오는 스택 계산기는

1. infix -> postfix

2. postfix 를 통한 결과 

로 이루어지는 과정이다.

 

풀이과정

1. dfs를 통해 괄호를 친다. 

   1. 괄호가 중복될수 없기 때문에 괄호보다는 괄호 처리된 연산을 따로 우선순위만 높여주는 방식으로 마킹하였다.

      1. 괄호 처리 : 우선순위 1

      2. * : 우선순위 2

      3. +,- : 우선순위 3

   2. dfs를 끝까지 간 후 수식을 계산한다.

2. 수식계산법

   1. Infix -> postfix

      1. 피연산자가 들어오면 바로 postfix 벡터에 넣는다.

      2. 입력이 연산자인 경우에는

         1. 스택이 비었거나, 스택 top보다 우선순위가 낮은 인풋일 때까지 pop 한다. pop한뒤에는 postfix 벡터에 넣는다.

         2. 연산자를 push한다.

         3. 인풋을 다 받고도 스택이 비어있지 않은 경우 다 비울 때까지 다 postfix에 넣는다.

   2. postfix를 통한 결과 도출

      1. 피연산자는 무조건 스택에 집어넣는다.

      2. 연산자가 나온 경우 스택에서 2개를 뽑아 계산한다.

      3. 계산한 결과를 다시 push 한다.

      4. 마지막까지 계산한 뒤 스택에 남은 한 개가 결과이다.

3. 결과를 갱신하여 최댓값을 찾는다.

 

위와 같은 로직으로 계산한다면 쉽게 문제를 풀 수 있다. 근데 주의해야 될게 이문제에서는 결과가 음수가 나올 수도 있어서 max_result 초기화를 0으로 하면 안 되고 INT_MIN으로 해줘야지 문제가 생기지 않는다.

 

소스코드

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <stack>
#include <limits.h>
#define OPERAND 0
#define BRACKET 1
#define PLUS 3
#define MINUS 3
#define MUL 2
using namespace std;
 
typedef struct Formula {
    char symbol;
    int num;
    int priority;//괄호 : 1, * : 2, +,- :3 
    Formula(char s, int p) { symbol = s; priority = p; }
    Formula(int n) { num = n; priority = 0; }
}Formula;
 
int formula_size;
int max_result=INT_MIN;
 
int cal(int a, int b, Formula oper) {
    switch (oper.symbol)
    {
    case '+':
        return a + b;
    case '-':
        return a - b;
    case '*':
        return a * b;
    default:
        cout << "error";
        return 0;
    }
}
 
vector<Formula> InfixToPostfix(vector<Formula> infix) {
    vector<Formula> postfix;
    stack<Formula> s;
    for (int i = 0; i < formula_size; i++) {
        if (infix[i].priority == OPERAND) {// 피연산자
            postfix.push_back(infix[i]);
        }
        else { //연산자
            while (!s.empty() && s.top().priority <= infix[i].priority) {//스택이 비었거나, 스택 탑보다 우선순위가 낮은 인풋일때까지 pop
                postfix.push_back(s.top());
                s.pop();
            }
            s.push(infix[i]);
        }
    }
    while (!s.empty()) {
        postfix.push_back(s.top());
        s.pop();
    }
 
    return postfix;
}
int postfixToResult(vector<Formula> postfix) {//후위연산 -> 결과
    stack<Formula> s;
    int result = 0;
    for (int i = 0; i < formula_size; i++) {
        if (postfix[i].priority == OPERAND) {//피연산자
            s.push(postfix[i]);
        }
        else {// 연산자
            int operand1 = s.top().num;
            s.pop();
            int operand2 = s.top().num;
            s.pop();
            result = cal(operand2, operand1, postfix[i]);
            s.push(result);
        }
    }
    return s.top().num;
}
 
int calculateFormula(vector<Formula> infix) {
    vector<Formula> postfix = InfixToPostfix(infix);
    int result = postfixToResult(postfix);
    return result;
}
void dfs(int idx, vector<Formula> formula) {
    if (idx >= formula.size()) {
        //계산하기
        int result = calculateFormula(formula);
        max_result = max(max_result, result);
        return;
    }
    if (idx >=3 && formula[idx - 2].priority==1) {//이전 연산자에 괄호가 쳐진경우
        dfs(idx + 2, formula);
    }
    else {
        dfs(idx + 2, formula);
        formula[idx].priority = 1;
        dfs(idx + 2, formula);
    }
 
}
 
int main() {
    vector<Formula> formula;
    string s;
    cin >> formula_size;
    cin >> s;
    for (int i = 0; i < formula_size; i++) {
        if (i % 2 == 0) {//operand
            formula.push_back(Formula(s[i]-'0'));
        } 
        else {//Oper
            int prior;
            if (s[i] == '*')
                prior = MUL;
            else
                prior = 3;
            formula.push_back(Formula(s[i], prior));
        }
    }
    dfs(1, formula);
    printf("%d\n", max_result);
}

 

 

문제 링크 : https://www.acmicpc.net/problem/16638

16638번: 괄호 추가하기 2