add BalancedParentheses

realDuYuanChao · realDuYuanChao · commit 4e06680e6505 · 2020-10-09T11:30:40.000+08:00
diff --git a/src/main/java/com/examplehub/datastructures/stack/BalancedParentheses.java b/src/main/java/com/examplehub/datastructures/stack/BalancedParentheses.java
@@ -0,0 +1,45 @@
+package com.examplehub.datastructures.stack;
+
+import java.util.Stack;
+
+public class BalancedParentheses {
+
+    /**
+     * Test if a parentheses expression
+     *
+     * @param parenthesesExpr the parentheses expression
+     * @return {@code true} if given parentheses expression is balanced.å
+     */
+    public static boolean isBalanced(String parenthesesExpr) {
+        Stack<Character> stack = new Stack<>();
+        for (int i = 0; i < parenthesesExpr.length(); i++) {
+            switch (parenthesesExpr.charAt(i)) {
+                case '(':
+                case '[':
+                case '{':
+                    stack.push(parenthesesExpr.charAt(i));
+                    break;
+                case ')':
+                case ']':
+                case '}':
+                    if (stack.isEmpty() || !isPaired(stack.pop(), parenthesesExpr.charAt(i))) {
+                        return false;
+                    }
+            }
+        }
+        return stack.isEmpty();
+    }
+
+    /**
+     * Test if left bracket and right bracket is paired.
+     *
+     * @param leftBracket  the left bracket.
+     * @param rightBracket the right bracket.
+     * @return {@code true} if two brackets are paired.
+     */
+    public static boolean isPaired(char leftBracket, char rightBracket) {
+        return leftBracket == '(' && rightBracket == ')'
+                || leftBracket == '[' && rightBracket == ']'
+                || leftBracket == '{' && rightBracket == '}';
+    }
+}
diff --git a/src/test/java/com/examplehub/datastructures/stack/BalancedParenthesesTest.java b/src/test/java/com/examplehub/datastructures/stack/BalancedParenthesesTest.java
@@ -0,0 +1,22 @@
+package com.examplehub.datastructures.stack;
+
+import org.junit.jupiter.api.Test;
+
+import static org.junit.jupiter.api.Assertions.*;
+
+class BalancedParenthesesTest {
+    @Test
+    void testIsBalanced() {
+        assertTrue(BalancedParentheses.isBalanced("([]{})"));
+        assertTrue(BalancedParentheses.isBalanced("[()]{}{[()()]()}"));
+        assertFalse(BalancedParentheses.isBalanced("[(])"));
+    }
+
+    @Test
+    void testIsPaired() {
+        assertTrue(BalancedParentheses.isPaired('[', ']'));
+        assertTrue(BalancedParentheses.isPaired('(', ')'));
+        assertTrue(BalancedParentheses.isPaired('{', '}'));
+        assertFalse(BalancedParentheses.isPaired('(', '}'));
+    }
+}
