# Check for balanced parentheses

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("()[]{}[][]"));
}
}
-
Best practices: 1) Use Snobol (in which most of the program reduces to BAL x, where x is the string to check for balance). –  Jerry Coffin Apr 1 '14 at 7:20
Does your code return false for "[(])" ? –  konijn Apr 1 '14 at 13:14
@konijn Yes, it does. –  RoToRa Apr 1 '14 at 15:18
Why wouldn't an empty string be trivially balanced? –  coredump Apr 3 '14 at 15:21
I dont know why nobody pointed out but this will fail for input (A+B)+(C-D) –  maniac87 Dec 14 '14 at 0:26

I just wanted to write that the code looks completely fine two 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.

-
Yes it does. O(n/2) is the same as O(n). Whether it's what the instructor intended is a different question... –  Thomas Apr 1 '14 at 18:34
Ah, ok. The O notation isn't my strong suit. But you can modify the code so that it only needs to store n/2+1 chars max. –  RoToRa Apr 1 '14 at 22:51
@fgrieu: Sorry, it will assert. When calling isBalanced("[["), then the two brackets ([) will only pushed on to the stack. The second clause of the if statement in the for loop (and thus the pop()s) are never called, so that it reaches the final return true. See ideone.com/Ed5eiU (doesn't use assert, but outputs true to stdout). –  RoToRa Apr 2 '14 at 13:46
@RoToRa: I stand corrected. –  fgrieu Apr 2 '14 at 13:50

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

• Map initialization in a static initializer block
• 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.

-
"It would be more flexible to allow arbitrary strings" But then the problem gets much harder due to possible overlaps. The same problem occurs if you allow custom single-char brackets and a closing bracket coincides with an opening one. Also why would one need to check for null explicitly? The documentation doesn't state that null is a valid input, and by default I would not assume it to be, so is a NullPointerException not enough? –  Niklas B. Apr 1 '14 at 19:55
@NiklasB. An explicit NPE with custom error message makes it much easier for a caller to debug. Leaving behaviour unspecified is a cheap cop out. Also, defensive programming is a best practice. Re ambiguity: this is no problem even with the given algorithmic complexity constraints as long as one sets up a few rules that decide how the input is parsed: e.g. overlapping tokens become a non-issue with longest token matching, committing instead of backtracking preserves O(n) behaviour, and we could decide that closing braces are preferred over opening braces. Further questions? :) –  amon Apr 1 '14 at 21:12
Sure, you can specify greedy parsing, but that might go against the intuition of users who would assume that the parser just implements the straightforward context-free grammer given in your answer (which would then be hard to parse). Just wanted to point out that if you go that road you will need to consider a lot of details. W.r.t defensive, would it be just as acceptable to just say "null is never a valid input unless otherwise specified"? That's usually how I do it (for an entire library, not just for certain methods) and it does not leave anything unspecified –  Niklas B. Apr 1 '14 at 21:16
@NiklasB. Yes of course, and I only added suggestions on how to make the isBalanced more general. I believe that offering more power to “the user” is preferable to offering a restricted “safe” set of operations, even though more power means that more stuff can go wrong. (For some unfathomable reason, I prefer Perl over Python and Scala over Java…) Oh, I forgot to mention another good way to deal with ambiguity etc.: Just throw an exception when ambiguity is encountered (possibly as early as collecting all braces in a data structure). –  amon Apr 1 '14 at 21:37

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.

-

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.

-
Wouldn't a LinkedList be more appropriate? A linked list is optimised for push and pop operations, which is what is used here. –  RoToRa Apr 1 '14 at 23:13
ArrayDeque's push and pop operations, merely change an int index, only when the array needs to grow, there will be a need to do System.arrayCopy(), LinkedList will have to create a new Node on each push. Since we know the exact maximum needed capacity, we can make sure the ArrayDeque never needs to grow, eliminating the one disadvantage for ArrayDeque. Even if we don't set a capacity, I think ArrayDeque will outperform LinkedList in this algorithm. –  bowmore Apr 2 '14 at 4:52
Ah. Good to know. Thanks! –  RoToRa Apr 2 '14 at 7:43

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.

-
+1 for attention to detail –  zencv Apr 2 '14 at 8:01

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('[', ']','{', '}','(', ')');
-
The instance initializer block you recommend leads to much confusion in real life, especially when you break the Java Code Style guidelines in the way that you have. –  rolfl Apr 6 '14 at 13:55
yeah..only if immutability is bad and more verbose code is less confusing in "real life". –  zencv Apr 6 '14 at 15:54
The immutability is fine, but the anonymous subclass with instance initializer block with non-standard code formatting is what is confusing... which is what my first comment said. More verbose code or correctly formatted readable code.... call it what you want, but what you are recommending is not best practice in any common reference. –  rolfl Apr 6 '14 at 15:58
You seem to agree about immutability, I do not know whether any best practice recommendation exists for/against anonymous subclassing in such cases. In production code I had reviewed, I have also seen mostly the approach without anon. subclass which you seem to prefer. But lately I have seen the approach I proposed in use increasingly, especially by those who have coded in non Java languages. Code review in general involves some subjective opinion, sometimes matters of preference, style etc. –  zencv Apr 6 '14 at 16:19
At minimum, the 'opening' {{ of the code should be separated by newline, and correctly indented. The closing }} should be split as well. The inner {} are a code block, and should be on their own lines just like a method block or any other compound statement.... –  rolfl Apr 6 '14 at 16:23

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(n2). 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.
-
1) Good point that Stack.push() could take longer than O(1) time. It may be prudent to call Stack.ensureCapacity() to avoid any possible penalty of having to expand the stack. You could also use a char[] array. Strings are immutable in Java, though, and would not be suitable. –  200_success Apr 2 '14 at 10:17
@200_success: very right! Fixed it. You guessed it, I'm not truly a Java programmer (I mostly use the Java Card 2 dialect, used in Smart Cards, in the variant where no variable can be int, we have only short) –  fgrieu Apr 2 '14 at 10:32
I would object to the test of the null string, since if you know that you will be throwing a NullPointerException than make a test that expect an exception. If for any reason something change and the exception is not throw anymore you will know it! –  Marc-Andre Apr 2 '14 at 12:56