The solution to this problem is surprisingly simple. So simple that some people actually solved this task in a text editor. Here is one possible complete implementation using sed:
sed -e '1d' -e '/^$/d' -e 's/[^0-9]//g' -e 's/^0*//' -e 's/^$/0/'The solution in human words: to produce the largest possible value, just keep all the digits (except for unnecessary leading zeros) and erase everything else.
Why does this work? The intuition behind this claim is that the numbers 40 − 7, 40 + 7, and even 40 ⋅ 7 are all smaller than the simple 470.
Now for a more formal argument.
First of all, note that if we take a valid expression and change all minuses into pluses, its value will not decrease. This is not a valid change in terms of our problem statement, but we will later erase all of those characters anyway, so it does not matter.
Next, the unary pluses can be safely erased. Thus, we are left with an expression with binary +s, binary *s and parentheses. Both + and * are nondecreasing functions on nonnegative integers: if we increase an argument, the result does not decrease.
The concatenation of nonnegative integers a and b has the value a ⋅ 10l + b, where l is the number of digits in b. We can now argue as follows:
a ⋅ 10l + b ≥ a ⋅ b + b ≥ a ⋅ b
a ⋅ 10l + b ≥ a ⋅ 1 + b = a + b
For example, instead of a ⋅ 935 it is always strictly better to do a ⋅ 1000 + 935.
Consider any expression that still contains some non-digit characters. Whenever you see an operator between two numbers, you may remove it without decreasing its value. Whenever you see parentheses around a single number, you may remove them as they have no effect anyway. After a finite number of such steps you will be left with no operators and no parentheses, just a single number.
Summary: We can start with any expression, apply the above sequence of steps, and end with just the string of digits. During those changes the value of the expression never decreased. Hence, the string of digits must be the expression with the largest possible value.
One final comment: If you did not see the trick, a valid solving strategy is to use brute force to solve the small subproblem – e.g., in Python you can easily generate all substrings and call eval on each of them (but you need to be careful because ** is exponentiation in Python). Once you get it accepted (to check that your answers are indeed correct), you can examine them and discover what’s going on.