Arithmetic Operators

Moderate
0/80
Average time to solve is 30m
profile
Contributed by
1 upvote
Asked in companies
WalmartHCL TechnologiesPaxcom

Problem statement

Given an arithmetic expression ‘EXP’ containing integer values separated by any of the three operators ‘ + ’, ‘ - ’ and ‘ * ’. You need to place parentheses in the given expression such that the value of expression gets maximized. Your task is to return the maximum value obtained.

For Example: 
If the Input Expression is 3*5+2, then the maximum value of ‘21’ can be obtained by placing the parentheses as 3*(5+2). So you need to return 21.
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line contains a single integer ‘T’ denoting the number of test cases to be performed.

The first line of each test case contains a string denoting the given expression.
Output Format: 
For each test case, return a single integer denoting the maximum value obtained from the given expression.
Note: 
You don't need to print anything, it has already been taken care of. Just implement the given function.
Constraints: 
1 <= T <= 5
1 <= |Exp| <= 100

Time limit: 1 sec
Sample Input 1:
2
7-3*4
6-9+8*5-9*10
Sample Output 1:
16
1451
Explanation Of Sample Input 1:
Test Case 1: The maximum value of the given expression will be obtained by placing parentheses as (( 7 - 3 )* 4 ).

We can verify that for any other placement of parentheses, we will get a value less than or equal to 16.

Test Case 2: By placing parentheses as ( 6 - ((9+8) * (5- (9*10)))), maximum value 1451 can be obtained.

We can verify that for any other placement of parentheses, we will get a value less than or equal to 1451.
Sample Input 2:
2
2-8*1-12
9+1+3*2
Sample Output 2:
90
26
Hint

Think of recursively dividing problems into sub-problems.

Approaches (3)
Recursion

The basic idea to solve this problem is to recursively place parentheses at all possible positions and find the maximum value obtained among all.

 

We can divide the input expression into smaller expressions recursively and find the maximum value.

 

If the input expression is ( EXP[ 0 ] opr EXP[ 1 ] opr EXP[ 2 ].............opr EXP[ n-1 ] ), then we can divide this expression into two as -

( EXP[ 0 ] opr……….opr EXP[ k-1 ] ) opr ( EXP[ k+1 ] opr……….opr EXP[ n-1 ] ). 

 

The input expression can be computed by first computing the two sub-expressions and then combining them based on the operator between them.

 

We can divide the expression into two expressions around all the operators in the expression.

For Example- If EXP = a + b * c -d then this can be divided into two expressions as ( a ) + ( b*c-d) , ( a+b ) * ( c-d), ( a+b*c) - d.

 

We will create a recursive function that will return an array of integers storing all the possible values that can be computed from the given expression by placing parentheses at all possible positions. The maximum value of all the values in this array will be the required answer.

 

Algorithm

 

  • Let FIND_MAX( EXP) be our recursive function.
  • Initialize a vector of integer 'RES' to store all the values obtained from the expression ‘EXP’.
  • Run a loop k: start  to end to divide the expression among all the operators
    • Initialize two vectors, 'LEFT_EXP' and 'RIGHT_EXP', that will store the result of left and right sub-expressions.
    • Recursively call for left and right sub-expressions.
      • 'LEFT_EXP' = FIND_MAX( substring of expression from 0 to k ).
      • 'RIGHT_EXP' = FIND_MAX( substring of expression from k+1 to end)
    • Now compute the result by combining every value in 'LEFT_EXP', with every value in 'RIGHT_EXP' using two loops.
    • The first loop points to every element in 'LEFT_EXP'. i = 0 to (size of ('LEFT_EXP') - 1)
      • The second loop points to every element in 'RIGHT_EXP', j = 0 to (size of ('RIGHT_EXP') - 1)
      • If EXP[ k ] = ‘+’, push 'LEFT_EXP'[ i ] + 'RIGHT_EXP'[ j ] to 'RES'
      • If EXP[ k ] = ‘-’, push 'LEFT_EXP'[ i ] - 'RIGHT_EXP'[ j ] to 'RES'
      • If EXP[ k ] = ‘*’, push 'LEFT_EXP'[ i ] * 'RIGHT_EXP'[ j ] to 'RES'
    • If size of 'RES' is ‘0’ i.e. no operator is present in ‘EXP’
      • Push the num in 'RES'
  • Return 'RES'.
  • Find the maximum value among all values in the 'RES' vector.
Time Complexity

O( N^N), where ‘N’ is the length of the given expression.

 

We are solving the problem recursively having exponential complexity. So the time complexity is O( N^N ).

Space Complexity

O( N ),  where ‘N’ is the length of the given expression.

 

We are using an extra array ‘res’ to store all the computed values. So the space complexity is O(N).

Code Solution
(100% EXP penalty)
Arithmetic Operators
Full screen
Console