From 27e7cf18d35a1dc2c8ad2acf9a77b2799d884a43 Mon Sep 17 00:00:00 2001
From: Haidong Ji
Date: Fri, 28 Dec 2018 14:58:39 -0600
Subject: Max exp value with paren done!

Wow, translating the algo into code was tricky! Debugging was
challenging, frustrating, and ultimately rewarding. Two debugging
takeaways I can think of now:
1. Make the test case small, so it's easy to trace the whole thing
through;
2. For bigger test case, the example from lecture notes was helpful. I
just needed to set breakpoint intelligently to see the min and max
arrays.

Also, initializing the min and max value, then use the Math.min and
Math.max was interesting. I may need to remember that, that's why I have
the notes here!---
 .../sources/PlacingParen.java                      | 73 ++++++++++++++++++++++
 .../tests/PlacingParenTest.java                    | 35 +++++++++++
 2 files changed, 108 insertions(+)
 create mode 100644 AlgoDesignAndTechniqueEdxJava/sources/PlacingParen.java
 create mode 100644 AlgoDesignAndTechniqueEdxJava/tests/PlacingParenTest.java

diff --git a/AlgoDesignAndTechniqueEdxJava/sources/PlacingParen.java b/AlgoDesignAndTechniqueEdxJava/sources/PlacingParen.java
new file mode 100644
index 0000000..ad80631
--- /dev/null
+++ b/AlgoDesignAndTechniqueEdxJava/sources/PlacingParen.java
@@ -0,0 +1,73 @@
+import java.util.Scanner;
+
+public class PlacingParen {
+
+    public static void main(String[] args) {
+        Scanner scanner = new Scanner(System.in);
+        String exp = scanner.next();
+        System.out.println(getMaxValue(exp));
+    }
+
+    public static long getMaxValue(String exp) {
+        int x = exp.length();
+        int[] d = new int[(x + 1) / 2];
+        char[] op = new char[(x - 1) / 2];
+
+        for (int i = 0; i < x - 1; i = i + 2) {
+            d[i / 2] = Character.getNumericValue(exp.charAt(i));
+            op[i / 2] = exp.charAt(i + 1);
+        }
+        d[(x + 1) / 2 - 1] = Character.getNumericValue(exp.charAt(x - 1));
+        return getMaxValue(d, op);
+    }
+
+    private static long getMaxValue(int[] d, char[] op) {
+        long[][] m = new long[d.length][d.length];
+        long[][] M = new long[d.length][d.length];
+        for (int i = 0; i < d.length; i++) {
+            m[i][i] = d[i];
+            M[i][i] = d[i];
+        }
+        for (int s = 0; s < op.length; s++) {
+            for (int i = 0; i < d.length - s; i++) {
+                int j = i + s + 1;
+                if (j >= d.length)
+                    break;
+                long[] tempMinAndMax = minAndMax(m, M, op, i, j);
+                m[i][j] = tempMinAndMax[0];
+                M[i][j] = tempMinAndMax[1];
+            }
+        }
+        return M[0][d.length - 1];
+    }
+
+    private static long[] minAndMax(long[][] m, long[][] M, char[] op, int i, int j) {
+        long min = Long.MAX_VALUE;
+        long max = Long.MIN_VALUE;
+
+        for (int k = i; k < j; k++) {
+            long a = eval(M[i][k], M[k + 1][j], op[k]);
+            long b = eval(M[i][k], m[k + 1][j], op[k]);
+            long c = eval(m[i][k], M[k + 1][j], op[k]);
+            long d = eval(m[i][k], m[k + 1][j], op[k]);
+            min = Math.min(min, Math.min(a, Math.min(b, Math.min(c, d))));
+            max = Math.max(max, Math.max(a, Math.max(b, Math.max(c, d))));
+        }
+        long[] result = { min, max };
+        return result;
+    }
+
+    private static long eval(long a, long b, char op) {
+        if (op == '+') {
+            return a + b;
+        } else if (op == '-') {
+            return a - b;
+        } else if (op == '*') {
+            return a * b;
+        } else {
+            assert false;
+            return 0;
+        }
+    }
+
+}
diff --git a/AlgoDesignAndTechniqueEdxJava/tests/PlacingParenTest.java b/AlgoDesignAndTechniqueEdxJava/tests/PlacingParenTest.java
new file mode 100644
index 0000000..91885e9
--- /dev/null
+++ b/AlgoDesignAndTechniqueEdxJava/tests/PlacingParenTest.java
@@ -0,0 +1,35 @@
+import static org.junit.jupiter.api.Assertions.*;
+
+import org.junit.jupiter.api.Test;
+
+class PlacingParenTest {
+
+    @Test
+    void test() {
+        String exp = "1+5";
+        assertEquals(6, PlacingParen.getMaxValue(exp));
+        ;
+    }
+
+    @Test
+    void test1() {
+        String exp = "5-8+7*4-8+9";
+        assertEquals(200, PlacingParen.getMaxValue(exp));
+        ;
+    }
+
+    @Test
+    void test2() {
+        String exp = "1+2-3*4-5";
+        assertEquals(6, PlacingParen.getMaxValue(exp));
+        ;
+    }
+
+    @Test
+    void test3() {
+        String exp = "1+2*3";
+        assertEquals(9, PlacingParen.getMaxValue(exp));
+        ;
+    }
+
+}
-- 
cgit v1.2.3