Lean4

7. Valid parentheses

MediumProgramAcademy Pass20 points

A string made of the characters (, ), [, ], { and } is balanced when every opening bracket is closed by a bracket of the same kind, and brackets close in the reverse order they were opened.

Write balanced s, which is true exactly when s is balanced.

Examples

  1. Inputbalanced "()"Outputtrue
  2. Inputbalanced "()[]{}"Outputtrue
  3. Inputbalanced "(]"Outputfalse
  4. Inputbalanced "([)]"Outputfalse

Submitting also runs 9 hidden tests.

Constraints

  • The empty string is balanced.
  • Only the six bracket characters occur in the tests.
stringsstacksrecursion

Running and submitting solutions, the hints and the editorial come with the Academy Pass. The daily problem is open to every account.

Learn the ideas

Similar problems

Solution.lean
Loading…
Loading editor…
3#guard (balanced "()") = (true)
4#guard (balanced "()[]{}") = (true)
5#guard (balanced "(]") = (false)
6#guard (balanced "([)]") = (false)
examples

Run checks your code against the examples and your custom inputs and records nothing. Submit also runs the hidden tests, confirms the axioms your proof uses and records the result. Each uses one compiler check.

ReadyLn 1, Col 1Lean 4
Draft saved in this browser