Home
3
Cobol

Matching Brackets in Cobol: Complete Solution & Deep Dive Guide

Code Debug

Mastering Stack Logic: A Deep Dive into Cobol's Matching Brackets Challenge

Solving the matching brackets problem in Cobol involves iterating through an input string and using a stack-like data structure, typically an array with a pointer, to manage opening brackets. When a closing bracket is found, it must match the last-pushed opening bracket, ensuring all pairs are correctly nested and balanced.

Imagine you're a developer tasked with maintaining a critical mainframe system that processes thousands of configuration files daily. A single misplaced brace } or a forgotten parenthesis ) in one of these files could bring the entire batch process to a grinding halt, costing time and resources. This isn't just a hypothetical scenario; it's a daily reality in the world of data parsing and syntax validation.

The core of this challenge lies in ensuring that every opening symbol has a corresponding closing symbol in the correct order. This is the essence of the "Matching Brackets" problem, a classic computer science puzzle that serves as a gateway to understanding more complex parsing algorithms. In this guide, we will dissect this problem and build a robust solution from scratch using Cobol, a language renowned for its stability and power in enterprise environments. You won't just get a block of code; you'll gain a fundamental understanding of stack data structures and their practical application, a skill that transcends any single programming language.

What is the Matching Brackets Problem?

The Matching Brackets problem, at its heart, is a challenge of structural validation. You are given a string of text that may contain various types of brackets, such as parentheses (), square brackets [], and curly braces {}. The goal is to write a program that can determine if the brackets within the string are "balanced."

For a string to be considered balanced, two conditions must be met:

  1. Every opening bracket must have a corresponding closing bracket of the same type. For example, a { must be closed by a }, not a ).
  2. The brackets must be correctly nested. The sequence of brackets must follow a "Last-In, First-Out" (LIFO) order. An opening bracket that appears later in the string must be closed before an opening bracket that appeared earlier.

