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

local function match_open(close)
	if close == ")" then
		return "("
	elseif close == "]" then
		return "["
	elseif close == "}" then
		return "{"
	end
	return " "
end

local text = "({[]})"
local stack = {}
local balanced = true
local i = 1
while balanced and i <= #text do
	local ch = string.sub(text, i, i)
	if ch == "(" or ch == "[" or ch == "{" then
		stack[#stack + 1] = ch
	else
		if #stack == 0 or stack[#stack] ~= match_open(ch) then
			balanced = false
		else
			stack[#stack] = nil
		end
	end
	i = i + 1
end
if #stack ~= 0 then
	balanced = false
end
if balanced then
	print("True")
else
	print("False")
end

Complexity

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

Implementation notes

Lua: a plain table with stack[#stack + 1] = ch for push and stack[#stack] = nil for pop is the smallest honest stack shape; reaching for table.insert / table.remove would hide the explicit push/pop pattern. A balanced flag plus while balanced and i <= #text do keeps the early-exit visible without leaning on break.
The match_open helper documents the closing -> opening map without leaking runtime references into the replay.
string.sub(text, i, i) is the canonical single-byte extraction for an ASCII bracket string; the lesson does not exercise multibyte sequences.
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 = {}` table as the open-bracket stack; push by `stack[#stack + 1] = ch`, pop by `stack[#stack] = nil`.

matching map A small `match_open(close)` helper returns the expected opener for each closing bracket — three explicit branches keep the lesson compact.