Max expression value by placing paren done!HEADmaster

2 files changed, 95 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()))
+
diff --git a/AlgoDesignAndTechniqueEdxPython/tests/placing_parenTest.py b/AlgoDesignAndTechniqueEdxPython/tests/placing_parenTest.py
new file mode 100644
index 0000000..7463182
--- /dev/null
+++ b/AlgoDesignAndTechniqueEdxPython/tests/placing_parenTest.py
@@ -0,0 +1,32 @@
+'''
+Created on Dec 28, 2018
+
+@author: haidong
+'''
+import unittest
+
+from sources.placing_paren import getMaxValue
+
+
+class Test(unittest.TestCase):
+
+    def testName(self):
+        exp = "1+5"
+        self.assertEqual(6, getMaxValue(exp))
+
+    def testName1(self):
+        exp = "5-8+7*4-8+9"
+        self.assertEqual(200, getMaxValue(exp))
+
+    def testName2(self):
+        exp = "1+2-3*4-5"
+        self.assertEqual(6, getMaxValue(exp))
+
+    def testName3(self):
+        exp = "1+2*3"
+        self.assertEqual(9, getMaxValue(exp))
+
+
+if __name__ == "__main__":
+    # import sys;sys.argv = ['', 'Test.testName']
+    unittest.main()