这个例子讨论了一个算法的实现,用于检查字符串中方括号的平衡,以及生成用于测试的随机括号序列。
平衡括号验证算法是一个经典的编程问题,用于验证嵌套结构的正确性。 它用于分析表达式的语法,验证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*ii
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 )