Stacks and Queues

Balanced Parentheses

Walk a string of bracket characters. Push every opening bracket. On a closing bracket, pop and verify the popped opener matches. Mismatch or empty-stack pop means unbalanced; an empty stack at the end means balanced.

Algorithm

Canonical balanced input is "({[]})"; the stack grows to three elements then empties as the closers arrive in matching order. The program prints T for balanced and F for unbalanced (Fortran logicals render to T/F with the (A) format used here).

push opener pop matching closer Each closing bracket must match the most recent unmatched opener.

Basic Implementation

basic.f90
Replay: real traced execution (multi-file project)
program stack_balanced
    implicit none
    character(len=*), parameter :: text = '({[]})'
    character(len=1) :: stack(16)
    integer :: top, i
    logical :: balanced
    character(len=1) :: ch, expected

    top = 0
    balanced = .true.
    do i = 1, len(text)
        ch = text(i:i)
        if (ch == '(' .or. ch == '[' .or. ch == '{') then
            top = top + 1
            stack(top) = ch
        else
            if (top == 0) then
                balanced = .false.
                exit
            end if
            select case (ch)
                case (')'); expected = '('
                case (']'); expected = '['
                case ('}'); expected = '{'
            end select
            if (stack(top) /= expected) then
                balanced = .false.
                exit
            end if
            top = top - 1
        end if
    end do
    if (top /= 0) balanced = .false.
    if (balanced) then
        print '(A)', 'T'
    else
        print '(A)', 'F'
    end if
end program stack_balanced

  1. text ← ({[]})

    2implicit none3character(len=*), parameter :: text = '({[]})'4character(len=1) :: stack(16)
    values this step({[]})text

  2. stack ← [], top ← 0

    9top = 010balanced = .true.
    values this step[]stack0top

  3. balanced ← .true.

    9top = 010balanced = .true.11do i = 1, len(text)
    values this step.true.balanced

  4. stack ← [(]

    11do i = 1, len(text)12    ch = text(i:i)13    if (ch == '(' .or. ch == '[' .or. ch == '{') then
    values this step[(]stack(ch

  5. stack ← [(, {]

    11do i = 1, len(text)12    ch = text(i:i)13    if (ch == '(' .or. ch == '[' .or. ch == '{') then
    values this step[(, {]stack{ch

  6. stack ← [(, {, []

    11do i = 1, len(text)12    ch = text(i:i)13    if (ch == '(' .or. ch == '[' .or. ch == '{') then
    values this step[(, {, []stack[ch

  7. stack ← [(, {]

    11do i = 1, len(text)12    ch = text(i:i)13    if (ch == '(' .or. ch == '[' .or. ch == '{') then
    values this step[(, {]stack]ch

  8. stack ← [(]

    11do i = 1, len(text)12    ch = text(i:i)13    if (ch == '(' .or. ch == '[' .or. ch == '{') then
    values this step[(]stack}ch

  9. stack ← []

    11do i = 1, len(text)12    ch = text(i:i)13    if (ch == '(' .or. ch == '[' .or. ch == '{') then
    values this step[]stack)ch

  10. balanced ← .true., stdout ← T

    34if (balanced) then35    print '(A)', 'T'36else
    values this step.true.balancedTstdout[]stack

Complexity

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

Implementation notes

  • Fortran: a fixed-size character(len=1) :: stack(16) with an integer top is the most readable stack. Push is top = top + 1; stack(top) = ch; pop is top = top - 1.
  • The replay shows the current character, the operation (push vs. pop), and the post-step stack contents using a literal [(, {, [] notation rather than any pointer identity.