---

Mastering Data Structures in Cairo: The Definitive Guide to Matching Brackets

The "Matching Brackets" problem is a classic computer science puzzle that elegantly tests your understanding of the Stack data structure. This guide provides a comprehensive solution in Cairo, explaining the core logic, its real-world applications in systems like Starknet, and a detailed, line-by-line code walkthrough.

Have you ever stared at a compiler error that screams about a missing parenthesis or a misplaced brace? It’s a frustratingly common experience for developers. This small mistake can bring an entire system to a halt. Now, imagine that system is an ancient, powerful mainframe called the Bracketeer™, and a single syntax error could cause a catastrophic crash requiring a full reboot. This is the challenge presented in this exclusive kodikra.com module.

This isn't just a theoretical exercise; it's the bedrock of parsing, validation, and syntax highlighting in almost every programming language, data format, and development tool you use daily. From validating JSON configurations to ensuring the integrity of smart contract data on Starknet, the principles you'll master here are universally applicable. In this deep dive, we will dissect this problem and build a robust solution from scratch using the Cairo programming language, transforming a potential system-crashing bug into a solved problem.

---

What Exactly is the Matching Brackets Problem?

At its core, the Matching Brackets problem is about structural validation. You are given a string that may contain various characters, including three specific types of bracket pairs: parentheses (), square brackets [], and curly braces {}.

The goal is to write a function that determines if the brackets within the string are "balanced." A string of brackets is considered balanced if two conditions are met:

1. Every opening bracket has a corresponding closing bracket of the same type. For example, a ( must be closed by a ), not a ].
2. The brackets are correctly nested. This means any pair of brackets that starts inside another pair must also end inside that same pair.

Let's illustrate with examples:

• "{[()]}" is balanced. The parentheses are nested inside the square brackets, which are in turn nested inside the curly braces. All pairs match correctly.
• "([)]" is not balanced. The square bracket [ opens, then the parenthesis ( opens. However, the ] closes before the ), violating the nesting rule (Last-In, First-Out).
• "}{" is not balanced. A closing bracket appears before its corresponding opening bracket.
• "abc(123)" is balanced. The algorithm should ignore any characters that are not brackets.

This problem forces us to think about order and sequence, making it a perfect candidate for a specific type of data structure designed to handle exactly that: the Stack.

---

Why This Skill is Crucial for Cairo and Web3 Developers

While it may seem like a simple puzzle, bracket matching is a fundamental concept with far-reaching implications, especially in the context of a provable computation language like Cairo and the Starknet ecosystem.

Compiler and Linter Design

The most direct application is in building compilers, interpreters, and code linters. When you write Cairo code, the compiler's first job is to parse it—to break it down into a structured format it can understand. This process, called syntactic analysis, heavily relies on matching brackets, parentheses, and braces to understand the scope of functions, loops, and conditional statements. An imbalance here is a syntax error.

Data Serialization and Validation

Modern applications, both on-chain and off-chain, constantly exchange data using formats like JSON (JavaScript Object Notation). A JSON object is defined by curly braces {} and its arrays by square brackets []. Before processing any incoming JSON data, a parser must first validate its structure. Is it a well-formed JSON? This validation is, in essence, a more complex version of the matching brackets problem.

For a Starknet smart contract, this is critical. If your contract expects input formatted in a specific way (e.g., a complex struct represented as a string), validating its structural integrity before processing can prevent unexpected behavior and potential vulnerabilities.

Mathematical and Logical Expression Parsing

Scientific calculators, database query engines, and even spreadsheet applications need to parse complex mathematical and logical expressions like (a + b) * [c / {d - e}]. To evaluate this correctly, the parser must understand the order of operations, which is dictated by the nesting of parentheses and brackets. The logic to parse these expressions is built upon the same stack-based principles we will explore.

---

How to Solve It: The Elegant Stack-Based Approach

The most efficient and intuitive way to solve the matching brackets problem is by using a Stack data structure. A stack operates on a simple principle: Last-In, First-Out (LIFO). Think of it like a stack of plates; you can only add a new plate to the top, and you can only remove the topmost plate.

