[BOJ]16637_괄호 추가하기

컴파일러의 동작방식을 참고하여 동작을 구현하였습니다.

 

compiler가 text code를 읽을때 가상의 dot(bar)을 설정하여  keyword와 operation를 처리하는 flow를 떠올렸습니다.

 

문제에서 연산자 우선순위는 왼쪽부터 이므로 적용이 수월합니다.

expression에서 괄호를 적용 할 수 있는 가장 좌측의 operation의 앞에 | (bar)를 두고

괄호를 적용한것, 하지 않은것 두개의 expression으로 분화 시킵니다.

 

이때 동작이 종료되는 것은 bar가 operation의 가장 오른쪽 idx를 넘어 가는 것으로 확인 할 수 있습니다.

 

children expression을 queue에 넣어 bfs방식으로 구현하였습니다.

 

이때 괄호를 적용하지 않은 child는 단순히 bar를 한칸 오른쪽으로 옮기면 됩니다.

괄호를 적용한 child는 연산을 수행하여 bar의 index에 위치시키고

bar index의 operation과

bar+1 index의 number하나를 erase합니다.

이후 bar를 한칸 오른쪽으로 밉니다. (괄호를 연속적으로 적용 할 수 없기 때문입니다.)

 

3 |+ 8 * 7 - 9 * 2

 

=> 3 + 8 |* 7 - 9 * 2       //no braket expression

=> 11 * 7|- 9 * 2            //braket expression

 

동작이 끝난 expression은 vector에 push하여 나중에 한번에 계산하였습니다.

#include <iostream>
#include <vector>
#include <string.h>
#include <algorithm>
#include <queue>

using namespace std;

int N;
string exp_;
vector<int> num_;
vector<char> ops_;

typedef struct expression{
   vector<int> num;
   vector<char> ops;
   int bar;
}expression;

void input()
{
   cin>>N;
   cin>>exp_;
}

void init_num_ops()
{
   bool is_num = true;
   for(auto i : exp_)
   {
      if(is_num) num_.push_back(i - '0');
      else ops_.push_back(i);
      is_num = !is_num;
   }
}

int calc(vector<int> n, vector<char> o)
{
   int size = o.size();
   for(int l = 0 ; l < size ; l++)
   {
      switch (o[l]){
      case '+':{
         n[l+1] = n[l] + n[l+1];
         break;
      }
      case '-':{
         n[l+1] = n[l] - n[l+1];
         break;
      }
      case '*':{
         n[l+1] = n[l] * n[l+1];
         break;
      }
      }
   }
   return n[size];
}

int calc_one(int a, int b, char op)
{
      int ret;
      switch (op){
      case '+':{
         ret = a + b;
         break;
      }
      case '-':{
         ret = a - b;
         break;
      }
      case '*':{
         ret = a * b;
         break;
      }
      }
   return ret;

}
vector<expression> children(expression e)
{
   vector<int> n = e.num;
   vector<char> o = e.ops;
   int b = e.bar;

   vector<expression> ve;

   //add bracket
   vector<int> ab_n = n;
   vector<char> ab_o = o;
   ab_n[e.bar] = calc_one(n[e.bar], n[e.bar+1], o[e.bar]);
   ab_n.erase(ab_n.begin() + e.bar+1);
   ab_o.erase(ab_o.begin() + e.bar);
   int ab_b = e.bar+1;

   if(ab_b <= ab_o.size()+1)
      ve.push_back({ab_n, ab_o, ab_b});

   //no braket
   vector<int> nb_n = n;
   vector<char> nb_o = o;
   int nb_b = e.bar+1;

   if(nb_b <= nb_o.size())
      ve.push_back({nb_n, nb_o, nb_b});

   return ve;
}


void solve()
{
   init_num_ops();

   //bfs
   queue<expression> q;
   q.push({num_, ops_, 0});
   vector<expression> le;
   while(!q.empty())
   {
      expression e = q.front();
      q.pop();
      if(e.bar >= e.ops.size())
      {
         le.push_back(e);
         continue;
      }
         
      vector<expression> ve = children(e);
      for(auto e : ve)
         q.push(e);
   }

   int ans = 0x80000000;
   for(auto e : le)
         ans = max(calc(e.num, e.ops), ans);
   
   cout<<ans;
}

int main()
{
   input();
   solve();
}