update 224

fishercoder1534 · fishercoder1534 · commit 76ee1ef7dbd7 · 2024-06-09T09:54:20.000-07:00
diff --git a/src/main/java/com/fishercoder/solutions/_224.java b/src/main/java/com/fishercoder/solutions/_224.java
@@ -109,4 +109,53 @@ private int cal(String s) {
         }
     }
 
+    public static class Solution3 {
+        /**
+         * A more elegant solution using stack and iterative approach, credit: https://leetcode.com/problems/basic-calculator/solutions/62361/iterative-java-solution-with-stack/
+         * Key points:
+         * 1. use an integer to represent sign: 1 or -1, so it can be pushed onto a stack that's of Integer type;
+         */
+        public int calculate(String s) {
+            Deque<Integer> stack = new LinkedList<>();
+            int result = 0;
+            int sign = 1;
+            int num = 0;
+            for (int i = 0; i < s.length(); i++) {
+                char c = s.charAt(i);
+                if (Character.isDigit(c)) {
+                    num = num * 10 + c - '0';
+                } else if (c == '(') {
+                    //we push the result onto the stack first, then sign
+                    stack.addLast(result);
+                    stack.addLast(sign);
+
+                    //reset them
+                    sign = 1;
+                    num = 0;
+                } else if (c == ')') {
+                    //this means we reached the end of one parenthesis, so we compute result and reset num
+                    result += num * sign;
+                    num = 0;
+
+                    result *= stack.pollLast();//this is the last sign we pushed onto the stack
+                    result += stack.pollLast();//this is the last number on the stack
+                } else if (c == '+') {
+                    result += num * sign;
+                    //reset below two variables
+                    num = 0;
+                    sign = 1;
+                } else if (c == '-') {
+                    result -= num * sign;
+                    //reset below two variables
+                    num = 0;
+                    sign = 1;
+                }
+            }
+            if (num != 0) {
+                result += num * sign;
+            }
+            return result;
+        }
+    }
+
 }
diff --git a/src/test/java/com/fishercoder/_224Test.java b/src/test/java/com/fishercoder/_224Test.java
@@ -9,12 +9,14 @@
 public class _224Test {
     private static _224.Solution1 solution1;
     private static _224.Solution2 solution2;
+    private static _224.Solution3 solution3;
     private static int expected;
 
     @BeforeEach
     public void setup() {
         solution1 = new _224.Solution1();
         solution2 = new _224.Solution2();
+        solution3 = new _224.Solution3();
     }
 
     @Test
@@ -39,6 +41,7 @@ public void test3() {
         expected = 23;
         assertEquals(expected, solution1.calculate(s));
         assertEquals(expected, solution2.calculate(s));
+        assertEquals(expected, solution3.calculate(s));
     }
 
     @Test
