Arithmetic Operators
Given an arithmetic expression containing '+', '-', '*' operators, generate a string by placing parenthesis in the given expression which will return the the maximum possible value of that expression.
eg: I/p ------- 8+4*2 O/p ------ ((8+4)*2) corresponding to a max value of 24
I/p ------- 5-8+7*4-8*9 O/p ------ (5 - ((8 + 7)*(4 - (8*9)))) corresponding to a max value of 1025.

Question

Arithmetic Operators

Given an arithmetic expression containing '+', '-', '*' operators, generate a string by placing parenthesis in the given expression which will return the the maximum possible value of that expression.

eg: I/p -------> 8+4*2 O/p ------> ((8+4)*2) corresponding to a max value of 24

I/p -------> 5-8+7*4-8*9 O/p ------> (5 - ((8 + 7)*(4 - (8*9)))) corresponding to a max value of 1025.

Accepted Answer

I solved this question using recursion by putting bracket at all possible places and evaluate the answer through recursion and found the maximum out of them.

Accepted Answer

We can solve this question by applying paranthesis at all places and then evaluating them using recursion and calculate the maximum answer.It is similiar to matrix chain multiplication concept but we have to maximise the expression.But in recursion we can see that there are lot of repeating subproblems that means answer of lot of substrings are calculating again and again ,so we can use dynammic programming approach here.We will store the result of each substring in map and if string in recursion is already evaluated, we return result from map instead of solving that again.

We will generate all the possible answers by paranthesizing the expression and find the maximum from them.Here is complete algorithm:

- Traverse the given string from start to end. -If character is operator then split the string and call recursion to substring (0 to i) where i is current index to get the all possible answers of substring before current index and store the result in vector.

-Also call recursion to substring (i+1 to lenght of string-1) where i is current index to get the all possible answers of substring after current index and store the result in another vector.

-Now combine all combinations of characters of both vectors by applying given operators on them individually

and push them in answer vector.

-And if only number is there in string we just push them in answer vector.

-Also store answer vector for current substring in map for memoisation.

-Now at last our answer vector will contain all possible outputs so we have to just find the maximum from answer vector.||ly you can find minimum also if question is modified to minimum.

Here is complete function code:

// Helper recursive method to get all possible result of given input string

// Will return vector of possible answers

vector util(string s,

map< string, vector > m) {

// If already calculated, then return from memo

if (m.find(s) != m.end())

return m[s];

vector ans;

for (int i = 0; i < s.size(); i++)

{

if (isOperator(s[i]))

{

// If character is operator then split and

// calculate recursively for left and right part

vector Pre = util(s.substr(0, i), m);

vector Suf = util(s.substr(i + 1), m);

// Combine all possible combination accpording to given operators // +, - and *

for (int j = 0; j < Pre.size(); j++)

{

for (int k = 0; k < Suf.size(); k++)

{

if (s[i] == '+')

ans.push_back(Pre[j] + Suf[k]);

else if (s[i] == '-')

ans.push_back(Pre[j] - Suf[k]);

else if (s[i] == '*')

ans.push_back(Pre[j] * Suf[k]);

}

// if input string contains only number then push that

// into res vector

if (ans.size() == 0)

ans.push_back(atoi(input.c_str()));

// Store in map so that input string is not

// evaluated again and again

m[input] = ans;

return ans;

}

// method to return all possible output

// from input expression

// input is given in form string s

int possibleResult(string s)

{

// map m is for memoisation

map< string, vector > m;

vector possible= possibleResultUtil(s, m);

int ans=INT_MIN

//find maximum from all possible answers

for(int i=0;i

{

if(possible[i]>ans) ans=possible[i];

}

return ans;

}

Top Cisco Networking Academy Software Developer interview questions & answers

Popular interview questions of Software Developer