007 - 木変形パズル

さあ，パズルを始めよう!

最初に，算術式が与えられる．この算術式は，整数，演算子記号 + と −，そして括弧のみから構成される． (4−1)−(2+3)−(5+6) はこのような算術式の例である． よく知られているように，算術式の構造は，自然に木として表すことができる． 図 C-1 中の木は (4−1)−(2+3)−(5+6) を表現するものである．

この図の木で，各四角形は葉ノードであり，整数のラベルがついている． また，各円は葉以外のノードであり，演算子記号 + または − のラベルがついている． 葉ノードの値はそこについているラベルの整数値そのものである． 演算子記号 + を持つノードの値は，その子ノードの値の総和である． 演算子記号 − を持つノードの値は， その最左の子ノードの値から他の子ノードの値すべてを減じた差である． このように計算した根ノードの値は，与えられた算術式を通常の算術の規則に従って計算した値と，もちろん一致する．

このパズルで与えられる算術式を表すあらゆる木において，根ノードは 3 つの子ノードを持ち，根でも葉でもないノードは 1 つの親ノードと 2 つの子ノードを持つ． したがって，葉以外のすべてのノードは，ちょうど 3 つのノードと直接つながっている．

与えられた式に対応する木構造を，その全体または一部に対して以下の操作を何度でも繰り返すことで，変形することを考えよう．

• 葉以外のノードの 2 つの子ノードを入れ替える．
• 根ノードの最左 (または最右) の子ノードが葉ノードでないとき，そのノードを新しい根ノードとし，古い根ノードを新しい根ノードの最右 (または最左) の子ノードとする．

上で明示的に述べられているものを除き，これらの操作は，ノード間の親子関係を変えないし，同じ親を共有する子ノード間の左右の順序も変えない．

こうした操作を施した結果の木は，元とは違う算術式を表し，元とは違う値を持つかもしれない．このパズルのゴールは，上述の操作を繰り返し適用することで得られる式の値のうちの最大値を求めることである．

たとえば，図 C-1 において，葉ノード以外で最も左のノード（−のラベルがついたもの）の2つの子ノードを入れ替えると，図 C-2 の木が得られる．

ここで，図 C-2 において，根ノードの最左と最右の子ノードを入れ替えると，図 C-3 の木が得られる． 元の算術式 (4−1)−(2+3)−(5+6) の値は −13 であったが，図 C-2, C-3 の木が表す算術式の値は，それぞれ −19 と 9 になる．

さらに，図 C-3 の根ノードの最も左の子ノードを新しい根ノードとし，元の根ノードを新しい根ノードの最も右の子ノードにすると，図 C-4 の木が得られる． この木が表す算術式は 5+6+((2+3)−(1−4))，その値は 19 となり，これがこの例の場合に取りうる最大値である．

入力は複数のデータセットからなる． 各データセットは次に定義するroot式だけを含む 1 行である．

• root式は，3 個のnon-root式とこれらを区切る 2 個の加算記号 (+) または 2 個の減算記号 (−) からなる文字列である．
• non-root式は，数字 1 文字 (1 桁の整数を表す) であるか，2 個のnon-root式，これらを区切る 1 個の加算記号または減算記号，そしてこれらを囲む 1 個ずつの開き括弧と閉じ括弧からなる．

各データセットは，少なくとも 5 個の文字 (i.e. 3 個の数字と 2 個の記号) を含む． 入力の全データセットに含まれる文字数の合計は高々 500,000 である． 括弧のネストの深さが 100 を超えることはない．

入力の終わりは，−1 だけからなる行で表される．

各データセットについて，パズルの答えを 1 行で出力せよ．

  2+3+4
  2-3-4
  ((5-1)-1)-7-9
  (3+2)-(4-1)-(5+6)
  -1
  

  9
  -1
  7
  19