Let's look at some examples to clarify:

  • {}() - Balanced. The curly braces are a pair, and the parentheses are a pair.
  • {([()_])} - Balanced. All brackets are nested correctly and have a matching partner. Non-bracket characters are ignored.
  • (} - Not Balanced. The opening parenthesis is incorrectly closed by a curly brace.
  • [(]) - Not Balanced. The square bracket is opened, then the parenthesis is opened. The parenthesis must be closed before the square bracket can be closed.
  • { - Not Balanced. The opening curly brace is never closed.

This validation is a foundational concept in computer science, forming the basis for how compilers check your code's syntax and how data formats like JSON or XML are parsed and verified.

Why This Problem is Crucial for Developers

You might wonder why we're tackling a classic algorithm problem in a language like Cobol. The reality is that the principles behind the Matching Brackets problem are universally applicable and particularly relevant in the enterprise environments where Cobol thrives.

The core applications include:

  • Syntax Highlighting and Linting: Code editors use this logic to check in real-time if you've closed all your functions, loops, and conditional blocks correctly.
  • Compilers and Interpreters: Before your code can be executed, the compiler must parse it to ensure its structure is valid. This includes verifying that all parentheses in a mathematical expression or all braces in a code block are balanced.
  • Data Serialization: Formats like JSON (JavaScript Object Notation) and XML (eXtensible Markup Language) rely heavily on nested structures using braces and brackets. Parsers for these formats must validate the structure before they can safely extract the data.
  • Mathematical Expression Evaluation: In scientific and financial computing, complex formulas often use nested parentheses to define the order of operations. A calculator or evaluation engine must first confirm the parentheses are balanced.

For a Cobol developer, this skill is directly transferable to validating complex data files, parsing control card statements in JCL, or ensuring the integrity of structured data streams processed in batch jobs. Mastering this concept demonstrates a deep understanding of data structures and algorithmic thinking, valuable assets for any programmer.

How to Solve It: The Stack Data Structure

The most elegant and efficient way to solve the Matching Brackets problem is by using a data structure called a stack. A stack operates on a simple principle: Last-In, First-Out (LIFO). Think of it like a stack of plates: you add a new plate to the top, and when you need a plate, you take the one from the top. The last plate you put on is the first one you take off.

A stack has two primary operations:

  • Push: Add an item to the top of the stack.
  • Pop: Remove the item from the top of the stack.

Here’s how we apply this to our problem:

  1. We create an empty stack. In Cobol, this will be an array with a pointer (an index variable) that keeps track of the "top" of the stack.
  2. We iterate through the input string, one character at a time.
  3. If we encounter an opening bracket ((, [, or {), we push it onto the stack.
  4. If we encounter a closing bracket (), ], or }), we check the top of the stack.
    • If the stack is empty, it means we have a closing bracket with no matching opener. The string is unbalanced.
    • If the stack is not empty, we "peek" at the item on top. If it's the corresponding opening bracket, we pop it from the stack and continue.
    • If the item on top is not the corresponding opening bracket, the nesting is incorrect. The string is unbalanced.
  5. After iterating through the entire string, we check the stack one last time. If the stack is empty, it means every opening bracket found a matching closing partner. The string is balanced!
  6. If the stack is not empty, it means there are leftover opening brackets that were never closed. The string is unbalanced.

ASCII Art Diagram: The Stack Logic in Action

Here is a visual representation of how the stack processes the string "{[()]}":

  ● Start Processing: "{[()]}"
  │
  ├─ Character: '{'  ⟶  Action: PUSH
  │                    Stack: ['{']
  ▼
  ├─ Character: '['  ⟶  Action: PUSH
  │                    Stack: ['{', '[']
  ▼
  ├─ Character: '('  ⟶  Action: PUSH
  │                    Stack: ['{', '[', '(']
  ▼
  ├─ Character: ')'  ⟶  Action: MATCH & POP
  │                    (Matches top '(', pop it)
  │                    Stack: ['{', '[']
  ▼
  ├─ Character: ']'  ⟶  Action: MATCH & POP
  │                    (Matches top '[', pop it)
  │                    Stack: ['{']
  ▼
  ├─ Character: '}'  ⟶  Action: MATCH & POP
  │                    (Matches top '{', pop it)
  │                    Stack: [] (Empty)
  ▼
  ● End of String
  │
  └─ Final Check: Is stack empty? ⟶ Yes
                                     │
                                     ▼
                                  [Result: Balanced]

Where the Logic Lives: The Cobol Implementation

Now, let's translate this logic into a fully functional Cobol program. Cobol doesn't have a built-in stack data type, but we can easily simulate one using an array (an OCCURS clause) and an integer variable to act as our stack pointer.

This program is written using modern, free-format Cobol, which is fully supported by compilers like GnuCOBOL. It's structured, readable, and demonstrates how to handle this classic algorithm effectively.

The Complete Cobol Source Code


      ******************************************************************
      * Program:   BRACKETS
      * Author:    kodikra.com
      * Date:      Current
      * Purpose:   Solves the Matching Brackets problem from the
      *            kodikra.com exclusive learning path.
      * Compiler:  GnuCOBOL 3.1.2+
      ******************************************************************
       IDENTIFICATION DIVISION.
       PROGRAM-ID. MatchingBrackets.

       DATA DIVISION.
       WORKING-STORAGE SECTION.
      *-- Input and Control Variables
       01 WS-INPUT-STRING           PIC X(100) VALUE SPACES.
       01 WS-INPUT-LEN              PIC 9(3)   VALUE 0.
       01 I                         PIC 9(3)   VALUE 0.
       01 WS-CURRENT-CHAR           PIC X(1).

      *-- Result Flag and Message
       01 WS-IS-BALANCED-FLAG       PIC X(1)   VALUE 'Y'.
          88 IS-BALANCED                       VALUE 'Y'.
          88 IS-NOT-BALANCED                   VALUE 'N'.

       01 WS-RESULT-MSG             PIC X(50).

      *-- Stack Implementation
      *   We use an array to simulate a stack.
      *   WS-STACK-POINTER points to the current top of the stack.
       01 WS-STACK-POINTER          PIC 9(3)   VALUE 0.
       01 WS-STACK-AREA.
          05 WS-STACK-CHARS         PIC X(1) OCCURS 100 TIMES
                                   INDEXED BY STACK-IDX.

      *-- Bracket Definitions
       01 CONSTANTS.
          05 OPENING-BRACKETS       PIC X(3) VALUE "({[".
          05 CLOSING-BRACKETS       PIC X(3) VALUE ")}]".

       PROCEDURE DIVISION.
      ******************************************************************
      *   MAIN DRIVER LOGIC
      ******************************************************************
       1000-MAIN-PROCEDURE.
           DISPLAY "Enter a string to check for balanced brackets: ".
           ACCEPT WS-INPUT-STRING.

           PERFORM 2000-VALIDATE-BRACKETS.
           PERFORM 3000-DISPLAY-RESULT.

           STOP RUN.

      ******************************************************************
      *   Core validation logic. Iterates through the string and
      *   manages the stack.
      ******************************************************************
       2000-VALIDATE-BRACKETS.
           MOVE FUNCTION UPPER-CASE(WS-INPUT-STRING) TO WS-INPUT-STRING.
           MOVE FUNCTION LENGTH(FUNCTION TRIM(WS-INPUT-STRING))
               TO WS-INPUT-LEN.

           IF WS-INPUT-LEN = 0
              MOVE 'Y' TO WS-IS-BALANCED-FLAG
              GO TO 2999-EXIT
           END-IF.

           PERFORM VARYING I FROM 1 BY 1 UNTIL I > WS-INPUT-LEN
              MOVE WS-INPUT-STRING(I:1) TO WS-CURRENT-CHAR

              EVALUATE TRUE
                 WHEN WS-CURRENT-CHAR = "(" OR "[" OR "{"
                    PERFORM 2100-PUSH-TO-STACK
                 WHEN WS-CURRENT-CHAR = ")" OR "]" OR "}"
                    PERFORM 2200-POP-FROM-STACK
              END-EVALUATE

      *      -- Early exit if a mismatch was found
              IF IS-NOT-BALANCED
                 GO TO 2999-EXIT
              END-IF
           END-PERFORM.

      *    -- After loop, if stack is not empty, it's unbalanced
           IF WS-STACK-POINTER > 0
              SET IS-NOT-BALANCED TO TRUE
           END-IF.

       2999-EXIT.
           EXIT.

      ******************************************************************
      *   Pushes an opening bracket onto our stack.
      ******************************************************************
       2100-PUSH-TO-STACK.
      *    -- Check for stack overflow
           IF WS-STACK-POINTER >= 100
              DISPLAY "Error: Stack overflow."
              SET IS-NOT-BALANCED TO TRUE
           ELSE
              ADD 1 TO WS-STACK-POINTER
              MOVE WS-CURRENT-CHAR TO WS-STACK-CHARS(WS-STACK-POINTER)
           END-IF.

      ******************************************************************
      *   Pops from stack if closing bracket matches the opener.
      ******************************************************************
       2200-POP-FROM-STACK.
      *    -- Check for stack underflow (closing bracket with no opener)
           IF WS-STACK-POINTER = 0
              SET IS-NOT-BALANCED TO TRUE
           ELSE
              PERFORM 2210-CHECK-MATCH
           END-IF.

      ******************************************************************
      *   Helper paragraph to check if closing bracket matches the
      *   bracket at the top of the stack.
      ******************************************************************
       2210-CHECK-MATCH.
           EVALUATE WS-CURRENT-CHAR
              WHEN ")"
                 IF WS-STACK-CHARS(WS-STACK-POINTER) = "("
                    SUBTRACT 1 FROM WS-STACK-POINTER
                 ELSE
                    SET IS-NOT-BALANCED TO TRUE
                 END-IF
              WHEN "]"
                 IF WS-STACK-CHARS(WS-STACK-POINTER) = "["
                    SUBTRACT 1 FROM WS-STACK-POINTER
                 ELSE
                    SET IS-NOT-BALANCED TO TRUE
                 END-IF
              WHEN "}"
                 IF WS-STACK-CHARS(WS-STACK-POINTER) = "{"
                    SUBTRACT 1 FROM WS-STACK-POINTER
                 ELSE
                    SET IS-NOT-BALANCED TO TRUE
                 END-IF
           END-EVALUATE.

      ******************************************************************
      *   Formats and displays the final result to the user.
      ******************************************************************
       3000-DISPLAY-RESULT.
           IF IS-BALANCED
              MOVE "Result: The string is BALANCED." TO WS-RESULT-MSG
           ELSE
              MOVE "Result: The string is NOT BALANCED." TO WS-RESULT-MSG
           END-IF.
           DISPLAY "----------------------------------------".
           DISPLAY "Input String: " FUNCTION TRIM(WS-INPUT-STRING).
           DISPLAY WS-RESULT-MSG.
           DISPLAY "----------------------------------------".

       END PROGRAM MatchingBrackets.

How to Compile and Run

If you have a modern Cobol compiler like GnuCOBOL installed, you can compile and run this program from your terminal.


# Compile the program (the -x flag creates an executable)
# The -free flag indicates modern, free-format source code
$ cobc -x -free MatchingBrackets.cbl

# Run the executable
$ ./MatchingBrackets

The program will then prompt you to enter a string, and it will output its analysis.

Detailed Code Walkthrough

Let's break down the Cobol code into its key components to understand exactly how it works. The program follows a structured, top-down design, which is a hallmark of good Cobol programming.

ASCII Art Diagram: Cobol Program Flow

This diagram shows the high-level control flow of our program.

    ● Start (1000-MAIN-PROCEDURE)
    │
    ├─ Accept User Input
    │
    ▼
  ┌────────────────────────┐
  │ 2000-VALIDATE-BRACKETS │
  └──────────┬─────────────┘
             │
             ├─ Loop through each character of the input string
             │
             ▼
        ◆ Is Char a Bracket?
       ╱         ╲
      Yes         No (Ignore)
      │
      ▼
  ◆ Opening or Closing?
 ╱                       ╲
Opening Bracket        Closing Bracket
 │                         │
 ▼                         ▼
┌─────────────────┐   ┌──────────────────┐
│ 2100-PUSH-TO-STACK │   │ 2200-POP-FROM-STACK │
└─────────────────┘   └─────────┬──────────┘
                                  │
                                  ▼
                             ◆ Is match valid?
                            ╱               ╲
                           Yes (Pop)         No (Set Error Flag)
                            │
                            ▼
                           Continue Loop
    │
    └─ After Loop: Check if stack is empty
    │
    ▼
  ┌───────────────────┐
  │ 3000-DISPLAY-RESULT │
  └───────────────────┘
    │
    ▼
    ● Stop Run

1. DATA DIVISION - Setting the Stage

This is where we define all our variables. The most important parts are:

  • WS-INPUT-STRING: A character buffer to hold the string provided by the user.
  • WS-IS-BALANCED-FLAG: A flag variable that tracks the validation status. We use an 88 level condition name (IS-BALANCED, IS-NOT-BALANCED) to make our procedural code more readable (e.g., IF IS-BALANCED...).
  • WS-STACK-AREA: This is our simulated stack. WS-STACK-CHARS OCCURS 100 TIMES creates an array that can hold up to 100 characters.
  • WS-STACK-POINTER: This numeric variable is the key to our stack. It holds the index of the last item pushed. A value of 0 means the stack is empty.

2. 1000-MAIN-PROCEDURE - The Conductor

This is the main entry point and driver of the program. Its job is simple: get the input, call the validation logic, call the display logic, and then terminate. This separation of concerns makes the program easy to follow and maintain.

3. 2000-VALIDATE-BRACKETS - The Core Logic

This paragraph contains the heart of the algorithm.

  • It first gets the actual length of the input string using FUNCTION TRIM to ignore trailing spaces.
  • The PERFORM VARYING I FROM 1 BY 1... statement creates a loop that iterates over each character of the string.
  • Inside the loop, an EVALUATE statement (similar to a switch in other languages) efficiently checks the current character.
  • If it's an opening bracket, it calls 2100-PUSH-TO-STACK.
  • If it's a closing bracket, it calls 2200-POP-FROM-STACK.
  • Any other character is simply ignored, fulfilling the problem's requirements.
  • Crucially, after the loop finishes, it checks if WS-STACK-POINTER is greater than 0. If it is, it means we have unclosed opening brackets, and the string is marked as not balanced.

4. 2100-PUSH-TO-STACK and 2200-POP-FROM-STACK

These two paragraphs implement our stack operations.

  • Push: The 2100-PUSH-TO-STACK paragraph first checks for a "stack overflow" (trying to push onto a full stack). If there's space, it increments the WS-STACK-POINTER and then places the current character into the WS-STACK-CHARS array at that new position.
  • Pop: The 2200-POP-FROM-STACK paragraph first checks for a "stack underflow" (trying to pop from an empty stack). If the stack isn't empty, it calls 2210-CHECK-MATCH. This helper paragraph compares the current closing bracket with the character at the top of the stack (WS-STACK-CHARS(WS-STACK-POINTER)). If they are a valid pair, it decrements the WS-STACK-POINTER, effectively "popping" the item. If not, it sets the error flag.

Pros and Cons of This Approach

Every algorithmic solution has trade-offs. The stack-based approach is widely considered the best for this problem, but it's still valuable to analyze its characteristics.

Pros Cons / Risks
High Efficiency: The time complexity is O(n), where 'n' is the length of the string. We only need to iterate through the string once, making it very fast even for long inputs. Fixed Memory Usage: Our Cobol implementation uses a fixed-size array for the stack. If an input string has a nesting depth greater than the array size (100 in our case), it will cause a stack overflow.
Simplicity and Readability: The logic is straightforward and easy to understand. The concepts of push and pop map directly to the problem's requirements. Not Thread-Safe (by default): If this logic were part of a multi-threaded program, the shared stack variables would need to be properly synchronized to avoid race conditions. This is less of a concern in traditional single-threaded batch Cobol.
Easily Extensible: Adding new types of bracket pairs (like < and >) is trivial. You would simply add them to the conditions in the EVALUATE statements. Manual Memory Management: Unlike languages with built-in dynamic data structures, we have to manage our stack pointer (WS-STACK-POINTER) manually. A bug here (e.g., forgetting to increment or decrement) would break the entire algorithm.

Frequently Asked Questions (FAQ)

1. What is a stack and why is it essential for this problem?
A stack is a "Last-In, First-Out" (LIFO) data structure. It's essential here because the nature of nested brackets is also LIFO—the last opening bracket you see must be the first one to be closed. The stack perfectly models this behavior.
2. Can this logic handle other types of pairs, like XML tags < and >?
Yes, absolutely. The core logic is extensible. You would modify the EVALUATE statements in the Cobol code to recognize < as an opening character and > as a closing one. The push/pop mechanism remains identical.
3. What happens if the input string is empty?
An empty string is technically balanced because it contains no unbalanced brackets. Our code handles this gracefully: the PERFORM VARYING loop is never entered, the stack remains empty, and the final check passes, correctly identifying it as balanced.
4. How does this Cobol solution handle memory for the stack?
The solution uses static memory allocation. In the WORKING-STORAGE SECTION, we declare an array WS-STACK-CHARS with a fixed size (OCCURS 100 TIMES). This memory is allocated when the program starts and is fixed throughout its execution. This is a common and efficient pattern in Cobol.
5. Is this approach efficient for very long strings?
Yes. The algorithm has a linear time complexity, denoted as O(n). This means the time it takes to run is directly proportional to the length of the string. It processes each character only once, so it scales very well and is suitable for large inputs, provided the nesting depth doesn't exceed the stack's fixed size.
6. Why use Cobol for a classic algorithm problem?
Solving classic problems like this in Cobol is an excellent way to master the language's fundamental constructs, such as loops, conditional logic, and data structures. It demonstrates that Cobol is a fully capable, Turing-complete language that can be used to implement complex logic, a vital skill for anyone working on enterprise systems. For more on the power of Cobol, dive deeper into our Cobol language resources.
7. What are common mistakes when implementing this in Cobol?
The most common mistakes include: 1) Forgetting to check if the stack is empty before popping (stack underflow). 2) Forgetting to check if the stack is empty after the loop finishes (unclosed brackets). 3) Off-by-one errors with the stack pointer index. 4) Not handling non-bracket characters correctly (i.e., they should be ignored).

Conclusion: Timeless Logic in a Timeless Language

We've journeyed from the theoretical concept of the Matching Brackets problem to a complete, working implementation in Cobol. The solution highlights a powerful truth in software development: a solid understanding of fundamental data structures, like the stack, is a universal tool that empowers you to solve complex problems in any language, from Python to Cobol.

By building this program, you've not only solved a specific challenge from the kodikra.com Cobol learning path but also sharpened your ability to think algorithmically. You've seen how to simulate a dynamic data structure in a language known for its static nature and how to write clean, structured, and maintainable code—a skill that is invaluable in the world of enterprise software.

Technology Disclaimer: The solution and code snippets in this article were developed and tested using GnuCOBOL 3.1.2. While the core logic is standard, specific syntax and intrinsic functions may vary slightly between different Cobol compilers.

Published by Kodikra — Your trusted Cobol learning resource.

Post a Comment