This LIFO behavior perfectly mirrors the nesting requirement of brackets. The last opening bracket you encounter must be the first one you close. For example, in "{[()]}", the last bracket opened is (, and it's the first one to be closed by ).

The Algorithm Explained

Here is the step-by-step algorithm we will implement in Cairo:

1. Initialize an empty stack. This stack will be used to store the opening brackets as we find them. In Cairo, this can be an Array.
2. Create a mapping of brackets. We need an easy way to look up the corresponding opening bracket for any closing bracket. A dictionary or hash map is perfect for this, mapping ')' to '(', ']' to '[', and '}' to '{'.
3. Iterate through the input string character by character.
4. For each character, apply the following logic:
   • If the character is an opening bracket ((, [, or {), push it onto the stack.
   • If the character is a closing bracket (), ], or }), we must perform a check:
     • First, is the stack empty? If it is, we have a closing bracket with no corresponding opener. The string is unbalanced. We can stop and return false.
     • If the stack is not empty, pop the last element from the stack. This element should be the most recently seen opening bracket.
     • Compare the popped bracket with the current closing bracket's required opener (using our map). If they don't match, the string is unbalanced. Stop and return false.
   • If the character is not a bracket, simply ignore it and continue to the next character.
5. Perform a final check after the loop. After iterating through the entire string, if the stack is empty, it means every opening bracket found a matching closing partner. The string is balanced, and we return true. If the stack is not empty, it means there are unclosed opening brackets, so the string is unbalanced. Return false.

High-Level Algorithm Flowchart

This ASCII diagram illustrates the decision-making process for each character in the input string.

    ● Start
    │
    ▼
  ┌───────────────────┐
  │ Initialize Stack  │
  │ & Bracket Map     │
  └─────────┬─────────┘
            │
            ▼
  ┌───────────────────┐
  │ Loop Each Char    │
  │ in Input String   │
  └─────────┬─────────┘
            │
            ▼
    ◆ Is it an Opener? (`(`, `[`, `{`)
   ╱                   ╲
 Yes ◀───────────────▶ No
  │                     │
  ▼                     ▼
┌───────────┐     ◆ Is it a Closer? (`)`, `]`, `}`)
│ Push onto │    ╱                   ╲
│ Stack     │   Yes ◀───────────────▶ No (Ignore Char)
└───────────┘    │
                 ▼
           ◆ Is Stack Empty?
          ╱               ╲
        Yes (Error)      No
         │                │
         ▼                ▼
       ┌──────┐      ┌──────────────────┐
       │ Return │      │ Pop from Stack   │
       │ false│      └─────────┬────────┘
       └──────┘               │
                              ▼
                        ◆ Do they Match?
                       ╱                ╲
                     Yes                No (Error)
                      │                  │
                      ▼                  ▼
                 (Continue Loop)       ┌──────┐
                                       │ Return │
                                       │ false│
                                       └──────┘
            │
            ▼ (After Loop)
    ◆ Is Stack Empty?
   ╱               ╲
 Yes                No
  │                  │
  ▼                  ▼
┌───────┐         ┌───────┐
│ Return│         │ Return│
│ true  │         │ false │
└───────┘         └───────┘
    │
    ▼
    ● End

---

Where the Logic is Implemented: A Cairo Code Walkthrough

Now, let's translate our algorithm into functional Cairo code. The following solution, designed for the kodikra learning path, is robust and demonstrates key features of the language like Array, Felt252Dict, and pattern matching.

The Complete Cairo Solution

We'll structure our code into a main function is_paired and a helper function get_bracket_pairs for clarity.

use core::dict::Felt252Dict;

/// Creates a dictionary mapping closing brackets to their opening counterparts.
fn get_bracket_pairs() -> Felt252Dict<u8> {
    let mut pairs: Felt252Dict<u8> = Default::default();
    pairs.insert(')', '(');
    pairs.insert(']', '[');
    pairs.insert('}', '{');
    pairs
}

/// Checks if a given string has balanced brackets.
/// Any non-bracket characters are ignored.
pub fn is_paired(value: ByteArray) -> bool {
    // 1. Initialize an empty stack to store opening brackets.
    let mut stack: Array<u8> = ArrayTrait::new();
    
    // 2. Get the mapping of closing to opening brackets.
    let pairs = get_bracket_pairs();

    // 3. Iterate through each character in the input ByteArray.
    let mut i = 0;
    while i < value.len() {
        let current_char = value.at(i);

        match current_char {
            // 4a. If it's an opening bracket, push it onto the stack.
            '(' | '[' | '{' => {
                stack.append(current_char);
            },
            // 4b. If it's a closing bracket, perform validation.
            ')' | ']' | '}' => {
                // Pop the last opening bracket from the stack.
                // If the stack is empty, `pop_back()` returns None.
                match stack.pop_back() {
                    Option::Some(last_open_bracket) => {
                        // Check if the popped bracket matches the expected one.
                        // We use the `pairs` dictionary to find the expected opener.
                        if *pairs.get(current_char) != last_open_bracket {
                            // Mismatch found (e.g., received ')' but last open was '[').
                            return false;
                        }
                    },
                    Option::None => {
                        // Stack was empty, meaning a closing bracket appeared
                        // without a preceding opening bracket.
                        return false;
                    }
                }
            },
            // 4c. If it's any other character, do nothing and continue.
            _ => {}
        }
        i += 1;
    }

    // 5. After the loop, the string is balanced only if the stack is empty.
    // If the stack is not empty, it means there are unclosed opening brackets.
    stack.is_empty()
}

Line-by-Line Code Explanation

Helper Function: get_bracket_pairs

• fn get_bracket_pairs() -> Felt252Dict<u8>: We define a helper function that returns a Felt252Dict<u8>. This is Cairo's primary dictionary type. It's efficient for key-value lookups.
• let mut pairs: Felt252Dict<u8> = Default::default();: We initialize a new, mutable dictionary.
• pairs.insert(')', '(');: We populate the dictionary. The keys are the closing brackets, and the values are their corresponding opening brackets. This structure makes lookups very convenient: when we see a ), we can quickly ask the dictionary, "What opener does this correspond to?" and get (.

Main Function: is_paired

• pub fn is_paired(value: ByteArray) -> bool: Our public function accepts a ByteArray, which is the standard way to handle strings in Cairo, and returns a bool (true for balanced, false for not).
• let mut stack: Array<u8> = ArrayTrait::new();: This is our stack. We use Cairo's dynamic Array, and we'll treat it like a stack by only using append (to push) and pop_back (to pop).
• let pairs = get_bracket_pairs();: We call our helper to get the bracket mapping.
• while i < value.len() { ... }: A standard loop to iterate over the bytes in the ByteArray.
• let current_char = value.at(i);: We fetch the character at the current index.
• match current_char { ... }: We use a match statement, which is a powerful and clean way to handle different cases in Cairo. It's more readable than a long chain of if-else if statements.
• '(' | '[' | '{' => { stack.append(current_char); }: This arm of the match handles all opening brackets. If the character matches any of these, we simply append it to our stack. This is our "push" operation.
• ')' | ']' | '}' => { ... }: This arm handles all closing brackets. This is where the core validation logic resides.
• match stack.pop_back() { ... }: We try to pop an element from the back of the array. In Cairo, pop_back is safe; it doesn't crash if the array is empty. Instead, it returns an Option: Option::Some(value) if an element was popped, or Option::None if the array was empty. We use another match to handle these two possibilities.
• Option::Some(last_open_bracket) => { ... }: This case runs if the stack was not empty. last_open_bracket now holds the character we just popped.
• if *pairs.get(current_char) != last_open_bracket: This is the crucial comparison. pairs.get(current_char) looks up the expected opening bracket for our current closing bracket. For example, if current_char is ], pairs.get(']') returns [. We then compare this expected value with the actual last_open_bracket we popped from the stack. If they don't match, we've found a nesting error, and we immediately return false.
• Option::None => { return false; }: This case runs if we encountered a closing bracket but the stack was empty. This is an error condition, so we immediately return false.
• _ => {}: The underscore _ is a wildcard pattern. It matches any other character not covered by the previous arms. We do nothing ({}), effectively ignoring all non-bracket characters.
• stack.is_empty(): After the loop finishes, this is the final line of the function. In Cairo, the last expression in a function is automatically its return value. If the stack is empty, this expression evaluates to true (balanced). If any opening brackets remain on the stack, it evaluates to false (unbalanced).

Visualizing the Stack in Action

Let's trace the execution with the input string "{a[(b)]}" to see how the stack evolves.

Input String: { a [ ( b ) ] }
Processing...
  │
  ├─ Char: '{'  ⟶  Action: Push '{'
  │              Stack: ['{']
  │
  ├─ Char: 'a'  ⟶  Action: Ignore
  │              Stack: ['{']
  │
  ├─ Char: '['  ⟶  Action: Push '['
  │              Stack: ['{', '[']
  │
  ├─ Char: '('  ⟶  Action: Push '('
  │              Stack: ['{', '[', '(']
  │
  ├─ Char: 'b'  ⟶  Action: Ignore
  │              Stack: ['{', '[', '(']
  │
  ├─ Char: ')'  ⟶  Action: Pop '('. Match OK.
  │              Stack: ['{', '[']
  │
  ├─ Char: ']'  ⟶  Action: Pop '['. Match OK.
  │              Stack: ['{']
  │
  └─ Char: '}'  ⟶  Action: Pop '{'. Match OK.
                 Stack: [] (Empty)

Loop End.
  │
  ▼
Final Check: Is Stack Empty? Yes.
  │
  ▼
Result: true (Balanced)

---

When to Consider Alternatives: Performance and Edge Cases

The stack-based approach is overwhelmingly the best solution for this problem. However, it's always good practice for a senior engineer to analyze the performance characteristics and consider potential edge cases.

Performance Analysis

• Time Complexity: O(n). The algorithm iterates through the input string of length n exactly once. Each operation inside the loop—pushing to the stack, popping from the stack, and dictionary lookup—is, on average, a constant time operation, O(1). Therefore, the total time complexity is linear with respect to the size of the input string. This is highly efficient.
• Space Complexity: O(n). In the worst-case scenario, the input string could consist entirely of opening brackets (e.g., "((((("). In this case, every character would be pushed onto the stack. The space required by the stack is therefore proportional to the length of the input string, resulting in a linear space complexity.

Handling Edge Cases

Our solution gracefully handles common edge cases:

• Empty String: If the input value is an empty ByteArray, the loop will not run. The function will proceed to the final line, stack.is_empty(). Since the stack is indeed empty, it will correctly return true. An empty string is considered balanced.
• String with No Brackets: If the input is something like "hello world", the loop will iterate through each character. The match statement will always fall through to the wildcard _ => {} case, and the stack will remain empty. The function will correctly return true.
• String with Only Closing Brackets: For an input like "])", on the first character ], the code will attempt to pop_back() from an empty stack. This will result in Option::None, and the function will immediately and correctly return false.
• String with Only Opening Brackets: For an input like "([{", the loop will complete, and all three characters will be on the stack. The final check, stack.is_empty(), will evaluate to false, which is the correct result.

