PROBLEM STATEMENT
You are given a sequence of digits. You must insert either a '+' (addition) operator or a '*' (multiplication) operator between each pair of adjacent digits in such a way that minimizes the value of the resulting expression. The expression should be evaluated using the standard order of operations (multiplication has a higher precedence than addition).
You will be given a string sequence. Perform the procedure described above on the sequence and return the resulting expression. If there are several possible answers, return the one that comes first lexicographically. Note that '*' comes before '+' lexicographically.
DEFINITION
Class:OperationsArrangement
Method:arrange
Parameters:string
Returns:string
Method signature:string arrange(string sequence)
CONSTRAINTS
-sequence will contain between 2 and 50 characters, inclusive.
-Each character in sequence will be a digit ('0'-'9').
EXAMPLES
0)
"222"
Returns: "2*2+2"
The minimal result can be obtained in three ways: "2*2+2", "2+2*2" and "2+2+2". The first one comes first lexicographically.
1)
"322"
Returns: "3+2*2"
2)
"307"
Returns: "3*0*7"
3)
"391118571"
Returns: "3+9*1*1*1+8+5+7*1"
4)
"111221911212"
Returns: "1*1*1*2*2*1+9*1*1+2*1*2"