Java · Course navigation

Java stacks and balanced brackets

Use a stack to check that brackets are properly nested.

On this page

Before you start

Java collections and loops.

Use a stack to check that brackets are properly nested.
Predict the sample output and explain the state changes.
Complete the practice task and check the boundary cases.

The concept

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.

Code example

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

Example details

Follow the code

Open the walkthrough to inspect the example one step at a time.

Show guided walkthrough

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

Behind the scenes

How Java processes this code

The Java compiler produces bytecode. The JVM loads the class and invokes its main method.

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.