<p>You are given a <strong>0-indexed</strong> 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.</p>

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

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

<p>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.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> expression = &quot;247+38&quot;
<strong>Output:</strong> &quot;2(47+38)&quot;
<strong>Explanation:</strong> 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>

<p><strong class="example">Example 2:</strong></p>

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

<p><strong class="example">Example 3:</strong></p>

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

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<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>

class Solution {
public:
    string minimizeResult(string expr) {
        //First find the index of '+ in expresseion. let it be idx.
		int idx;
        int n=expr.size();
        for(int i=0;i<n;i++)
            if(expr[i]=='+')
            {
                idx=i;
                break;
            }
			
		//Now find two numbers which are on left and right side of '+' sign in expression	
        string num1 = expr.substr(0,idx);
        string num2 = expr.substr(idx+1,n-idx-1);
		
		//b1 and b2 are for brackets . b1=left bracket, b2=right bracket
        int b1=0,b2=0;
        int min =INT_MAX;
        string ans;
		
		//p1 and p2 are product number outside the brackets i.e our expresion is p1(sum)p2
        int p1,p2;
		
		//Find all possible conditions, iterate left bracket over num1 and right bracket over num2
        for(int b1=0;b1<num1.size();b1++)
        {
            for(int b2=0;b2<num2.size();b2++)
            {
                // s1 and s2 are strings which are outside the left parenthesis and right parenthesis respectively 
                string s1=num1.substr(0,b1);
                string s2=num2.substr(b2+1,b2-num2.size()-1);
               
               //if any of the string is empty then its int value should be 1 else its same as string.
			   if(s1.empty())
                    p1=1;
                else
                    p1=stoi(num1.substr(0,b1));
                if(s2.empty())
                    p2=1;
                else
                    p2=stoi(num2.substr(b2+1,b2-num2.size()-1));
					
				//sum stores the numerical value of the sum between the parenthesis	
                int sum=stoi(num1.substr(b1,num1.size())) + stoi(num2.substr(0,b2+1));
               //eval stores the numerical value of whole expression
			   int eval=p1*sum*p2;
			   
			   //if velue of expression is less then minimum, then make ans string = s1(sum) s1
                if(eval<min){
                    
                    min=eval;
                    ans=s1+"("+num1.substr(b1,num1.size())+"+"+num2.substr(0,b2+1)+")"+s2;
                
                }
                
            }
        }
        return ans;
        //return final string
        
    }
};
8500