CODEWITHSUNDEEP
pythondynamic-programmingparentheses
Elen
Elen

Reputation: 151

Dynamic programming solution to maximizing an expression by placing parentheses

I'm trying to implement an algorithm from Algorithmic Toolbox course on Coursera that takes an arithmetic expression such as 5+8*4-2 and computes its largest possible value. However, I don't really understand the choice of indices in the last part of the shown algorithm; my implementation fails to compute values using the ones initialized in 2 tables (which are used to store maximized and minimized values of subexpressions).

The evalt function just takes the char, turns it into the operand and computes a product of two digits:

def evalt(a, b, op):
    if op == '+':
        return a + b
#and so on

MinMax computes the minimum and the maximum values of subexpressions

def MinMax(i, j, op, m, M):
    mmin = 10000
    mmax = -10000
    for k in range(i, j-1):
        a = evalt(M[i][k], M[k+1][j], op[k])
        b = evalt(M[i][k], m[k+1][j], op[k])
        c = evalt(m[i][k], M[k+1][j], op[k])
        d = evalt(m[i][k], m[k+1][j], op[k])
        mmin = min(mmin, a, b, c, d)
        mmax = max(mmax, a, b, c, d)
    return(mmin, mmax)

And this is the body of the main function

def get_maximum_value(dataset):
    op = dataset[1:len(dataset):2]
    d = dataset[0:len(dataset)+1:2]
    n = len(d)
    #iniitializing matrices/tables
    m = [[0 for i in range(n)] for j in range(n)]  #minimized values
    M = [[0 for i in range(n)] for j in range(n)]  #maximized values
    for i in range(n):
        m[i][i] = int(d[i])   #so that the tables will look like
        M[i][i] = int(d[i])   #[[i, 0, 0...], [0, i, 0...], [0, 0, i,...]]
    for s in range(n):   #here's where I get confused
        for i in range(n-s):
            j = i + s
            m[i][j], M[i][j] = MinMax(i,j,op,m,M)
    return M[0][n-1]

Upvotes: 5

Views: 8669

Answers (2)

Maaz Ahmed
Maaz Ahmed

Reputation: 1

The following change should work.

 for s in range(1,n):
    for i in range(0,n-s):

Upvotes: 0

Elen
Elen

Reputation: 151

Sorry to bother, here's what had to be improved:

for s in range(1,n)

in the main function, and 

for k in range(i, j):

in MinMax function. Now it works.

Upvotes: 4

Related Questions