1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
|
# Uses python3
def evalt(a, b, op):
if op == '+':
return a + b
elif op == '-':
return a - b
elif op == '*':
return a * b
else:
assert False
def minAndMax(m, M, op, i, j):
minValue = float("inf")
maxValue = float("-inf")
for k in range(i, j):
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])
minValue = min(minValue, a, b, c, d)
maxValue = max(maxValue, a, b, c, d)
return (minValue, maxValue)
def getMaxValueFrom(d, op):
m = [[0 for _ in range(len(d))] for _ in range(len(d))]
M = [[0 for _ in range(len(d))] for _ in range(len(d))]
for i in range(len(d)):
m[i][i] = d[i]
M[i][i] = d[i]
for s in range(len(op)):
for i in range(len(d) - s):
j = i + s + 1
if j >= len(d):
break
tempMinAndMax = minAndMax(m, M, op, i, j)
m[i][j] = tempMinAndMax[0]
M[i][j] = tempMinAndMax[1]
return M[0][len(d) - 1]
def getMaxValue(exp):
x = len(exp)
d = [0] * int(((x + 1) / 2))
# op = "-" * int(((x - 1) / 2))
op = [0] * int(((x - 1) / 2))
for i in range(0, x - 1, 2):
d[int(i / 2)] = int(exp[i])
op[int(i / 2)] = exp[i + 1]
d[int((x + 1) / 2 - 1)] = int(exp[x - 1])
return getMaxValueFrom(d, op)
if __name__ == "__main__":
print(getMaxValue(input()))
|