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.

stack push/pop Use a `Stack<char>` for the open-bracket stack; push by `stack.Push(ch)`, pop by `stack.Pop()`.
matching map A small `MatchOpen(close)` helper returns the expected opener for each closing bracket — three explicit `switch` arms keep the lesson compact.

Basic Implementation

basic.cs
Replay: real traced execution (multi-file project)
using System;
using System.Collections.Generic;

class Program {
	static char MatchOpen(char close) {
		switch (close) {
			case ')': return '(';
			case ']': return '[';
			case '}': return '{';
			default: return (char)0;
		}
	}

	static void Main() {
		string text = "({[]})";
		Stack<char> stack = new Stack<char>();
		bool balanced = true;
		for (int i = 0; i < text.Length; i++) {
			char ch = text[i];
			if (ch == '(' || ch == '[' || ch == '{') {
				stack.Push(ch);
			} else {
				if (stack.Count == 0 || stack.Peek() != MatchOpen(ch)) {
					balanced = false;
					break;
				}
				stack.Pop();
			}
		}
		if (stack.Count != 0) {
			balanced = false;
		}
		Console.WriteLine(balanced ? "True" : "False");
	}
}

  1. text ← ({[]})

    14static void Main() {15	string text = "({[]})";16	Stack<char> stack = new Stack<char>();
    values this step({[]})text

  2. stack ← []

    15string text = "({[]})";16Stack<char> stack = new Stack<char>();17bool balanced = true;
    values this step[]stack

  3. balanced ← true

    16Stack<char> stack = new Stack<char>();17bool balanced = true;18for (int i = 0; i < text.Length; i++) {
    values this steptruebalanced

  4. stack ← [(]

    18for (int i = 0; i < text.Length; i++) {19	char ch = text[i];20	if (ch == '(' || ch == '[' || ch == '{') {
    values this step[(]stack(ch

  5. stack ← [(, {]

    18for (int i = 0; i < text.Length; i++) {19	char ch = text[i];20	if (ch == '(' || ch == '[' || ch == '{') {
    values this step[(, {]stack{ch

  6. stack ← [(, {, []

    18for (int i = 0; i < text.Length; i++) {19	char ch = text[i];20	if (ch == '(' || ch == '[' || ch == '{') {
    values this step[(, {, []stack[ch

  7. stack ← [(, {]

    18for (int i = 0; i < text.Length; i++) {19	char ch = text[i];20	if (ch == '(' || ch == '[' || ch == '{') {
    values this step[(, {]stack]ch

  8. stack ← [(]

    18for (int i = 0; i < text.Length; i++) {19	char ch = text[i];20	if (ch == '(' || ch == '[' || ch == '{') {
    values this step[(]stack}ch

  9. stack ← []

    18for (int i = 0; i < text.Length; i++) {19	char ch = text[i];20	if (ch == '(' || ch == '[' || ch == '{') {
    values this step[]stack)ch

  10. balanced ← true, stdout ← True

    32	}33	Console.WriteLine(balanced ? "True" : "False");34}
    values this steptruebalancedTruestdout[]stack

Complexity

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

Implementation notes

  • C#: Stack<char> with Push / Pop / Peek is the smallest honest stack shape; its managed backing storage grows as needed and is reclaimed by GC. The stack.Count == 0 check guards Peek() and Pop(), which would throw on an empty stack.
  • The MatchOpen helper documents the closing -> opening map without leaking runtime references into the replay. The lesson iterates C# char values from a string, which is enough for this ASCII bracket set.
  • The replay highlights the current character, shows the stack updating each frame, and surfaces the final balanced/unbalanced verdict.