Pros and Cons of the Stack-Based Method

Pros	Cons
Intuitive and Elegant: The LIFO nature of a stack perfectly models the nested structure of brackets, making the logic easy to understand and reason about.	Space Usage: For extremely large inputs with deep nesting, the stack could consume a significant amount of memory (though this is rarely a practical issue).
Highly Efficient: With O(n) time complexity, the solution is as fast as theoretically possible, since every character must be inspected at least once.	Not Concurrency-Friendly (in its simple form): This specific iterative algorithm is inherently sequential. It's not a problem that easily benefits from parallel processing.
Easily Extensible: The logic can be easily adapted to handle other types of paired delimiters, such as XML/HTML tags (e.g., <div> and </div>) or different kinds of quotes.	Limited Scope: This algorithm only validates structure; it does not validate the semantic meaning within the brackets.

---

Frequently Asked Questions (FAQ)

1. What is a Stack and why is it the ideal data structure for this problem?

A Stack is an abstract data type that serves as a collection of elements, with two principal operations: Push, which adds an element to the collection, and Pop, which removes the most recently added element. This "Last-In, First-Out" (LIFO) principle perfectly matches the "first-closed is the last-opened" rule of nested brackets, making it the most natural and efficient tool for this task.

2. How does the provided Cairo solution handle non-bracket characters?

