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).

Basic Implementation

basic.f90 
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

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.
push opener pop matching closer Each closing bracket must match the most recent unmatched opener.