TopCoder

Thumb hsnu2016
Adrien Wu
烏梭聯合王國,簡稱烏梭,為北佤羅善、安那海及佤羅善島弧國家之一。

User's AC Ratio

86.7% (13/15)

Submission's AC Ratio

60.0% (15/25)

Description

有一位間諜,依他所屬情報單位要求編碼方式,將他所收集到情報全部編成數字碼。但他認為這樣還是不夠安全,因此他再將這些數字字串,隨意切割成好幾個整數,然後將每個整數用一個數學算式來表示。這些算式只用了加、減、乘三種運算子,而且每個運算元都是正整數。最後,他為了讓他自己更為心安,他將整個密碼分成兩本密碼簿儲存。密碼本A存放這些數學算式,但他將算式內的所有括號全部拿掉,然後再將這些拿掉的括號資訊記錄在密碼本B裡面。
過了不久他返國述職,發現他把密碼本B弄丟了。再加上他的記憶力不好,很多情報內容根本記不得,所以現在沒了密碼本B幾乎束手無策。在不得已的情況下他的情報單位派了幾位心理與腦神經生理專家詢問他,希望能喚起他腦海內的記憶。這些專家試了好幾天,用盡各種心理生理辦法後,終於承認他的記憶力果真很差,怎麼也問不出情報內容。倒是心理學專家有一發現,即這位情報員在寫密碼算式時,傾向於將括號加在那些會讓算式得最大值的位置。例如5*7+2這個算式,有兩種括法:((5*7)+2)以及(5*(7+2)),第二種括法所得的值較大。請寫一程式,算出這些算式的可能最大值。

Input Format

每一筆輸入資料為一行算式,運算子只有三種即一般的加、減、乘三種二元運算子,分別以符號 "+"、"-"、"*" 表示。
每一個運算元都是一個正整數( ≤ 100),運算元和運算子之間不會有空白,一行算式不會有超過50個運算元。

Output Format

相對於每一輸入算式,輸出所有可能運算結果的最大值。該值都會是一個正整數,而且不會超過2147483647。

Sample Input

輸入範例1:
5*7+2

輸入範例2:
6*3-9*3

輸入範例3:
5+2-7*2-3

Sample Output

輸出範例1:
45

輸出範例2:
27

輸出範例3:
14

Hints

Problem Source

原TIOJ1145 / 95全國賽(prob 6)。

Subtasks

For Testdata: 0 ~ 0, Score: 20
For Testdata: 1 ~ 1, Score: 20
For Testdata: 2 ~ 2, Score: 20
For Testdata: 3 ~ 3, Score: 20
For Testdata: 4 ~ 4, Score: 20
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 30000 65536 65536
1 30000 65536 65536
2 30000 65536 65536
3 30000 65536 65536
4 30000 65536 65536