summaryrefslogtreecommitdiff
path: root/AlgoDesignAndTechniqueEdxPython/sources
diff options
context:
space:
mode:
Diffstat (limited to 'AlgoDesignAndTechniqueEdxPython/sources')
-rw-r--r--AlgoDesignAndTechniqueEdxPython/sources/placing_paren.py63
1 files changed, 63 insertions, 0 deletions
diff --git a/AlgoDesignAndTechniqueEdxPython/sources/placing_paren.py b/AlgoDesignAndTechniqueEdxPython/sources/placing_paren.py
new file mode 100644
index 0000000..90ac021
--- /dev/null
+++ b/AlgoDesignAndTechniqueEdxPython/sources/placing_paren.py
@@ -0,0 +1,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()))
+