Arithmetic Operators
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.

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

Question

Arithmetic Operators

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.

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

Accepted Answer

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.

Space Complexity: O(n)Explanation:

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

Time Complexity: O(n^n)Explanation:

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

Accepted Answer

Memoization

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.

Space Complexity: O(n^2)Explanation:

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

We are using an extra map ‘value’ to store the result of the recursive calls. Therefore space complexity is O( N^2).

Time Complexity: O(n^3)Explanation:

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

We are computing the value of every sub-expression once which takes O(N) time, and the maximum number of sub-expressions can be N^2. So the time complexity is O( N^3)

Python (3.5)

"""

    Time Complexity: O(N^3)

    Space Complexity : O(N^2)

    

    where 'N' is the length of the given expression.

"""



import math



intMin = -2147483648

mod = 1000000007





def findMaxHelper(exp, value):



    # If value is already computed, return value[exp].

    if exp in value:

        return value[exp]



    # Vector to store all the computed values.

    res = []



    # Traverse the given expression.

    for k in range(len(exp)):



        # If operatoe is encountered.

        if exp[k] == '+' or exp[k] == '-' or exp[k] == '*':



            # Vectors to store result of left and right sub-expression.

            leftExp = []

            rightExp = []



            # Recursive calls.

            leftExp = findMaxHelper(exp[0:k], value)

            rightExp = findMaxHelper(exp[k + 1:], value)



            # Combining values of 'leftExp' with 'rightExp'.

            for i in range(len(leftExp)):

                for j in range(len(rightExp)):



                    if exp[k] == '+':

                        res.append(math.fmod(leftExp[i] + rightExp[j],

                                   mod))

                    elif exp[k] == '-':



                        res.append(math.fmod(leftExp[i] - rightExp[j],

                                   mod))

                    elif exp[k] == '*':



                        res.append(math.fmod(leftExp[i] * rightExp[j],

                                   mod))



    # If no operator is present in 'exp'.

    if len(res) == 0:

        res.append(int(exp))



    # Add 'res' to 'value'

    value[exp] = res

    return res





def findMax(exp):



    res = []



    # Initializing map to store result of recursive calls.

    value = {}



    # Recursive function.

    res = findMaxHelper(exp, value)

    ans = intMin



    # Finding maximum value in 'res' vector.

    for i in range(len(res)):

        ans = max(ans, res[i])



    return int(math.fmod(ans, mod))

Java (SE 1.8)

/*
    Time Complexity: O(N^3)
    Space Complexity : O(N^2)
    
    where 'N' is the length of the given expression.
    
*/

import java.util.*;

public class Solution {
    public static ArrayList findMaxHelper(String exp, Map> value)
    {
        // If value is already computed, return value[exp].
        if (value.containsKey(exp))
        {
            return value.get(exp);
        }

        // ArrayList to store all the computed values.
        ArrayList res = new ArrayList();

        // Iterate through the expression.
        for (int k = 0; k < exp.length(); k++)
        {

            // If operator is encountered.
            if (exp.charAt(k) == '+' || exp.charAt(k) == '-' || exp.charAt(k) == '*')
            {

                // Initializing ArrayLists to store result of left and right sub-expression.
                ArrayList leftExp = new ArrayList();
                ArrayList rightExp = new ArrayList();

                // Recursively call for left and right sub-expression.
                leftExp = findMaxHelper(exp.substring(0, k), value);
                rightExp = findMaxHelper(exp.substring(k + 1), value);

                /* Computing values by combining every value in 'leftExp' with
                every value in 'rightExp'*/
                for (int i = 0; i < leftExp.size(); i++)
                {
                    for (int j = 0; j < rightExp.size(); j++)
                    {

                        if (exp.charAt(k) == '+')
                        {
                            res.add((leftExp.get(i) + rightExp.get(j))%1000000007);
                        }

                        else if (exp.charAt(k) == '-')
                        {
                            res.add((leftExp.get(i) - rightExp.get(j))%1000000007);
                        }

                        else if (exp.charAt(k) == '*')
                        {
                            res.add((leftExp.get(i) * rightExp.get(j))%1000000007);
                        }
                    }
                }
            }
        }

        // If 'exp' has no operator, push number to 'res'
        if (res.size() == 0)
        {
            res.add(Integer.parseInt(exp));
        }

        // Add 'res' to 'value'
        value.put(exp, res);
            
        return res;
    }

    public static int findMax(String exp){
        ArrayList res = new ArrayList();

        // Initializing map to store result of recursive calls.
        Map> value = new HashMap>();

        // Recursive function to compute all the values.
        res = findMaxHelper(exp, value);

        // Variable to store answer.
        int ans = Integer.MIN_VALUE;

        // Calculate maximum value among all values in 'res'.
        for (int i = 0; i < res.size(); i++)
        {

            ans = Math.max(ans, res.get(i));
        }

        // Return ans.
        return ans % 1000000007;
    }
}

C++ (g++ 5.4)

/*
    Time Complexity: O(N^3)
    Space Complexity : O(N^2)
    
    where 'N' is the length of the given expression.
    
*/

#define intMin -2147483648
#define mod 1000000007
#include 

vector findMaxHelper(string exp, unordered_map> &value)
{

    // If value is already computed, return value[exp].
    if (value.find(exp) != value.end())
    {
        return value[exp];
    }
    
    // Vector to store all the computed values.
    vector res;

    // Traverse the given expression.
    for (int k = 0; k < exp.length(); k++)
    {

        // If operator is encountered.
        if (exp[k] == '+' || exp[k] == '-' || exp[k] == '*')
        {

            // Vectors to store result of left and right sub-expression.
            vector leftExp;
            vector rightExp;

            // Recursive calls.
            leftExp = findMaxHelper(exp.substr(0, k), value);
            rightExp = findMaxHelper(exp.substr(k + 1), value);

            // Combining values of 'leftExp' with 'rightExp'.
            for (int i = 0; i < leftExp.size(); i++)
            {

                for (int j = 0; j < rightExp.size(); j++)
                {
                    if (exp[k] == '+')
                    {
                        res.push_back((leftExp[i] + rightExp[j])%mod);
                    }

                    else if (exp[k] == '-')
                    {
                        res.push_back((leftExp[i] - rightExp[j])%mod);
                    }

                    else if (exp[k] == '*')
                    {
                        res.push_back((leftExp[i] * rightExp[j])%mod);
                    }
                }
            }
        }
    }

    // If no operator is present in 'exp'.
    if (res.size() == 0)
    {
        res.push_back(atoi(exp.c_str()));

    }
    
    // Add 'res' to 'value'
    value[exp] = res;

    return res;
}

int findMax(string &exp)
{
    vector res;

    // Initializing map to store result of recursive calls.
    unordered_map> value;

    // Recursive function.
    res = findMaxHelper(exp, value);

    int ans = intMin;

    // Finding maximum value in 'res' vector.
    for (int i = 0; i < res.size(); i++)
    {

        ans = max(ans, res[i]);
    }

    return ans % mod;
}

Accepted Answer

Dynamic Programming

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

Space Complexity: O(n^2)Explanation:

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

We have used extra 2-D arrays ‘MAX_RES’ and ‘MIN_RES’, making the space complexity O(N^2).