Check for balanced parentheses

Question

Given an expression string exp, write a program to examine whether the pairs and the orders of

"{","}","(",")","[","]"

are correct in exp.

For example, the program should print true for

exp = "[()]{}{[()()]()}"

and false for

exp = "[(])"

Complexity:

• Time complexity: O(n) where n is length of the string
• Space complexity: O(n/2) where n is length of string

Looking for code review, optimizations and best practices.

public final class BalancedParanthesis {

    private static final Map<Character, Character> brackets = new HashMap<Character, Character>();
    static {
        brackets.put('[', ']');
        brackets.put('{', '}');
        brackets.put('(', ')');
    }  

    private BalancedParanthesis() {};

    /**
     * Returns true is parenthesis match open and close.
     * Understands [], {}, () as the brackets
     * It is clients responsibility to include only valid paranthesis as input.
     * A false could indicate that either parenthesis did not match or input including chars other than valid paranthesis
     * 
     * @param str   the input brackets
     * @return      true if paranthesis match.
     */
    public static boolean isBalanced(String str) {
        if (str.length() == 0) {
            throw new IllegalArgumentException("String length should be greater than 0");
        }
        // odd number would always result in false
        if ((str.length() % 2) != 0) {
            return false;
        }

        final Stack<Character> stack = new Stack<Character>();
        for (int i = 0; i < str.length(); i++) {
            if (brackets.containsKey(str.charAt(i))) {
                stack.push(str.charAt(i));
            } else if (stack.empty() || (str.charAt(i) != brackets.get(stack.pop()))) {
                return false;
            } 
        }
        return true;
    } 

    public static void main(String[] args) {
        assertEquals(true, isBalanced("{}([])"));
        assertEquals(false,isBalanced("([}])"));
        assertEquals(true, isBalanced("([])"));
        assertEquals(true, isBalanced("()[]{}[][]"));
    }
}

Answer 1

I just wanted to write that the code looks completely fine to me, until...

assertEquals(false, isBalanced("[["));

I''m sure you'll find the error :-)

Otherwise two small remarks:

• Personally I'd have the function return true for an empty string instead of throwing an exception.

• Stack is outdated. I'd use a Deque implementation instead.

EDIT: I'm sorry, but I just realized something else: Your program doesn't fulfill the requirement O(n/2) for space complexity.

Answer 2

assertEquals vs assertTrue

I see that you're using :

    assertEquals(true, isBalanced("{}([])"));
    assertEquals(false,isBalanced("([}])"));
    assertEquals(true, isBalanced("([])"));
    assertEquals(true, isBalanced("()[]{}[][]"));

This is not the best way to assert boolean values. You should be using :

    assertTrue(isBalanced("{}([])"));
    assertFalse(isBalanced("([}])"));
    assertTrue(isBalanced("([])"));
    assertTrue(isBalanced("()[]{}[][]"));

This is more clear since it is clear that you are checking for true/false.

Separation

All your tests are still in the main, I will again strongly recommend to extract those tests in a test class, and create a single method for each case. This will help if you give relevant name to your tests to see at first glance what are you testing specifically. Is it an exception, a normal case, etc.

Answer 3

This code is basically perfect (save for that little bug found by RoToRa):

• Map initialization in a static initializer block
• constructor is made inaccessible
• the code does what the documentation says
• clever short circuiting
• implementation using explicit stack

However, there are a few points which we can talk about:

• The JavaDoc doesn't mention that the string must contain at least two characters. I would expect that the string "" is indeed balanced. For me, a balanced string would be described by the following EBNF grammar:

  <Balanced> ::=
    '(' <Balanced> ')'
  | '{' <Balanced> '}'
  | '[' <Balanced> ']'
  | epsilon
  

  that is, the empty string is allowed via this recursive definition. Instead, you've implemented a recognizer for the following grammar:

  <Balanced> ::=
    '(' <InnerBalanced> ')'
  | '{' <InnerBalanced> '}'
  | '[' <InnerBalanced> ']'
  
  <InnerBalanced> ::=
    <Balanced>
  | epsilon
  

• You forgot to test that str != null

