ferinの競プロ帳

競プロについてのメモ

AOJ2613 Unordered Operators

問題ページ

解法

まず演算子の優先順序が*>+>-となっている場合のBNFを書いてみる。左再帰演算子の優先順序に気をつけつつ書くと以下のようになる。

<expr1> = <expr2> ['-' <expr2>]*
<expr2> = <expr3> ['+' <expr3>]*
<expr3> = <factor> ['*' <factor>]*
<factor> = '(' <expr1> ')' | <number> 

他の優先順序の場合についても同様にBNFを書ける。BNFにしたがって再帰構文解析を書けばよい。

#include <bits/stdc++.h>
 
using namespace std;
using ll = long long;
#define int ll
using PII = pair<int, int>;
 
#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
 
template<typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template<typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template<typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; }
template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); }

template<typename T> vector<T> make_v(size_t a) { return vector<T>(a); }
template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts) { 
  return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));
}
template<typename T,typename V> typename enable_if<is_class<T>::value==0>::type
fill_v(T &t, const V &v) { t=v; }
template<typename T,typename V> typename enable_if<is_class<T>::value!=0>::type
fill_v(T &t, const V &v ) { for(auto &e:t) fill_v(e,v); }

template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
  out<<'('<<a.first<<','<<a.second<<')'; return out;
}
template<typename T>
istream& operator >> (istream& is, vector<T>& vec){
  for(T& x: vec) {is >> x;} return is;
}
template<class T>
ostream &operator <<(ostream& out,const vector<T>& a){
  out<<'['; for(T i: a) {out<<i<<',';} out<<']'; return out;
}

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0}; // DRUL
const int INF = 1<<30;
const ll LLINF = 1LL<<60;
const int MOD = 1000000007;

char op[3] = {'+', '-', '*'};

int pos;
string s;

ll exprA1();
ll exprA2();
ll exprA3();
ll factorA();
ll exprB1();
ll exprB2();
ll factorB();
ll exprC1();
ll exprC2();
ll factorC();
ll exprD1();
ll factorD();
ll number();

ll exprA1() {
  ll ret = exprA2();

  while(pos < s.size()) {
    if(s[pos] == op[0]) {
      if(op[0] == '+') pos++, ret += exprA2();
      else if(op[0] == '*') pos++, ret *= exprA2();
      else if(op[0] == '-') pos++, ret -= exprA2();
    } else {
      break;
    }
  }
  return ret;
}

ll exprA2() {
  ll ret = exprA3();

  while(pos < s.size()) {
    if(s[pos] == op[1]) {
      if(op[1] == '+') pos++, ret += exprA3();
      else if(op[1] == '*') pos++, ret *= exprA3();
      else if(op[1] == '-') pos++, ret -= exprA3();
    } else {
      break;
    }
  }
  return ret;
}

ll exprA3() {
  ll ret = factorA();

  while(pos < s.size()) {
    if(s[pos] == op[2]) {
      if(op[2] == '+') pos++, ret += factorA();
      else if(op[2] == '*') pos++, ret *= factorA();
      else if(op[2] == '-') pos++, ret -= factorA();
    } else {
      break;
    }
  }
  return ret;
}

ll factorA() {
  ll ret;
  if(s[pos] == '(') {
    pos++;
    ret = exprA1();
    pos++;
  } else {
    ret = number();
  }
  return ret;
}

ll exprB1() {
  ll ret = exprB2();

  while(pos < s.size()) {
    if(s[pos] == op[0]) {
      if(op[0] == '+') pos++, ret += exprB2();
      else if(op[0] == '*') pos++, ret *= exprB2();
      else if(op[0] == '-') pos++, ret -= exprB2();
    } else if(s[pos] == op[1]) {
      if(op[1] == '+') pos++, ret += exprB2();
      else if(op[1] == '*') pos++, ret *= exprB2();
      else if(op[1] == '-') pos++, ret -= exprB2();
    } else {
      break;
    }
  }
  return ret;
}

