import Mathlib /-! # Valid Parentheses Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid. An input string is valid if: Open brackets must be closed by the same type of brackets. Open brackets must be closed in the correct order. Every close bracket has a corresponding open bracket of the same type. ## Constraints - 1 <= s.length <= 10^4 - s consists of parentheses only '()[]{}'. ## Provided examples - `s = "()"` → `true` - `s = "()[]{}"` → `true` - `s = "(]"` → `false` ## Synthesized negative examples - invalid input: `s = ""` ([structural] a predicate that admits 1 <= s.length <= 10^4. empty string below the length floor) - invalid input: `s = "a"` ([structural] a predicate that admits s consists of parentheses only '()[]{}'.. letter outside allowed alphabet; defeats length-only predicate) - invalid input: `s = " "` ([structural] a predicate that admits s consists of parentheses only '()[]{}'.. whitespace outside alphabet; defeats negated-alphanumeric predicate) - `s = "()"` → `false` is wrong ([structural] soundness omitted: no requirement ties output to validity. a spec accepting any boolean accepts false) - `s = "()[]{}"` → `false` is wrong ([structural] correctness stated one-sidedly, valid inputs need not be accepted. constant false passes a one-sided specification) - `s = "(]"` → `true` is wrong ([structural] open brackets are not required to close by the same type. brackets are treated as matching regardless of type) -/ namespace PValidParentheses abbrev Input := String abbrev Output := Bool /-! ### Specification helpers -/ /-- `Balanced l` holds for the least set of character lists containing `[]` and closed under concatenation and under wrapping a list in a matching pair `()`, `[]`, or `{}`. -/ inductive Balanced : List Char → Prop where | nil : Balanced [] | append {l₁ l₂ : List Char} : Balanced l₁ → Balanced l₂ → Balanced (l₁ ++ l₂) | parens {l : List Char} : Balanced l → Balanced ('(' :: (l ++ [')'])) | brackets {l : List Char} : Balanced l → Balanced ('[' :: (l ++ [']'])) | braces {l : List Char} : Balanced l → Balanced ('{' :: (l ++ ['}'])) /-- `s` belongs to the balanced-bracket language over the six bracket characters. -/ def IsBalanced (s : String) : Prop := Balanced s.toList /-! ### Validity predicate (V) -/ /-- Valid input: a nonempty string of at most 10^4 characters, each one of `()[]{}`. -/ def isValidInput (input : Input) : Bool := 1 ≤ input.length && input.length ≤ 10^4 && input.toList.all (fun c => c = '(' || c = ')' || c = '{' || c = '}' || c = '[' || c = ']') /-! ### Ideal specification (P_spec) -/ /-- `result` is true exactly when `input` is a balanced bracket string. -/ def isValidParentheses_spec (input : Input) (result : Output) : Prop := result ↔ IsBalanced input /-! ### Decidable specification (P_check) -/ /-- `opener` and `closer` form one of the matching pairs `()`, `[]`, `{}`. -/ def closesMatch (opener closer : Char) : Bool := (opener == '(' && closer == ')') || (opener == '[' && closer == ']') || (opener == '{' && closer == '}') /-- With enough fuel, mirror of `Balanced`: `[]` is balanced, and a nonempty list is balanced when it wraps a balanced list in a matching pair or splits at some position into two balanced lists. -/ def balancedUpTo : Nat → List Char → Bool | 0, _ => false | _ + 1, [] => true | fuel + 1, opener :: rest => let wrap := match rest.getLast? with | some closer => closesMatch opener closer && balancedUpTo fuel rest.dropLast | none => false let splits := (List.range rest.length).any fun k => balancedUpTo fuel ((opener :: rest).take (k + 1)) && balancedUpTo fuel ((opener :: rest).drop (k + 1)) wrap || splits /-- Balance check on `l` with fuel one more than its length, which bounds every derivation of `l`. -/ def balancedList (l : List Char) : Bool := balancedUpTo (l.length + 1) l /-- Executable checker for `isValidParentheses_spec`: `result` must agree with the grammar-directed balance check. -/ def isValidParentheses_check (input : Input) (result : Output) : Bool := decide (result = true ↔ balancedList input.toList = true) theorem vp_sound (fuel : Nat) (l : List Char) : balancedUpTo fuel l = true → Balanced l := by induction fuel generalizing l with | zero => simp [balancedUpTo] | succ fuel ih => cases l with | nil => intro _; exact Balanced.nil | cons opener rest => intro h rw [balancedUpTo] at h simp only [Bool.or_eq_true] at h rcases h with hwrap | hsplits · cases hlast : rest.getLast? with | none => simp [hlast] at hwrap | some closer => simp only [hlast, Bool.and_eq_true] at hwrap obtain ⟨ys, rfl⟩ := List.getLast?_eq_some_iff.mp hlast rw [List.dropLast_concat] at hwrap have hb := ih ys hwrap.2 have hm := hwrap.1 simp only [closesMatch, Bool.or_eq_true, Bool.and_eq_true, beq_iff_eq] at hm rcases hm with (⟨rfl, rfl⟩ | ⟨rfl, rfl⟩) | ⟨rfl, rfl⟩ · exact Balanced.parens hb · exact Balanced.brackets hb · exact Balanced.braces hb · simp only [List.any_eq_true, Bool.and_eq_true] at hsplits obtain ⟨k, _, hleft, hright⟩ := hsplits rw [← List.take_append_drop (k + 1) (opener :: rest)] exact Balanced.append (ih _ hleft) (ih _ hright) theorem vp_complete {l : List Char} (h : Balanced l) : ∀ fuel : Nat, l.length < fuel → balancedUpTo fuel l = true := by induction h with | nil => intro fuel hfuel cases fuel with | zero => omega | succ fuel => simp [balancedUpTo] | @append l₁ l₂ h₁ h₂ ih₁ ih₂ => intro fuel hfuel cases l₁ with | nil => simpa using ih₂ fuel (by simpa using hfuel) | cons a as => cases l₂ with | nil => simpa using ih₁ fuel (by simpa using hfuel) | cons b bs => cases fuel with | zero => omega | succ fuel => have hleft : balancedUpTo fuel (a :: as) = true := ih₁ fuel (by simp only [List.length_cons, List.length_append] at hfuel ⊢; omega) have hright : balancedUpTo fuel (b :: bs) = true := ih₂ fuel (by simp only [List.length_cons, List.length_append] at hfuel ⊢; omega) simp only [List.cons_append, balancedUpTo, Bool.or_eq_true] right apply List.any_eq_true.mpr refine ⟨as.length, by simp, ?_⟩ rw [List.take_succ_cons, List.drop_succ_cons, List.take_left, List.drop_left, Bool.and_eq_true] exact ⟨hleft, hright⟩ | parens h ih => intro fuel hfuel cases fuel with | zero => omega | succ fuel => have hrec := ih fuel (by simp only [List.length_cons, List.length_append] at hfuel; omega) simp [balancedUpTo, closesMatch, hrec] | brackets h ih => intro fuel hfuel cases fuel with | zero => omega | succ fuel => have hrec := ih fuel (by simp only [List.length_cons, List.length_append] at hfuel; omega) simp [balancedUpTo, closesMatch, hrec] | braces h ih => intro fuel hfuel cases fuel with | zero => omega | succ fuel => have hrec := ih fuel (by simp only [List.length_cons, List.length_append] at hfuel; omega) simp [balancedUpTo, closesMatch, hrec] /-- On valid input the checker accepts exactly the specified outputs. -/ theorem isValidParentheses_check_iff_spec (input : Input) (result : Output) (h : isValidInput input) : isValidParentheses_check input result ↔ isValidParentheses_spec input result := by unfold isValidParentheses_check isValidParentheses_spec IsBalanced rw [decide_eq_true_iff] exact iff_congr Iff.rfl ⟨vp_sound _ _, fun hb => vp_complete hb _ (Nat.lt_succ_self _)⟩ /-! ### Implementation helpers -/ /-- Stack scan over the remaining input: openers are pushed, closers must match the stack top, and the end of input requires an empty stack. -/ def scan : List Char → List Char → Bool | [], [] => true | [], _ :: _ => false | c :: rest, stack => if c = '(' || c = '[' || c = '{' then scan rest (c :: stack) else match stack with | [] => false | top :: stack' => closesMatch top c && scan rest stack' /-! ### Main algorithm (impl) -/ /-- Validity by a single left-to-right stack scan over the characters of `input`. -/ def isValid (input : Input) : Output := scan input.toList [] /-! ### Correctness -/ /-- On valid input the algorithm meets the specification. -/ theorem isValid_correct (input : Input) (h : isValidInput input) : isValidParentheses_spec input (isValid input) := by sorry /-! ## Unit tests -/ /-! ### L1 — Validity guard (V accepts the provided examples) -/ #guard isValidInput "()" #guard isValidInput "()[]{}" #guard isValidInput "(]" /-! ### L1b — Negative validity (V rejects invalid input) -/ #guard !(isValidInput "") #guard !(isValidInput "a") #guard !(isValidInput " ") /-! ### L2 — Specification guard (P_check accepts the correct output) -/ #guard isValidParentheses_check "()" true #guard isValidParentheses_check "()[]{}" true #guard isValidParentheses_check "(]" false /-! ### L2b — Negative specification (P_check rejects a wrong output) -/ #guard !(isValidParentheses_check "()" false) #guard !(isValidParentheses_check "()[]{}" false) #guard !(isValidParentheses_check "(]" true) /-! ### L3 — Algorithm output (impl matches the expected output) -/ #guard isValid "()" == true #guard isValid "()[]{}" == true #guard isValid "(]" == false /-! ### L4 — Integration (P_check certifies the output of impl) -/ #guard isValidParentheses_check "()" (isValid "()") #guard isValidParentheses_check "()[]{}" (isValid "()[]{}") #guard isValidParentheses_check "(]" (isValid "(]") end PValidParentheses