Maximum Value of an Arithmetic Expression

Problem Introduction 

In this problem, your goal is to add parentheses to a given arithmetic expression to maximize its value. max(5 − 8 + 7 × 4 − 8 + 9) =?

Problem Description Task. 

Find the maximum value of an arithmetic expression by specifying the order of applying its arithmetic operations using additional parentheses. 

Input Format.

 The only line of the input contains a string 𝑠 of length 2𝑛 + 1 for some 𝑛, with symbols 𝑠0, 𝑠1, . . . , 𝑠2𝑛. Each symbol at an even position of 𝑠 is a digit (that is, an integer from 0 to 9) while each symbol at an odd position is one of three operations from {+,-,*}. 

Constraints. 

0 ≤ 𝑛 ≤ 14 (hence the string contains at most 29 symbols). 

Output Format.  

Output the maximum possible value of the given arithmetic expression among different orders of applying arithmetic operations. 


Solution

# Uses python3
#SLOUTION 
import math
def calc(a, b, op):
    if op == '+':
        return a + b
    elif op == '-':
        return a - b
    else:
        return a * b


def MinAndMax(M, m, i, j, operators):
    min_value = float('inf')
    max_value = -float('inf')
    for k in range(i, j):
        a = calc(M[i][k], M[k+1][j], operators[k])
        b = calc(M[i][k], m[k+1][j], operators[k])
        c = calc(m[i][k], M[k+1][j], operators[k])
        d = calc(m[i][k], m[k+1][j], operators[k])
        min_value = min(min_value, a, b, c, d)
        max_value = max(max_value, a, b, c, d)
    return min_value, max_value


def gmv(operands, operators):
    n = len(operands)
    m = [[None for x in range(n)] for x in range(n)]
    M = [[None for x in range(n)] for x in range(n)]

    for i in range(n):
        m[i][i] = operands[i]
        M[i][i] = operands[i]

    for s in range(1, n):
        for i in range(0, n-s):
            j = i + s
            m[i][j], M[i][j] = MinAndMax(M, m, i, j, operators)

    return M[0][n-1]

if __name__ == "__main__":
    expression = input()
    operators, operands = [], []

    for i in expression:
        if i in ['+', '-', '*']:
            operators.append(i)
        else:
            operands.append(int(float(i)))

    print(gmv(operands, operators))


#IT WORKED FOR ME :))