• You could use the diamond operator to invoke inference on generic arguments:

  • Map<Character, Character> brackets = new HashMap<>()
  • Stack<Character> stack = new Stack<>()

• A user of your function can't specify custom parens like <…>. It would be good to enable some possibility of customization, and default to (…) otherwise.

• If you enable custom parens, then there may be some ambiguity – each opening paren would be associated with a set of possible closing parens. Note that given an O(1) membership test, this won't affect the algorithmic complexity of your code. Examples: |…| (norm operator/abs from mathematics), |…> (Bra-ket notation from quantum physics), <…> (mean value/expected value from statistics).

• When checking whether a given string has balanced parens, this string will usually contain non-paren text as well. A function that returns true for q{foo($bar{baz} .= do {my $x = '('; bless \$x})} given the delimiters {…} would be useful in real-world applications. Unfortunately, this disables your check that the string must be of even length.

• You only support single “characters” as delimiters. It would be more flexible to allow arbitrary strings. Note that Java's Characters aren't real Unicode characters, but effectively only 16-bit code units. To represent any Unicode code point, we need one or two Java characters (think: “int is the new char”). Note further that this is only sufficient for single code points, whereas one logical character (“grapheme”) may consist of multiple code points.

Answer 4

The class is misnamed: BalancedParanthesis should be BalancedParentheses. "Paranthesis" should be spelled "Parenthesis", and should be made plural to "Parentheses", since you can't balance one parenthesis.

Consider renaming it to BalancedDelimiters to be more general, since you support more than just parentheses.

Answer 5

I've only one addition to the other answers

For the stack you use java.util.Stack, this seems like an obvious choice, yet it is a remnant from pre-collection times, and is a subclass of java.util.Vector, and therefore synchronized. You don't need the synchronization overhead, and are better off using java.util.ArrayDeque. That is a double ended queue, but functions perfectly as a stack if only accessed from the top. In fact Stack's javadoc advises you to use ArrayDeque instead.

Answer 6

Even though your bracketsis private, it is a good practice to make these kind of key-value holders immutable as well. So your code

private static final Map<Character, Character> brackets = new HashMap<Character, Character>();
    static {
        brackets.put('[', ']');
        brackets.put('{', '}');
        brackets.put('(', ')');
    }

could be rewritten as

private static final Map<Character, Character> brackets = Collections.unmodifiableMap(new HashMap<Character, Character>() {{
        put('[', ']');
        put('{', '}');
        put('(', ')');
    }});

This is more concise and also serves as good documentation even if your Map is private and even if you don't have a setter.

Another way is to use Guava library from Google which claims better performance and real immutability with a more concise syntax

private static final Map<Character, Character> guavaBracket = ImmutableMap.of('[', ']','{', '}','(', ')');

Answer 7

Some remarks:

1. As correctly pointed in the accepted answer, the code is plain broken; changing return true into return stack.empty() seems to fix that (disclaimer: I did not run the code).
2. I'm not sure that stack.push is truly of complexity O(1), which is necessary to match the "Time complexity: O(n)" requirement (think of what happens for an input consisting of a large even number of '{': the stack is grown at every push). For this reason I would use, rather than a stack object, a single auxiliary string char[] array of size str.length()/2 used as a stack, and an index into that. It is enough for the job, tends to make the code much simpler, and makes it appreciably faster (especially since stack is synchronized, as I learned from this answer).
3. The fragment for (int i = 0; i < str.length(); i++) matches the "Time complexity: O(n)" requirement, but its straight C equivalent would squarely not, for there strlen() is O(n), thus the statement O(n²). I suggest a variable n set to str.length() on entry, that will likely speed up things slightly, clarify and slightly shorten the code, and in any case can't harm much.
4. My reading of the problem's statement is that the empty string is perfectly acceptable.
5. It is not clear from the problem's statement that any character other than the 6 ones in {}[]() is prohibited, in particular space.
6. After that change of 1., the test (str.length() % 2) != 0 becomes redundant, and I would say unwanted (independently of the previous item).
7. I do not think that it is useful to add a test that str is null, for in that case str.length will throw an exception, and that's fine for me. It would be good style in C, though.