Introduction to Algorithms Chapter 3 3.1 problem

shekhargulati · shekhargulati · commit b1cb925b690f · 2016-02-25T15:06:06.000+05:30
diff --git a/java8/src/main/java/com/shekhargulati/ninetynine_problems/java8/_00_random/stack/ParenthesisBalanceChecker.java b/java8/src/main/java/com/shekhargulati/ninetynine_problems/java8/_00_random/stack/ParenthesisBalanceChecker.java
@@ -0,0 +1,51 @@
+package com.shekhargulati.ninetynine_problems.java8._00_random.stack;
+
+import java.util.Stack;
+
+/**
+ * A common problem for compilers and text editors is determining whether the parentheses in a string are balanced and properly nested.
+ * For example, the string ((())())() contains properly nested pairs of parentheses, which the strings )()( and ()) do not.
+ * Give an algorithm that returns true if a string contains properly nested and balanced parentheses, and false if otherwise.
+ * For full credit, identify the position of the first offending parenthesis if the string is not properly nested and balanced.
+ */
+public class ParenthesisBalanceChecker {
+
+    public boolean isBalancedString(final String input) {
+        /*
+        Algorithm:
+            1. Iterate over all the characters in a String
+            2. if stack is not empty and character is ')' then pop the element from the stack
+            3. else push the element into the stack
+            4. After iteration if stack is empty then return true else return false.
+         */
+        Stack<Character> stack = new Stack<>();
+        char[] chars = input.toCharArray();
+        for (char ch : chars) {
+            if (ch == ')' && !stack.empty()) {
+                stack.pop();
+            } else {
+                stack.push(ch);
+            }
+        }
+        return stack.isEmpty();
+    }
+
+    public int firstOffendingParenthesis(String input) {
+        /*
+        Algorithm:
+            1. Iterate over all the characters of input String
+            2. If character is ')' and stack is not empty then remove element from stack
+            3. Else add the position into the stack
+            4. After iteration, if stack is empty then return -1 else get the first element and return its value.
+         */
+        Stack<Integer> stack = new Stack<>();
+        for (int i = 0; i < input.length(); i++) {
+            if (input.charAt(i) == ')' && !stack.empty()) {
+                stack.pop();
+            } else {
+                stack.push(i);
+            }
+        }
+        return stack.empty() ? -1 : stack.elementAt(0);
+    }
+}
diff --git a/java8/src/test/java/com/shekhargulati/ninetynine_problems/java8/_00_random/stack/ParenthesisBalanceCheckerTest.java b/java8/src/test/java/com/shekhargulati/ninetynine_problems/java8/_00_random/stack/ParenthesisBalanceCheckerTest.java
@@ -0,0 +1,61 @@
+package com.shekhargulati.ninetynine_problems.java8._00_random.stack;
+
+import org.junit.Test;
+
+import static org.hamcrest.CoreMatchers.equalTo;
+import static org.junit.Assert.*;
+
+public class ParenthesisBalanceCheckerTest {
+
+    private final ParenthesisBalanceChecker checker = new ParenthesisBalanceChecker();
+
+    @Test
+    public void shouldSayTrueForEmptyString() throws Exception {
+        final String input = "";
+        boolean balanced = checker.isBalancedString(input);
+        assertTrue(balanced);
+    }
+
+    @Test
+    public void shouldSayTrueWhenStringIsBalanced() throws Exception {
+        final String input = "((())())()";
+        boolean balanced = checker.isBalancedString(input);
+        assertTrue(balanced);
+    }
+
+    @Test
+    public void shouldSayFalseWhenStringIsNotBalanced() throws Exception {
+        final String input = ")()(";
+        boolean balanced = checker.isBalancedString(input);
+        assertFalse(balanced);
+    }
+
+    @Test
+    public void shouldSayFalseWhenStringIsNotBalanced_anotherInput() throws Exception {
+        final String input = "())";
+        boolean balanced = checker.isBalancedString(input);
+        assertFalse(balanced);
+    }
+
+    @Test
+    public void shouldFindPositionOfFirstOffendingParenthesis() throws Exception {
+        final String input = ")()(";
+        int position = checker.firstOffendingParenthesis(input);
+        assertThat(position, equalTo(0));
+    }
+
+    @Test
+    public void shouldFindPositionOfFirstOffendingParenthesis_input2() throws Exception {
+        final String input = "(())(";
+        int position = checker.firstOffendingParenthesis(input);
+        assertThat(position, equalTo(4));
+    }
+
+    @Test
+    public void shouldFindPositionOfFirstOffendingParenthesis_input3() throws Exception {
+        final String input = "())";
+        int position = checker.firstOffendingParenthesis(input);
+        assertThat(position, equalTo(2));
+    }
+
+}
