Stacks and Queues

Balanced Parentheses

Walk a string of bracket characters. Push every opening bracket. On a closing bracket, pop and verify it matches; mismatch or empty-stack pop means unbalanced. At end of string, stack must be empty.

Algorithm

Canonical input "({[]})" (balanced) finishes with the stack empty and the result true.

stack push/pop Use an `ArrayDeque<Character>` as the stack.
matching map A small `HashMap` mapping each closing bracket to its expected opener keeps the lesson compact.

Basic Implementation

Basic.java
Replay: real traced execution (multi-file project)
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.HashMap;
import java.util.Map;

public class Basic {
    public static void main(String[] args) {
        String text = "({[]})";
        Map<Character, Character> pairs = new HashMap<>();
        pairs.put(')', '(');
        pairs.put(']', '[');
        pairs.put('}', '{');
        Deque<Character> stack = new ArrayDeque<>();
        boolean balanced = true;
        for (int i = 0; i < text.length(); i++) {
            char ch = text.charAt(i);
            if (ch == '(' || ch == '[' || ch == '{') {
                stack.push(ch);
            } else {
                if (stack.isEmpty() || stack.peek() != pairs.get(ch)) {
                    balanced = false;
                    break;
                }
                stack.pop();
            }
        }
        if (!stack.isEmpty()) {
            balanced = false;
        }
        System.out.println(balanced);
    }
}

  1. text ← ({[]})

    7public static void main(String[] args) {8    String text = "({[]})";9    Map<Character, Character> pairs = new HashMap<>();
    values this step({[]})text

  2. stack ← []

    12pairs.put('}', '{');13Deque<Character> stack = new ArrayDeque<>();14boolean balanced = true;
    values this step[]stack

  3. balanced ← true

    13Deque<Character> stack = new ArrayDeque<>();14boolean balanced = true;15for (int i = 0; i < text.length(); i++) {
    values this steptruebalanced

  4. stack ← [(]

    15for (int i = 0; i < text.length(); i++) {16    char ch = text.charAt(i);17    if (ch == '(' || ch == '[' || ch == '{') {
    values this step[(]stack(ch

  5. stack ← [(, {]

    15for (int i = 0; i < text.length(); i++) {16    char ch = text.charAt(i);17    if (ch == '(' || ch == '[' || ch == '{') {
    values this step[(, {]stack{ch

  6. stack ← [(, {, []

    15for (int i = 0; i < text.length(); i++) {16    char ch = text.charAt(i);17    if (ch == '(' || ch == '[' || ch == '{') {
    values this step[(, {, []stack[ch

  7. stack ← [(, {]

    15for (int i = 0; i < text.length(); i++) {16    char ch = text.charAt(i);17    if (ch == '(' || ch == '[' || ch == '{') {
    values this step[(, {]stack]ch

  8. stack ← [(]

    15for (int i = 0; i < text.length(); i++) {16    char ch = text.charAt(i);17    if (ch == '(' || ch == '[' || ch == '{') {
    values this step[(]stack}ch

  9. stack ← []

    15for (int i = 0; i < text.length(); i++) {16    char ch = text.charAt(i);17    if (ch == '(' || ch == '[' || ch == '{') {
    values this step[]stack)ch

  10. balanced ← true, stdout ← true

    26}27if (!stack.isEmpty()) {28    balanced = false;
    values this steptruebalancedtruestdout[]stack

Complexity

  • Time: O(n)
  • Space: O(n) worst case

Implementation notes

  • Java: ArrayDeque<Character> is the idiomatic stack; avoid java.util.Stack, which is synchronized and legacy.
  • The replay highlights the current character, shows the stack updating each frame, and surfaces the final balanced/unbalanced verdict.