Find the Minimum and Maximum values of given expression with + and *

Program to find the minimum and maximum values of given expression is discussed here. Given an algebraic expression with + and *, find the minimum and maximum values.

For example,

Sample Input:

1+2*3+4*5

Sample Output:

27
105

Explanation:

 1 + (2 * 3) + (4 * 5)  =  27 (Minimum)
(1 + 2) * (3 + 4) * 5  = 105 (Maximum)

Algorithm to find the minimum and maximum values of given expression with + and *

  • Separate the operators and numbers from the given expression.
  • Two 2D arrays are taken for storing the intermediate result which is updated.
  • Different parenthesization is tried among the numbers in accordance with the operators occurring between them.
  • Store the minimum value in the last cell of the 1st array and the maximum value in the last cell of the 2nd array.

Program to find the minimum and maximum values of given expression with + and * is given below.

/* C++ program to find the minimum and maximum values of given expression with + and * */

#include <bits/stdc++.h>
using namespace std;
bool isOperator(char op)
{
   return (op==’+’ || op==’*’);
}
void printMinAndMaxValueOfExp(string exp)
{
   vector num;
   vector opr;
   string tmp=””;
   for(int i=0;i<exp.length();i++)
   {
       if(isOperator(exp[i]))
       {
           opr.push_back(exp[i]);
           num.push_back(atoi(tmp.c_str()));
           tmp=””;
       }
       else
       {
           tmp+=exp[i];
       }
   }
   num.push_back(atoi(tmp.c_str()));
   int len=num.size();
   int minVal[len][len];
   int maxVal[len][len];
   for(int i=0;i<len;i++)
   {
       for(int j=0;j<len;j++)
       {
           minVal[i][j]=INT_MAX;
           maxVal[i][j]=0;
           if(i==j)
               minVal[i][j]=maxVal[i][j]=num[i];
       }
   }
   for(int L=2;L<=len;L++)
   {
       for(int i=0;i<len-L+1;i++)
       {
           int j=i+L-1;
           for (int k=i;k<j;k++)
           {
               int minTmp=0,maxTmp=0;
               if(opr[k]==’+’)
               {
                   minTmp = minVal[i][k] + minVal[k + 1][j];
                   maxTmp = maxVal[i][k] + maxVal[k + 1][j];
               }
               else if(opr[k] == ‘*’)
               {
                   minTmp = minVal[i][k] * minVal[k + 1][j];
                   maxTmp = maxVal[i][k] * maxVal[k + 1][j];
               }
               if(minTmp < minVal[i][j])
                   minVal[i][j] = minTmp;
               if(maxTmp > maxVal[i][j])
                   maxVal[i][j] = maxTmp;
           }
       }
   }
   cout<<minVal[0][len – 1]<<endl;
   cout<<maxVal[0][len – 1];
}
int main()
{
   string expression;
   cin>>expression;
   printMinAndMaxValueOfExp(expression);
   return 0;
}

Test Case 1

I/P
1+2*3+4*5
O/P
27
105

Test Case 2

I/P
10*20+30*40+50
O/P
1450
45000

Test Case 3

I/P
1*2+3*4+5
O/P
19
45

Test Case 4

I/P
1+8*9+5*1
O/P
78
126

Test Case 5

I/P
11+101*102
O/P
10402
20502