The solution handles non-bracket characters by explicitly ignoring them. The match statement has specific arms for opening and closing brackets. Any character that doesn't fit these patterns is caught by the wildcard arm _ => {}. The empty braces {} signify "do nothing," so the loop simply proceeds to the next character without modifying the stack.

3. What happens if the input string is empty? Is that considered balanced?

Yes, an empty string is considered perfectly balanced. Our algorithm handles this correctly. If the input ByteArray is empty, the while loop condition is immediately false, and the code proceeds to the final statement, stack.is_empty(). Since the stack was initialized as empty and never modified, this returns true.

4. Can this logic be extended to other types of pairs, like XML tags?

Absolutely. The core logic is highly adaptable. To validate XML/HTML tags, you would modify the algorithm: when you encounter an opening tag like <div>, you push "div" onto the stack. When you encounter a closing tag like </div>, you pop from the stack and check if the popped value is "div". This demonstrates the power of the underlying pattern.

5. What is the time and space complexity of this algorithm?

The time complexity is O(n), where 'n' is the length of the input string, because we process each character only once. The space complexity is also O(n) in the worst case, as the stack could potentially store all 'n' characters if the input consists solely of opening brackets.

6. Why use ByteArray for the string input in Cairo?

In modern Cairo (1.0 and later), ByteArray is the preferred type for handling arbitrary string data, especially when dealing with ASCII or UTF-8 encoded text. It provides a flexible, dynamic buffer of bytes, which is more versatile than a single felt252 that has a strict character limit. For a function that needs to parse strings of any length, ByteArray is the standard and correct choice.

