Java stacks and balanced brackets

Use a stack to check that brackets are properly nested.

Java

import java.util.*;

class Main {
  static boolean balanced(String text) {
    Deque<Character> stack = new ArrayDeque<>();
    for (char ch : text.toCharArray()) {
      if (ch == '(' || ch == '[' || ch == '{') {
        stack.push(ch);
      } else if (ch == ')' || ch == ']' || ch == '}') {
        if (stack.isEmpty()) {
          return false;
        }
        char open = stack.pop();
        if ((ch == ')' && open != '(') || (ch == ']' && open != '[') || (ch == '}' && open != '{')) {
          return false;
        }
      }
    }
    return stack.isEmpty();
  }

  public static void main(String[] args) {
    String[] tests = {"(a[b]{c})", "(]", "((", ")(", ""};
    for (String test : tests) {
      System.out.println("'" + test + "' -> " + balanced(test));
    }
  }
}

Output

'(a[b]{c})' -> true
'(]' -> false
'((' -> false
')(' -> false
'' -> true

Explanation

A stack is a last-in, first-out structure: the item pushed most recently is the first one popped. In Java, ArrayDeque is the recommended implementation, with push, pop, and peek working at the top. The older Stack class is synchronized and not recommended for new code.

Checking brackets is a classic stack problem. Scan the text from left to right. Push each opening bracket. For each closing bracket, the top of the stack must be the matching opening bracket, otherwise the text is invalid. At the end the stack must be empty, or some brackets were never closed.

Explore the dry run

Guided walkthroughReady

1import java.util.*;

3class Main {

4 static boolean balanced(String text) {

5 Deque<Character> stack = new ArrayDeque<>();

6 for (char ch : text.toCharArray()) {

7 if (ch == '(' || ch == '[' || ch == '{') {

8 stack.push(ch);

9 } else if (ch == ')' || ch == ']' || ch == '}') {

10 if (stack.isEmpty()) {

11 return false;

12 }

13 char open = stack.pop();

14 if ((ch == ')' && open != '(') || (ch == ']' && open != '[') || (ch == '}' && open != '{')) {

15 return false;

16 }

17 }

18 }

19 return stack.isEmpty();

20 }

22 public static void main(String[] args) {

23 String[] tests = {"(a[b]{c})", "(]", "((", ")(", ""};

24 for (String test : tests) {

25 System.out.println("'" + test + "' -> " + balanced(test));

26 }

27 }

28}

Follow the example

Start to inspect the source, values, and output. These prepared steps explain the published sample; grouped loop steps describe multiple iterations.

View the complete dry-run table

Prepared trace of the published program. Some rows group repeated iterations.
What happens	State after step	Output so far
An empty stack of characters.	`—`	—
An opening bracket is pushed.	`stack grows`	—
A closing bracket removes the most recent opening bracket, which must match.	`stack grows`	—
Leftover opening brackets mean the text is unbalanced.	`stack grows`	—
Only the properly nested and empty texts are balanced.	`stack grows`	'(a[b]{c})' -> true '(]' -> false '((' -> false ')(' -> false '' -> true

Cost and common mistakes

O(n) time and O(n) space for a text of n characters.

Calling pop on an empty ArrayDeque throws NoSuchElementException. The code checks isEmpty first.
Counting brackets is not enough. The text ')(' has equal counts but is invalid.
Prefer ArrayDeque over Stack and LinkedList for stacks and queues.

Try it yourself

What happens for the input "{[}]"?

Reveal answer and reasoning

It returns false: when } arrives the top of the stack is [, which is not its match.

Java stacks and balanced brackets

Explanation

Follow the example

Cost and common mistakes

Try it yourself

Further reading