Checking that brackets match (an application of stacks)

This lesson covers checking bracket matching with a stack in Julia, with the aim of seeing a practical application of the data structure.

With a stack (last in, first out) you push each opening bracket such as ( or [, and each time a closing bracket arrives you check it against the top of the stack.

The sample code holds the opening bracket for each closing bracket in a Dict called pairs, uses a typed Char[] array as the stack, pushes with push!() when an opening bracket arrives, and checks against the top when a closing one does.

A common early stumble is handling several kinds of bracket at once (round, square, and curly mixed together). Counting openings and closings is not enough — you have to check they nest in the right order.

A similar mechanism sits inside a compiler's syntax analysis. It is an idea with broad application.

📖 Reference code

function is_balanced(str)
    stack = Char[]
    pairs = Dict(')' => '(', ']' => '[', '}' => '{')
    for ch in str
        if ch in "([{"
            push!(stack, ch)
        elseif ch in ")]}"
            if isempty(stack) || pop!(stack) != pairs[ch]
                return false
            end
        end
    end
    return isempty(stack)
end

println(is_balanced("(a[b]{c})"))
println(is_balanced("(a[b)]"))

✍️ Your code

Type your code, then press "Run"

🧪 This site can't compile or run Julia directly, so it checks on the spot whether what you typed matches the reference code (scoring happens entirely in your browser — nothing is sent anywhere).