7. Is recursion a viable alternative to an iterative stack for this problem?

While it's possible to solve this problem using recursion (where the function calls itself to handle nested structures), it's generally not recommended. A recursive solution can be less intuitive and is vulnerable to "stack overflow" errors if the nesting depth is too large, exceeding the program's call stack limit. The iterative approach using an explicit stack data structure is more robust, memory-efficient, and is the standard professional solution.

---

Conclusion: From Theory to Practical Mastery

The Matching Brackets problem is more than just an academic exercise; it's a gateway to understanding how computers parse and validate the very code we write and the data we use. By implementing a solution in Cairo, you've not only solved a classic computer science puzzle but also gained hands-on experience with fundamental Cairo data structures like Array and Felt252Dict, control flow with match, and the concept of memory-safe operations using Option.

The stack-based algorithm you've mastered is a testament to how choosing the right data structure can lead to a solution that is simple, efficient, and profoundly elegant. This foundational skill will serve you well as you tackle more complex parsing and data validation challenges in your journey through the Cairo 5 learning roadmap and beyond.

As you continue to build on the Starknet ecosystem, you'll find this pattern of structural validation reappearing in various forms. Now, you have the tools and the understanding to handle it with confidence.

Disclaimer: The code in this article is written for modern Cairo versions (2.0+). The Cairo language is continuously evolving, and syntax or library functions may change in future releases. Always consult the official documentation for the latest standards. For a complete overview of the language, be sure to master the Cairo language from scratch with our exclusive guides.

---

Published by Kodikra — Your trusted Cairo learning resource.