summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorHaidong Ji2018-12-28 14:58:39 -0600
committerHaidong Ji2018-12-28 14:58:39 -0600
commit27e7cf18d35a1dc2c8ad2acf9a77b2799d884a43 (patch)
tree4a3b41df51c7690dea3ef84cca077f62eb62326b
parent993716627a616e821aefd8707230221d0dac6cd7 (diff)
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!
-rw-r--r--AlgoDesignAndTechniqueEdxJava/sources/PlacingParen.java73
-rw-r--r--AlgoDesignAndTechniqueEdxJava/tests/PlacingParenTest.java35
2 files changed, 108 insertions, 0 deletions
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));
+ ;
+ }
+
+}