Given an expression using only* and binary operators and integer operands we wan
ID: 3871526 • Letter: G
Question
Given an expression using only* and binary operators and integer operands we want to "evaluate it" such that we obtain the largest possible result. For our task we do not follow the usual arithmetic precedence of doing multiplication (denoted by *) before addition (denoted by +). For example, 5+3 2 can be evaluated as (with parentheses used to denote operator ordering): (5+3) 2-16 or 5+(3 2)-11 Input will be one line containing a positive integer n, followed by n lines of test expressions, each with at least 1 and at most 200 operators. Each operator and operand is separated by at least one space character. For each case, output the maximum evaluation value over all possible operator orderings Each integer in the input expression can fit in a 32-bit word. However, note you may need to use a multi-precision data type (e.g., Biglnteger) to express some of the answers for the harder test data Sample Input 5+ 3 2 100100 100100100 100 100 1 -4-3 Sample Output 16 40000000000 15Explanation / Answer
def evaluate(a, b, op):
if op == '+':
return a + b
else:
return a * b
def MaxValue(i, j, op, m, M):
mmax = -10000
mmin = 10000
for k in range(i, j):
a = evaluate(M[i][k], M[k+1][j], op[k])
b = evaluate(M[i][k], m[k+1][j], op[k])
c = evaluate(m[i][k], M[k+1][j], op[k])
d = evaluate(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)
def get_maximum_value(expression):
expression="".join(expression.split())
op = expression[1:len(expression):2]
d = expression[0:len(expression)+1:2]
n = len(d)
m = [[0 for i in range(n)] for j in range(n)]
M = [[0 for i in range(n)] for j in range(n)]
for i in range(n):
m[i][i] = int(d[i])
M[i][i] = int(d[i])
for s in range(1,n):
for i in range(n-s):
j = i + s
m[i][j], M[i][j] = MaxValue(i,j,op,m,M)
return M[0][n-1]
num=int(raw_input())
for i in range(num):
expression=raw_input()
print get_maximum_value(expression)
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.