Arithmetic Operators

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.

Following is a partial recursion tree of the recursion approach for Expression = “5+14-2*8”

We can observe that in this partial recursion tree, (4,6) is solved two times. This problem of overlapped sub-problems can be solved by memoization. We will solve the problem as we did in the recursive approach and store the recursive call results in an unordered map ‘VALUE’.

For every recursive call, we will first check the ‘VALUE’ map. If the value is already computed, we will return it; otherwise, solve it and put it in the ‘value’ map.

The idea to solve this problem is the same as we did in the recursive approach, i.e., splitting the expression into sub-expressions whenever any operator is encountered.

We will separate the operands and operators in the expression and store them in the linear array of integers and characters. 

If the operator between two sub-expressions is ‘+’ we can simply combine the two sub-expressions according to the operator between them.

But if the operator is ‘-’, then the maximum value will be obtained by subtracting the minimum value of the second subexpression from the maximum value of the first sub-expression.  

And for the ‘ * ’ operator, the maximum value can be obtained by either multiplying the maximum values of both the expressions or multiplying the minimum value of the two sub-expressions.

Algorithm

• Create an array of integers 'OPERANDS' and an array of characters 'OPERATORS' to store the operands and operators in the given expression.
• Traverse through the given expression and separate the operators and operands.
• Store the length of 'OPERATORS' in 'LEN'.
• Initialize two 2-D arrays ‘MAX_RES’ and ‘MIN_RES’ of size len * len with all initial values ‘INT_MIN’ and ‘INT_MAX’ and main diagonal values ( where i= j ) with operand[ i ] where MAX_RES[ i ][ j ] and MIN_RES[ i ][ j ] denotes the maximum and minimum value of the expression between ‘i-th’ and ‘j-th’ operands.
• Fill the ‘MAX_RES’ and ‘MIN_RES’ array diagonally. For any cell RES[ i ][ j ] -
  • Run a loop k: i to j - 1
  • If operator[ k ] = ‘+’
    • MAX_RES[ i ][ j ] = max( MAX_RES[ i ][ j ] , MAX_RES[ i ][ k ] + MAX_RES[ k+1 ][ j ]
    • MIN_RES[ i ][ j ] = min( MIN_RES[ i ][ j ], MIN_RES[ i ][ k ] + MIN_RES[ k+1 ][ j ]
  • If operator[ k ] = ‘*’
    • MAX_RES[ i ][ j ] = max( MAX_RES[ i ][ j ] , MAX_RES[ i ][ k ] * MAX_RES[ k+1 ][ j ] , MIN_RES[ i ][ k ] * MIN_RES[ k+1 ][ j ] )
    • MIN_RES[ i ][ j ] = min( MIN_RES[ i ][ j ], MIN_RES[ i ][ k ] * MIN_RES[ k+1 ][ j ] , MIN_RES[ i ][ k ] * MAX_RES[ k+1][ j ], MAX_RES[ i ][ k+1 ] * MIN_RES[ k+1][ j ]
  • If operator[ k ] = ‘-’
    • MAX_RES[ i ][ j ] = max( MAX_RES[ i ][ j ] , MAX_RES[ i ][ k ] - MIN_RES[ k+1 ][ j ]
    • MIN_RES[ i ][ j ] = min( MIN_RES[ i ][ j ], MIN_RES[ i ][ k ] - MAX_RES[ k+1 ][ j ]
• Return MAX_RES[ 0 ][ len - 1 ].