minimize-result-by-adding-parentheses-to-expression

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

Algorithms

You are given a 0-indexed string <code>expression</code> of the form <code>&quot;&lt;num1&gt;+&lt;num2&gt;&quot;</code> where <code>&lt;num1&gt;</code> and <code>&lt;num2&gt;</code> represent positive integers.

Add a pair of parentheses to <code>expression</code> such that after the addition of parentheses, <code>expression</code> is a valid mathematical expression and evaluates to the smallest possible value. The left parenthesis must be added to the left of <code>&#39;+&#39;</code> and the right parenthesis must be added to the right of <code>&#39;+&#39;</code>.

Return <code>expression</code> after adding a pair of parentheses such that <code>expression</code> evaluates to the smallest possible value. If there are multiple answers that yield the same result, return any of them.

The input has been generated such that the original value of <code>expression</code>, and the value of <code>expression</code> after adding any pair of parentheses that meets the requirements fits within a signed 32-bit integer.

&nbsp;
Example 1:

<pre>
Input: expression = &quot;247+38&quot;
Output: &quot;2(47+38)&quot;
Explanation: The <code>expression</code> evaluates to 2 * (47 + 38) = 2 * 85 = 170.
Note that &quot;2(4)7+38&quot; is invalid because the right parenthesis must be to the right of the <code>&#39;+&#39;</code>.
It can be shown that 170 is the smallest possible value.
</pre>

Example 2:

<pre>
Input: expression = &quot;12+34&quot;
Output: &quot;1(2+3)4&quot;
Explanation: The expression evaluates to 1 * (2 + 3) * 4 = 1 * 5 * 4 = 20.
</pre>

Example 3:

<pre>
Input: expression = &quot;999+999&quot;
Output: &quot;(999+999)&quot;
Explanation: The <code>expression</code> evaluates to 999 + 999 = 1998.
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>3 &lt;= expression.length &lt;= 10</code></li>
	<li><code>expression</code> consists of digits from <code>&#39;1&#39;</code> to <code>&#39;9&#39;</code> and <code>&#39;+&#39;</code>.</li>
	<li><code>expression</code> starts and ends with digits.</li>
	<li><code>expression</code> contains exactly one <code>&#39;+&#39;</code>.</li>
	<li>The original value of <code>expression</code>, and the value of <code>expression</code> after adding any pair of parentheses that meets the requirements fits within a signed 32-bit integer.</li>
</ul>