检查平衡括号
这个例子讨论了一个算法的实现，用于检查字符串中方括号的平衡，以及生成用于测试的随机括号序列。
导言
平衡括号验证算法是一个经典的编程问题，用于验证嵌套结构的正确性。 它用于分析表达式的语法，验证HTML/XML文档结构的正确性，以及其他需要匹配打开和关闭元素的情况。
在这种情况下，实施方括号序列的检查。 [ 和 ]. 该算法的工作原理如下:
- 当满足左括号
[计数器递增。 - 当满足右括号
]计数器正在减少。 - 如果计数器变为负数，则表示有一个额外的右括号，并且该字符串被认为是不正确的。
- 在行程结束时，计数器必须为零以获得正确的序列。
除了主验证功能外，还实现了随机序列生成功能 n 可用于测试算法的括号对。
# Установка пакета Printf (если еще не установлен)
import Pkg; Pkg.add(["Printf", "Random"])
主要部分
检查括号平衡的功能
功能 balancedbrackets(str) 接受字符串作为输入，并检查括号是否正确放置。 [ 和 ].
工作的逻辑:
-每个左括号 [ 计数器递增 i.
-每次关闭 ] -它正在减少。
-如果计数器值变为负数，则表示遇到了额外的右括号，函数返回 false.
-查看行后，如果计数器值为零，括号平衡，则返回 true.
行为示例:
"[]"→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
随机括号序列生成函数
功能 brackets(n) 从 n 成对的括号中的随机顺序。
它是如何工作的？
"[]" ^ n创建字符串"[[][]...]"（重复模式n次[])collect(...)把它变成一个字符数组shuffle(...)随机洗牌的元素join(...)把所有的东西放在一起
"""
Функция `brackets(n)` создает строку из n пар случайно перемешанных скобок '[' и ']'.
Сначала создается коллекция из n пар символов ("[]" repeated n times),
потом она преобразуется в массив символов и перемешивается функцией shuffle().
Затем результат объединяется в строку с помощью join().
"""
brackets(n::Integer) = join(shuffle(collect(Char, "[]" ^ n)))
程序的主要逻辑:
对于从0到8的每个数字:
1. 生成一个随机的长度括号字符串 2*i (i 对）。
2. 函数被调用 balancedbrackets() 检查余额。
3. 结果以格式化格式显示:
-字符串本身
-验证结果 ("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
结论
我们回顾了Julia语言中检查方括号平衡的算法的实现和应用。
做了什么:
-实现了功能 balancedbrackets()，其中检查括号是否正确放置。
-已编写辅助函数 brackets()，它创建用于测试的随机括号字符串。
-对几个值进行了自动测试，并演示了输出。
此示例对于理解数据结构分析的原理非常重要，并且在处理解析器、语法检查和其他需要打开和关闭元素配对的任务时非常有用。
该示例是使用[Rosetta代码]的材料开发的（https://rosettacode.org/wiki/Balanced_brackets ）