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.

Basic Implementation

basic.pl 
use strict; use warnings;

sub match_open {
	my ($close) = @_;
	if ($close eq ')') {
		return '(';
	} elsif ($close eq ']') {
		return '[';
	} elsif ($close eq '}') {
		return '{';
	}
	return ' ';
}

my $text = "({[]})";
my @stack = ();
my $balanced = 1;
my $i = 0;
while ($balanced && $i < length($text)) {
	my $ch = substr($text, $i, 1);
	if ($ch eq '(' || $ch eq '[' || $ch eq '{') {
		push @stack, $ch;
	} else {
		if (scalar(@stack) == 0 || $stack[-1] ne match_open($ch)) {
			$balanced = 0;
		} else {
			pop @stack;
		}
	}
	$i = $i + 1;
}
if (scalar(@stack) != 0) {
	$balanced = 0;
}
if ($balanced) {
	print "True\n";
} else {
	print "False\n";
}

Complexity

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

Implementation notes

  • Perl: a plain @stack with push / pop / $stack[-1] / scalar(@stack) == 0 is the smallest honest stack shape; reaching for a wrapper class would hide the explicit push/pop pattern. A $balanced flag plus while ($balanced && $i < length($text)) loop keeps the early-exit visible without leaning on last.
  • The match_open helper documents the closing -> opening map without leaking runtime references into the replay. Single-character string equality uses eq / ne rather than == / != (which would compare numeric coercions).
  • Bracket characters come from substr($text, $i, 1); this is the most beginner-readable single-character access in Perl and keeps the iteration index visible.
  • The replay highlights the current character, shows the stack updating each frame, and surfaces the final balanced/unbalanced verdict.
stack push/pop Use a plain `@stack` as the open-bracket stack; push by `push @stack, $ch`, pop by `pop @stack`.
matching map A small `match_open($close)` helper returns the expected opener for each closing bracket — three explicit `if`/`elsif` arms keep the lesson compact.