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.

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

Basic Implementation

basic.dart
Replay: real traced execution (multi-file project)
void main() {
  final text = '({[]})';
  final pairs = <String, String>{')': '(', ']': '[', '}': '{'};
  final stack = <String>[];
  var balanced = true;
  for (var i = 0; i < text.length; i++) {
    final ch = text[i];
    if (ch == '(' || ch == '[' || ch == '{') {
      stack.add(ch);
    } else {
      if (stack.isEmpty || stack.last != pairs[ch]) {
        balanced = false;
        break;
      }
      stack.removeLast();
    }
  }
  if (stack.isNotEmpty) {
    balanced = false;
  }
  print(balanced);
}

  1. text ← ({[]})

    1void main() {2  final text = '({[]})';3  final pairs = <String, String>{')': '(', ']': '[', '}': '{'};
    values this step({[]})text

  2. stack ← []

    3final pairs = <String, String>{')': '(', ']': '[', '}': '{'};4final stack = <String>[];5var balanced = true;
    values this step[]stack

  3. balanced ← true

    4final stack = <String>[];5var balanced = true;6for (var i = 0; i < text.length; i++) {
    values this steptruebalanced

  4. stack ← [(]

    6for (var i = 0; i < text.length; i++) {7  final ch = text[i];8  if (ch == '(' || ch == '[' || ch == '{') {
    values this step[(]stack(ch

  5. stack ← [(, {]

    6for (var i = 0; i < text.length; i++) {7  final ch = text[i];8  if (ch == '(' || ch == '[' || ch == '{') {
    values this step[(, {]stack{ch

  6. stack ← [(, {, []

    6for (var i = 0; i < text.length; i++) {7  final ch = text[i];8  if (ch == '(' || ch == '[' || ch == '{') {
    values this step[(, {, []stack[ch

  7. stack ← [(, {]

    6for (var i = 0; i < text.length; i++) {7  final ch = text[i];8  if (ch == '(' || ch == '[' || ch == '{') {
    values this step[(, {]stack]ch

  8. stack ← [(]

    6for (var i = 0; i < text.length; i++) {7  final ch = text[i];8  if (ch == '(' || ch == '[' || ch == '{') {
    values this step[(]stack}ch

  9. stack ← []

    6for (var i = 0; i < text.length; i++) {7  final ch = text[i];8  if (ch == '(' || ch == '[' || ch == '{') {
    values this step[]stack)ch

  10. balanced ← true, stdout ← true

    20  }21  print(balanced);22}
    values this steptruebalancedtruestdout[]stack

Complexity

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

Implementation notes

  • Dart: a growable List<String> is a fine stack — add / removeLast are O(1) amortized. stack.isEmpty / stack.last read the top without leaking the underlying storage.
  • The replay shows the current character, the operation (push vs. pop), and the post-step stack contents using a literal [(, {, [] notation rather than any object identity.