AOJ2613 Unordered Operators

問題
二項演算子の優先度を自由に設定した時、以下のBNFで表される式から導かれる値の最大値を求めよ。ただし、結合性は左結合である。
<expr> ::= ( <expr> ) | <number> | <expr> <op> <expr>
<op> ::= + | - | *

解法
先に各二項演算子に対して優先度を決めておいて、構文解析をする。
読み込んだ二項演算子が同一の優先度を持つとき、同じ再帰のスタック上でfor文などで処理するようにする。
優先度に変化が現れるタイミングで再帰する。
あとは、3^3のパターンの優先度をすべて試して最大値を取れば解が求まる。

namespace solver {
string s;
char ops[3] = {'+','-','*'};
int priority[3];
int turn;
typedef string::const_iterator Iter;
Iter it;
 
void consume(char e) {
  assert(*it == e);
  it ++;
}
 
bool isconsume(char e) {
  if(*it == e) {
    consume(e);
    return true;
  }
  return false;
}
 
ll number() {
  assert(isdigit(*it));
  Iter end = s.end();
  stringstream ss(string(it, end));
  ll x; ss >> x;
  int size = to_string(x).size();
  while(size --) it++;
  return x;
}
 
// 1. solve operator priority
ll expr(int p) {
  if(p == 3) {
    if(isconsume('(')) {
      ll r = expr(0);
      consume(')');
      return r;
    }
    return number();
  }
 
  ll r = expr(p + 1);
 
  // 2. solve operator associativity
  auto condition = [&]() { return find(ops, ops+3, *it)-ops < 3 && priority[find(ops, ops+3, *it)-ops] == p; };
 
  while(condition())
    if(isconsume('+')) r += expr(p + 1);
    else if(isconsume('-')) r -= expr(p + 1);
    else if(isconsume('*')) r *= expr(p + 1);
     
  return r;
}
 
ll calc() {
  it = s.begin();
  ll r = expr(0);
  assert(it == s.end());
  return r;
}
 
bool set_piority() {
  int a = 0;
  rep(i, 3) rep(j, 3) rep(k, 3) {
    if(a++ == turn) {
      turn ++;
      priority[0] = i;
      priority[1] = j;
      priority[2] = k;
      return true;
    }
  }
  return false;
}
 
void solve() {
 
  cin >> s;
  ll ans = std::numeric_limits<ll>::min();
  while(set_piority())
    ans = max(ans, calc());
  cout << ans << endl;
}
 
}