Checking balanced brackets

This example discusses the implementation of an algorithm for checking the balance of square brackets in a string, as well as generating random sequences of brackets for testing.

Introduction

The balanced parenthesis verification algorithm is a classic programming problem that is used to verify the correctness of nested structures. It is used when analyzing the syntax of expressions, verifying the correctness of the structure of HTML/XML documents, and in other cases where matching of opening and closing elements is required.

In this case, the check of the sequence of square brackets is implemented. [ and ]. The algorithm works as follows:

When meeting the opening parenthesis [ the counter is incremented.
When meeting the closing parenthesis ] the counter is decreasing.
If the counter becomes negative, it means that there is an extra closing parenthesis, and the string is considered incorrect.
At the end of the line pass, the counter must be zero for the correct sequence.

In addition to the main verification function, a random sequence generation function is implemented from n pairs of parentheses that can be used to test the algorithm.

# Установка пакета Printf (если еще не установлен)
import Pkg; Pkg.add(["Printf", "Random"])

   Resolving package versions...
   Installed UnicodePlots ─ v3.8.1
    Updating `~/.project/Project.toml`
  [de0858da] + Printf v1.11.0
  No Changes to `~/.project/Manifest.toml`

The main part

The function of checking the balance of brackets

Function balancedbrackets(str) accepts a string as input and checks whether the brackets are correctly placed. [ and ].

The logic of the work:

For each opening parenthesis [ the counter is incremented i.
For each closing ] — it is decreasing.
If the counter value becomes negative, it means that an extra closing parenthesis has been encountered, and the function returns false.
After viewing the line, if the counter value is zero, the brackets are balanced, it is returned true.

Example of behavior:

"[]" → true
"][" → false
"[[[]]]" → true
"[]""]][[" → false

# Подключение модуля Printf для форматированного вывода
using Printf
using Random

"""
Функция `balancedbrackets` принимает строку и проверяет,
сбалансированы ли в ней квадратные скобки.

Это делается путем подсчета:
- при встрече '[' увеличиваем счетчик (i += 1),
- при встрече ']' уменьшаем счетчик (i -= 1).
Если счетчик уходит в минус — слишком много закрывающих скобок.
В конце проверяем, что счетчик равен 0.
"""
function balancedbrackets(str::AbstractString)
    # Инициализируем счетчик
    i = 0
    
    # Проходим по каждому символу строки
    for c in str
        # Увеличиваем счетчик, если открытая скобка
        if c == '[' 
            i += 1 
        # Уменьшаем, если закрытая
        elseif c == ']' 
            i -= 1 
        end
        
        # Если счетчик стал отрицательным — лишняя закрывающая скобка
        if i < 0 
            return false 
        end
    end
    
    # Возвращаем true, только если все скобки нашли пару
    return i == 0
end

balancedbrackets

Random parenthesis sequence generation function

Function brackets(n) generates a string from n pairs of brackets in random order.

How does it work?

"[]" ^ n creates a string "[[][]...]" (repeated pattern n times [])
collect(...) turns it into an array of characters
shuffle(...) randomly shuffles the elements
join(...) puts everything back together in one line

"""
Функция `brackets(n)` создает строку из n пар случайно перемешанных скобок '[' и ']'.
Сначала создается коллекция из n пар символов ("[]" repeated n times),
потом она преобразуется в массив символов и перемешивается функцией shuffle().
Затем результат объединяется в строку с помощью join().
"""
brackets(n::Integer) = join(shuffle(collect(Char, "[]" ^ n)))

brackets

The main logic of the program:

For each number from 0 to 8:

1. A random string of length brackets is generated 2*i (i pairs).

2. The function is called balancedbrackets() to check the balance.

3. The result is displayed in formatted format:

- the string itself

- verification result ("pass" / "fail").

for (test, pass) in map(x -> (x, balancedbrackets(x)), collect(brackets(i) for i = 0:8))
    @printf "%22s %10s\n\n" test pass ? "pass" : "fail"
end

                             pass

                    []       pass

                  [][]       pass

                ][[]][       fail

              [[[][]]]       pass

            ][[][[[]]]       fail

          []]][[[[][]]       fail

        [][[[]][][][]]       pass

      []][[][]][[]][[]       fail

Conclusion

We have reviewed the implementation and application of the algorithm for checking the balance of square brackets in the Julia language.

What was done:

Implemented the function balancedbrackets(), which checks whether the brackets are correctly placed.
An auxiliary function has been written brackets(), which creates random parenthesis strings for testing.
Automatic testing was performed for several values and the output was demonstrated.

This example is important for understanding the principles of data structure analysis and can be useful when working with parsers, syntax checking, and other tasks where the pairing of opening and closing elements is required.

The example was developed using materials from Rosetta Code