You are given a string expression of the form A+B, where A and B are non-empty strings of digits (no digit is '0'). You must insert exactly one pair of parentheses ( and ) into the expression such that:
-
The parentheses form a valid expression and
must include the plus sign
.
-
Any digits
outside
the parentheses remain adjacent to the parentheses and are interpreted as
multiplication
with the parenthesized sum.
More precisely, choose a split of A into A = L1 + L2 (concatenation) and a split of B into B = R1 + R2 such that the resulting value is:
-
If
L1
is empty, treat it as multiplicative factor 1; otherwise factor is integer value of
L1
.
-
If
R2
is empty, treat it as multiplicative factor 1; otherwise factor is integer value of
R2
.
Resulting value = factor(L1) * (int(L2) + int(R1)) * factor(R2).
Return the expression string with parentheses inserted that yields the minimum possible value. If multiple answers tie, return any one.
Example: input "435+122" could become something like "4(35+12)2" (not necessarily optimal).