ICPC Calculator

時間制限 : 8 sec, メモリ制限 : 262144 KB
英語版はこちら

ICPC 計算機

数学では,一般的に括弧を使って計算の順序を表現する. たとえば,7 × (3 + 2) は 3 + 2 を先に計算して, その結果を 7 に掛ける式であって,7 × 3 の結果に 2 を足す式ではない. しかし,世の中には括弧の存在を快く思わない人たちがいる. 国際反括弧会議 (International Counter of Parentheses Council) では,括弧を使わない記法を世界標準にしようとしている. 彼等は日夜括弧を使わない記法を研究している.

国際反括弧会議のメンバーである都九波博士は,括弧を使わない新しい記法を考案した. 博士が考案した記法では,加算演算子 (+),乗算演算子 (*),あるいは整数からなる行を並べて式を表す. 式は,整数ひとつか,被演算子への演算子の適用のどちらかである. 整数は十進数で 1 行に表記される. 演算子の適用の場合は,演算子の行を先に書き,直後の行から演算子が適用されるふたつ以上の被演算子を並べて書くことで表現する.被演算子は再帰的に同じ記法で表記した式である. 被演算子が演算子の適用である場合,被演算子が複数の行にわたることになる.

式はいくらでも入れ子になるので,どの演算子がどの被演算子に適用されるのかをわかるようにしなければならない. そのために,式には入れ子レベルを考える. 最上位の式は入れ子レベル 0 である. レベル n の式が演算子適用の場合,その被演算子はレベル n + 1 の式になる. 式の最初の行は入れ子レベルの数だけのピリオド (.) から始める.

例えば,通常の数学で 2 + 3 と書く式は図1 のように書く. 演算子はふたつ以上の被演算子に適用でき,+* はそれぞれ全ての被演算子の総和や,全ての被演算子を掛け合わせる演算を表す. 例えば,図2 は 2 と 3 と 4 を掛け合わせる式である. 複雑な例では,通常の数学での (2 + 3 + 4) × 5 は図3 のように書け, (2 + 3) × 4 × 5 は図4 のように書ける.

+
.2
.3
図1: 2 + 3

*
.2
.3
.4
図2: 2, 3, 4 を全て掛ける式

*
.+
..2
..3
..4
.5
図3: (2 + 3 + 4) × 5

*
.+
..2
..3
.4
.5
図4: (2 + 3) × 4 × 5

あなたの仕事は,博士を手伝ってこの記法で書かれた式の値を計算するプログラムを作ることだ.

Input

入力は複数のデータセットからなる. データセットの 1 行目は 1 以上の整数 n だけを含む行である. 引き続く n 行には都九波博士の考案した記法でひとつの式が書かれている.

式に含まれる整数は全て 1 桁であり,ひとつの式に含まれる整数は 9 個以下であると仮定してよい. また,入力される式は全て正確に博士の記法に従っていると仮定してよい. 入力に空白などの余分な文字や空行は含まれていない.

最後のデータセットの直後には,ひとつのゼロだけからなる行がある.

Output

各データセットについて,式の値のみからなる行を出力せよ.

Sample Input

1
9
4
+
.1
.2
.3
9
+
.0
.+
..*
...1
...*
....1
....2
..0
10
+
.+
..6
..2
.+
..1
..*
...7
...6
.3
0

Output for the Sample Input

9
6
2
54

Source: ACM International Collegiate Programming Contest , Japan Domestic Contest, Tsukuba, Japan, 2015-06-26
http://icpc.iisf.or.jp/2015-tsukuba/