summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorHaidong Ji2018-12-28 18:05:45 -0600
committerHaidong Ji2018-12-28 18:05:45 -0600
commit6eac7fac3f842cadb88b068635e17a79108897f6 (patch)
treebddd04c4bdad9682ed7955fa484cb2f0031ab4e3
parentf32e2e8777d12869ce9e82aee1e3b9cc9e87f0f6 (diff)
Max expression value by placing paren done!HEADmaster
-rw-r--r--AlgoDesignAndTechniqueEdxPython/sources/placing_paren.py63
-rw-r--r--AlgoDesignAndTechniqueEdxPython/tests/placing_parenTest.py32
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()