Matching Brackets
Check that every bracket, brace and parenthesis in a string is closed by its own kind, in order.
Adapted from Exercism’s problem specification (MIT). Listed under Parsing & Validation.
// FILE: matching_brackets.nomi
//# Checks that every bracket, brace and parenthesis in a text is matched and
//# nested correctly.
/// Whether every bracket, brace and parenthesis in `text` is closed by its
/// own kind, in the right order. Other characters are ignored.
pub fn is_paired(text: String) -> Bool
is_balanced(String.to_codepoints(text), [])
end
/// `awaited` holds the closer each open bracket waits for, innermost first.
fn is_balanced(rest: List<Codepoint>, awaited: List<Codepoint>) -> Bool
case (rest, awaited)
([], _) -> awaited == []
(['(', ..rest], _) -> is_balanced(rest, [')', ..awaited])
(['[', ..rest], _) -> is_balanced(rest, [']', ..awaited])
(['{', ..rest], _) -> is_balanced(rest, ['}', ..awaited])
([cp, ..rest], [next, ..awaited]) when cp == next -> is_balanced(rest, awaited)
([')' or ']' or '}', ..], _) -> False
([_, ..rest], _) -> is_balanced(rest, awaited)
end
end
// FILE: matching_brackets_test.nomi
import matching_brackets
test "checks bracket pairing"
[
("paired square brackets", "[]", True),
("empty string", "", True),
("unpaired brackets", "[[", False),
("wrong ordered brackets", "}{", False),
("wrong closing bracket", "{]", False),
("paired with whitespace", "{ }", True),
("partially paired brackets", "{[])", False),
("simple nested brackets", "{[]}", True),
("several paired brackets", "{}[]", True),
("paired and nested brackets", "([{}({}[])])", True),
("unopened closing brackets", "{[)][]}", False),
("unpaired and nested brackets", "([{])", False),
("paired and wrong nested brackets", "[({]})", False),
("paired and wrong nested brackets but innermost are correct", "[({}])", False),
("paired and incomplete brackets", "{}[", False),
("too many closing brackets", "[]]", False),
("early unexpected brackets", ")()", False),
("early mismatched brackets", "{)()", False),
("math expression", "(((185 + 223.85) * 15) - 543)/2", True),
(
"complex latex expression",
"\\left(\\begin{array}{cc} \\frac{1}{3} & x\\\\ \\mathrm{e}^{x} &... x^2 \\end{array}\\right)",
True,
),
]
|> subtests (description, text, expected), description
assert matching_brackets.is_paired(text) == expected
end
endok checks bracket pairing (20 cases)
test result: ok. 20 passed, 0 failed
How it’s written
Section titled “How it’s written”- The string is scanned as
String.to_codepoints, so each bracket is a codepoint literal in a pattern (style guide §20). - The stack holds the closer each open bracket waits for, so a closing bracket only has to equal the stack’s head.
- One
caseover the pair(rest, awaited)with list patterns. A first version matchedrestalone and nested acase awaitedin the closer arm;fmtthen broke every arm of the outercaseonto two lines, which hid the shape, so the pair form replaced it. - One
subteststable for all 20 cases. - A closer that does not match the stack’s head ends the scan:
([')' or ']' or '}', ..], _) -> False, anorpattern nested in the list pattern. A closer that does match is any codepoint equal to the head, since only closers are pushed. Matching the closer by name there too ([')' or ']' or '}' as closer, ..rest]) made the arm too long for one line, andfmtthen broke every arm onto two lines.