ll exprB2() {
  ll ret = factorB();

  while(pos < s.size()) {
    if(s[pos] == op[2]) {
      if(op[2] == '+') pos++, ret += factorB();
      else if(op[2] == '*') pos++, ret *= factorB();
      else if(op[2] == '-') pos++, ret -= factorB();
    } else {
      break;
    }
  }
  return ret;
}

ll factorB() {
  ll ret;
  if(s[pos] == '(') {
    pos++;
    ret = exprB1();
    pos++;
  } else {
    ret = number();
  }
  return ret;
}

ll exprC1() {
  ll ret = exprC2();

  while(pos < s.size()) {
    if(s[pos] == op[0]) {
      if(op[0] == '+') pos++, ret += exprC2();
      else if(op[0] == '*') pos++, ret *= exprC2();
      else if(op[0] == '-') pos++, ret -= exprC2();
    } else if(s[pos] == op[1]) {
      if(op[1] == '+') pos++, ret += exprC2();
      else if(op[1] == '*') pos++, ret *= exprC2();
      else if(op[1] == '-') pos++, ret -= exprC2();
    } else {
      break;
    }
  }
  return ret;
}

ll exprC2() {
  ll ret = factorC();

  while(pos < s.size()) {
    if(s[pos] == op[1]) {
      if(op[1] == '+') pos++, ret += factorC();
      else if(op[1] == '*') pos++, ret *= factorC();
      else if(op[1] == '-') pos++, ret -= factorC();
    } else if(s[pos] == op[2]) {
      if(op[2] == '+') pos++, ret += factorC();
      else if(op[2] == '*') pos++, ret *= factorC();
      else if(op[2] == '-') pos++, ret -= factorC();
    } else {
      break;
    }
  }
  return ret;
}

ll factorC() {
  ll ret;
  if(s[pos] == '(') {
    pos++;
    ret = exprC1();
    pos++;
  } else {
    ret = number();
  }
  return ret;
}

ll exprD1() {
  ll ret = factorD();

  while(pos < s.size()) {
    if(s[pos] == op[0]) {
      if(op[0] == '+') pos++, ret += factorD();
      else if(op[0] == '*') pos++, ret *= factorD();
      else if(op[0] == '-') pos++, ret -= factorD();
    } else if(s[pos] == op[1]) {
      if(op[1] == '+') pos++, ret += factorD();
      else if(op[1] == '*') pos++, ret *= factorD();
      else if(op[1] == '-') pos++, ret -= factorD();
    } else if(s[pos] == op[2]) {
      if(op[2] == '+') pos++, ret += factorD();
      else if(op[2] == '*') pos++, ret *= factorD();
      else if(op[2] == '-') pos++, ret -= factorD();
    } else {
      break;
    }
  }
  return ret;
}

ll factorD() {
  ll ret;
  if(s[pos] == '(') {
    pos++;
    ret = exprD1();
    pos++;
  } else {
    ret = number();
  }
  return ret;
}

ll number() {
  ll ret = 0;
  while(pos < s.size() && isdigit(s[pos])) {
    ret *= 10;
    ret += s[pos]-'0';
    pos++;
  }
  return ret;
}

signed main(void)
{
  cin.tie(0);
  ios::sync_with_stdio(false);

  cin >> s;

  ll ans = LLONG_MIN;
  sort(op, op+3);
  do {
    pos = 0;
    ll ret = exprA1();
    chmax(ans, ret);
  } while(next_permutation(op, op+3));

  sort(op, op+3);
  do {
    pos = 0;
    ll ret = exprB1();
    chmax(ans, ret);
  } while(next_permutation(op, op+3));

  sort(op, op+3);
  do {
    pos = 0;
    ll ret = exprC1();
    chmax(ans, ret);
  } while(next_permutation(op, op+3));

  sort(op, op+3);
  do {
    pos = 0;
    ll ret = exprD1();
    chmax(ans, ret);
  } while(next_permutation(op, op+3));

  cout << ans << endl;

  return 0;
}

久々に構文解析かいたらfactor置く位置とか意味不明なバグらせ方をした。