Description
Problem Introduction
In this problem, your goal is to add parentheses to a given arithmetic expression to maximize its value.
max(5 − 8 + 7 × 4 − 8 + 9) =?
Problem Description
Task.
Find the maximum value of an arithmetic expression by specifying the order of applying its arithmetic operations using additional parentheses.
Input Format.
The only line of the input contains a string s of length 2n + 1 for some n, with symbols S0, ..., S2n.
Each symbol at an even position of S is a digit (that is, an integer from 0 to 9) while each symbol at an odd position is one of three operations from {+,-,*}.
Constraints.
1 ≤ n ≤ 14 (hence the string contains at most 29 symbols).
Output Format.
Output the maximum possible value of the given arithmetic expression among different orders of applying arithmetic operations.
E.g. 1.
Input:
1+5
Output: 6
E.g. 2.
Input: 5-8+7*4-8+9
Output: 200
200 = (5 − ((8 + 7) × (4 − (8 + 9))))