import Mathlib /-! # Evaluate Reverse Polish Notation You are given an array of strings tokens that represents an arithmetic expression in a Reverse Polish Notation. Evaluate the expression. Return an integer that represents the value of the expression. Note that: The valid operators are '+', '-', '*', and '/'. Each operand may be an integer or another expression. The division between two integers always truncates toward zero. There will not be any division by zero. The input represents a valid arithmetic expression in a reverse polish notation. The answer and all the intermediate calculations can be represented in a 32-bit integer. ## Constraints - 1 <= tokens.length <= 10^4 - tokens[i] is either an operator: "+", "-", "*", or "/", or an integer in the range [-200, 200]. ## Provided examples - `tokens = ["2", "1", "+", "3", "*"]` → `9` - `tokens = ["4", "13", "5", "/", "+"]` → `6` - `tokens = ["10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"]` → `22` ## Synthesized negative examples - invalid input: `tokens = []` ([structural] a predicate that admits 1 <= tokens.length <= 10^4. empty where at least one token is required) - invalid input: `tokens = ["201", "1", "+"]` ([structural] a predicate that admits tokens[i] is either an operator: "+", "-", "*", or "/", or an integer in the range [-200, 200].. one above the allowed integer maximum) - invalid input: `tokens = ["1.5", "1", "+"]` ([structural] a predicate that admits tokens[i] is either an operator: "+", "-", "*", or "/", or an integer in the range [-200, 200].. numeric-looking but not an integer) - `tokens = ["2", "1", "+", "3", "*"]` → `5` is wrong ([structural] specification omits the RPN order requirement, allowing standard precedence. 2 + 1 * 3 = 5 under ordinary precedence) - `tokens = ["4", "13", "5", "/", "+"]` → `7` is wrong ([structural] division truncation toward zero omitted. 13/5 rounded to 3, giving 7) - `tokens = ["10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"]` → `12` is wrong ([structural] division truncates toward negative infinity instead of toward zero. floor division at '/' gives 12) -/ namespace PEvaluateReversePolishNotation abbrev Input := List String abbrev Output := Int /-! ### Specification helpers -/ /-- `n` provided it fits in a signed 32-bit integer, else `none`. -/ def guard32 (n : Int) : Option Int := if -2147483648 ≤ n && n ≤ 2147483647 then some n else none /-- The operation an operator token denotes on the two preceding values, `none` on division by zero or overflow. -/ def arithOp (op : String) (a b : Int) : Option Int := match op with | "+" => guard32 (a + b) | "-" => guard32 (a - b) | "*" => guard32 (a * b) | "/" => if b == 0 then none else guard32 (a.tdiv b) | _ => none /-- Applies an operator token to the top two stack values, `none` on underflow, division by zero, or overflow. -/ def stepOp (op : String) (stack : List Int) : Option (List Int) := match stack with | b :: a :: rest => match arithOp op a b with | some v => some (v :: rest) | none => none | _ => none /-- Folds the tokens over a value stack, `none` on malformed tokens, underflow, division by zero, or overflow. -/ def evalStack (stack : List Int) (tokens : List String) : Option (List Int) := match tokens with | [] => some stack | t :: ts => match t with | "+" | "-" | "*" | "/" => match stepOp t stack with | some s' => evalStack s' ts | none => none | _ => match t.toInt? with | some n => evalStack (n :: stack) ts | none => none termination_by tokens /-- The value a token list denotes as one complete RPN expression, `none` when it is not exactly one. -/ def evalTokens (tokens : List String) : Option Int := match evalStack [] tokens with | some [v] => some v | _ => none /-- A token is one of the four operators or a decimal integer in [-200, 200]. -/ def isValidToken (t : String) : Bool := t = "+" || t = "-" || t = "*" || t = "/" || match t.toInt? with | some n => -200 ≤ n && n ≤ 200 | none => false /-- Denotation of an RPN token list: numbers denote their values, operators the operation on the two preceding subexpressions, division truncating toward zero. -/ inductive RPNValue : List String → Int → Prop where | number {s : String} {n : Int} (h : s.toInt? = some n) : RPNValue [s] n | add {t₁ t₂ : List String} {a b : Int} (h₁ : RPNValue t₁ a) (h₂ : RPNValue t₂ b) : RPNValue (t₁ ++ t₂ ++ ["+"]) (a + b) | sub {t₁ t₂ : List String} {a b : Int} (h₁ : RPNValue t₁ a) (h₂ : RPNValue t₂ b) : RPNValue (t₁ ++ t₂ ++ ["-"]) (a - b) | mul {t₁ t₂ : List String} {a b : Int} (h₁ : RPNValue t₁ a) (h₂ : RPNValue t₂ b) : RPNValue (t₁ ++ t₂ ++ ["*"]) (a * b) | div {t₁ t₂ : List String} {a b : Int} (h₁ : RPNValue t₁ a) (h₂ : RPNValue t₂ b) (hb : b ≠ 0) : RPNValue (t₁ ++ t₂ ++ ["/"]) (a.tdiv b) /-! ### Validity predicate (V) -/ /-- Valid input: 1 to 10^4 admissible tokens forming one complete RPN expression with no division by zero and every value 32-bit. -/ def isValidInput (input : Input) : Bool := 1 ≤ input.length && input.length ≤ 10000 && input.all isValidToken && (evalTokens input).isSome /-! ### Ideal specification (P_spec) -/ /-- `result` is the integer the RPN expression `input` denotes, and no other integer is denoted by it. -/ def evalRPN_spec (input : Input) (result : Output) : Prop := RPNValue input result ∧ ∀ v : Int, RPNValue input v → v = result /-! ### Decidable specification (P_check) -/ /-- Executable checker for `evalRPN_spec`: the stack evaluator's unique denoted value is `result`. -/ def evalRPN_check (input : Input) (result : Output) : Bool := decide (evalTokens input = some result) /-- A string that starts with no minus sign and is not a numeral denotes no integer. -/ theorem toInt_none_of_notNat (s : String) (h1 : s.startsWith '-' = false) (h2 : s.isNat = false) : s.toInt? = none := by rw [String.toInt?_eq_toNat?_of_startsWith_eq_false h1, String.toNat?_eq_none h2] rfl /-- The four operator tokens denote no integer. -/ theorem toInt_ne_ops {s : String} {n : Int} (h : s.toInt? = some n) : (s = "+" → False) ∧ (s = "-" → False) ∧ (s = "*" → False) ∧ (s = "/" → False) := by have hplus : String.toInt? "+" = none := toInt_none_of_notNat "+" (by decide +kernel) (by simp only [← Bool.not_eq_true, String.isNat_iff]; simp) have hmul : String.toInt? "*" = none := toInt_none_of_notNat "*" (by decide +kernel) (by simp only [← Bool.not_eq_true, String.isNat_iff]; simp) have hdiv : String.toInt? "/" = none := toInt_none_of_notNat "/" (by decide +kernel) (by simp only [← Bool.not_eq_true, String.isNat_iff]; simp) have hsub : String.toInt? "-" = none := by simp only [String.toInt?_eq_none_iff, ← Bool.not_eq_true, String.isInt_iff, String.isNat_iff] simp intro x hx hne exfalso have hh := congrArg String.toList hx simp at hh exact hne (by simpa using hh.symm) refine ⟨?_, ?_, ?_, ?_⟩ <;> intro he <;> subst he <;> simp_all /-- `stk` is the value stack (top first) produced by the token list `ts`. -/ def RPNStackOf : List Int → List String → Prop | [], ts => ts = [] | v :: stk, ts => ∃ t₁ t₂, ts = t₁ ++ t₂ ∧ RPNStackOf stk t₁ ∧ RPNValue t₂ v /-- Applying an operator to the top two entries of a witnessed stack keeps it witnessed. -/ theorem RPNStackOf_op {op : String} {a b v : Int} {rest : List Int} {pre : List String} (hs : RPNStackOf (b :: a :: rest) pre) (hmk : ∀ t₁ t₂, RPNValue t₁ a → RPNValue t₂ b → RPNValue (t₁ ++ t₂ ++ [op]) v) : RPNStackOf (v :: rest) (pre ++ [op]) := by simp only [RPNStackOf] at hs ⊢ obtain ⟨t₁, t₂, h1, hst, hb⟩ := hs obtain ⟨u₁, u₂, h2, hst2, ha⟩ := hst refine ⟨u₁, u₂ ++ t₂ ++ [op], ?_, hst2, hmk _ _ ha hb⟩ subst h1; subst h2; simp /-- A successful operator step pops two values and pushes the operator's result. -/ theorem stepOp_some {op : String} {stk s' : List Int} (h : stepOp op stk = some s') : ∃ a b rest w, stk = b :: a :: rest ∧ s' = w :: rest ∧ arithOp op a b = some w := by rcases stk with _ | ⟨b, _ | ⟨a, rest⟩⟩ · simp [stepOp] at h · simp [stepOp] at h · simp only [stepOp] at h cases hw : arithOp op a b with | none => simp only [hw] at h; simp at h | some w => simp only [hw, Option.some.injEq] at h exact ⟨a, b, rest, w, rfl, h.symm, hw⟩ theorem arithOp_add_value {a b w : Int} (hw : arithOp "+" a b = some w) : w = a + b := by simp only [arithOp, guard32] at hw split_ifs at hw <;> simp_all theorem arithOp_sub_value {a b w : Int} (hw : arithOp "-" a b = some w) : w = a - b := by simp only [arithOp, guard32] at hw split_ifs at hw <;> simp_all theorem arithOp_mul_value {a b w : Int} (hw : arithOp "*" a b = some w) : w = a * b := by simp only [arithOp, guard32] at hw split_ifs at hw <;> simp_all theorem arithOp_div_value {a b w : Int} (hw : arithOp "/" a b = some w) : w = a.tdiv b ∧ b ≠ 0 := by simp only [arithOp, guard32] at hw split_ifs at hw with h1 h2 <;> simp_all /-- One operator token consumes the two values below it and leaves the evaluator's tail run. -/ theorem op_step_agree {op : String} {a b v : Int} {stk : List Int} {ts : List String} {r : List Int} (hunf : evalStack (b :: a :: stk) (op :: ts) = (match stepOp op (b :: a :: stk) with | some s' => evalStack s' ts | none => none)) (hop : ∀ w : Int, arithOp op a b = some w → w = v) (hev : evalStack (b :: a :: stk) (op :: ts) = some r) : evalStack (v :: stk) ts = some r := by rw [hunf] at hev simp only [stepOp] at hev cases hw : arithOp op a b with | none => simp only [hw] at hev; simp at hev | some w => simp only [hw] at hev rw [← hop w hw] exact hev /-- Soundness of the stack evaluator against the denotation relation. -/ theorem evalStack_sound (tokens : List String) : ∀ (stk : List Int) (pre : List String) (out : List Int), RPNStackOf stk pre → evalStack stk tokens = some out → RPNStackOf out (pre ++ tokens) := by induction tokens with | nil => intro stk pre out hpre hev rw [evalStack.eq_1] at hev simp only [Option.some.injEq] at hev subst hev simpa using hpre | cons t ts ih => intro stk pre out hpre hev have hcat : pre ++ (t :: ts) = (pre ++ [t]) ++ ts := by simp rw [hcat] by_cases h1 : t = "+" · subst h1 rw [evalStack.eq_2] at hev cases hstep : stepOp "+" stk with | none => simp only [hstep] at hev; simp at hev | some s' => simp only [hstep] at hev obtain ⟨a, b, rest, w, rfl, rfl, hw⟩ := stepOp_some hstep have hv : w = a + b := arithOp_add_value hw subst hv exact ih _ _ _ (RPNStackOf_op hpre (fun _ _ ha hb => RPNValue.add ha hb)) hev · by_cases h2 : t = "-" · subst h2 rw [evalStack.eq_3] at hev cases hstep : stepOp "-" stk with | none => simp only [hstep] at hev; simp at hev | some s' => simp only [hstep] at hev obtain ⟨a, b, rest, w, rfl, rfl, hw⟩ := stepOp_some hstep have hv : w = a - b := arithOp_sub_value hw subst hv exact ih _ _ _ (RPNStackOf_op hpre (fun _ _ ha hb => RPNValue.sub ha hb)) hev · by_cases h3 : t = "*" · subst h3 rw [evalStack.eq_4] at hev cases hstep : stepOp "*" stk with | none => simp only [hstep] at hev; simp at hev | some s' => simp only [hstep] at hev obtain ⟨a, b, rest, w, rfl, rfl, hw⟩ := stepOp_some hstep have hv : w = a * b := arithOp_mul_value hw subst hv exact ih _ _ _ (RPNStackOf_op hpre (fun _ _ ha hb => RPNValue.mul ha hb)) hev · by_cases h4 : t = "/" · subst h4 rw [evalStack.eq_5] at hev cases hstep : stepOp "/" stk with | none => simp only [hstep] at hev; simp at hev | some s' => simp only [hstep] at hev obtain ⟨a, b, rest, w, rfl, rfl, hw⟩ := stepOp_some hstep obtain ⟨hv, hb0⟩ := arithOp_div_value hw subst hv exact ih _ _ _ (RPNStackOf_op hpre (fun _ _ ha hb => RPNValue.div ha hb hb0)) hev · rw [evalStack.eq_6 stk t ts h1 h2 h3 h4] at hev cases hn : t.toInt? with | none => simp only [hn] at hev; simp at hev | some n => simp only [hn] at hev refine ih (n :: stk) (pre ++ [t]) out ?_ hev simp only [RPNStackOf] exact ⟨pre, [t], rfl, hpre, RPNValue.number hn⟩ /-- Any denotation of a prefix that the evaluator can complete is the value the evaluator pushes. -/ theorem rpn_eval_agree {t : List String} {v : Int} (hv : RPNValue t v) : ∀ (stk : List Int) (ts : List String) (r : List Int), evalStack stk (t ++ ts) = some r → evalStack (v :: stk) ts = some r := by induction hv with | @number s n hn => intro stk ts r hev obtain ⟨h1, h2, h3, h4⟩ := toInt_ne_ops hn rw [List.singleton_append, evalStack.eq_6 stk s ts h1 h2 h3 h4] at hev simp only [hn] at hev exact hev | @add t₁ t₂ a b _ _ ih₁ ih₂ => intro stk ts r hev simp only [List.append_assoc, List.singleton_append] at hev exact op_step_agree (evalStack.eq_2 _ _) (fun w hw => arithOp_add_value hw) (ih₂ (a :: stk) ("+" :: ts) r (ih₁ stk (t₂ ++ "+" :: ts) r hev)) | @sub t₁ t₂ a b _ _ ih₁ ih₂ => intro stk ts r hev simp only [List.append_assoc, List.singleton_append] at hev exact op_step_agree (evalStack.eq_3 _ _) (fun w hw => arithOp_sub_value hw) (ih₂ (a :: stk) ("-" :: ts) r (ih₁ stk (t₂ ++ "-" :: ts) r hev)) | @mul t₁ t₂ a b _ _ ih₁ ih₂ => intro stk ts r hev simp only [List.append_assoc, List.singleton_append] at hev exact op_step_agree (evalStack.eq_4 _ _) (fun w hw => arithOp_mul_value hw) (ih₂ (a :: stk) ("*" :: ts) r (ih₁ stk (t₂ ++ "*" :: ts) r hev)) | @div t₁ t₂ a b _ _ _ ih₁ ih₂ => intro stk ts r hev simp only [List.append_assoc, List.singleton_append] at hev exact op_step_agree (evalStack.eq_5 _ _) (fun w hw => (arithOp_div_value hw).1) (ih₂ (a :: stk) ("/" :: ts) r (ih₁ stk (t₂ ++ "/" :: ts) r hev)) /-- `evalTokens` succeeds only when the stack evaluator ends on a singleton. -/ theorem evalStack_of_evalTokens {input : List String} {r : Int} (h : evalTokens input = some r) : evalStack [] input = some [r] := by unfold evalTokens at h split at h <;> simp_all /-- The evaluator's answer is denoted by the token list. -/ theorem evalTokens_sound {input : List String} {r : Int} (h : evalTokens input = some r) : RPNValue input r := by have h1 := evalStack_sound input [] [] [r] (by simp [RPNStackOf]) (evalStack_of_evalTokens h) simp only [List.nil_append, RPNStackOf] at h1 obtain ⟨t₁, t₂, hcat, ht1, hv⟩ := h1 subst ht1 simp only [List.nil_append] at hcat subst hcat exact hv /-- The token list denotes nothing but the evaluator's answer. -/ theorem evalTokens_unique {input : List String} {r v : Int} (h : evalTokens input = some r) (hv : RPNValue input v) : v = r := by have h2 := rpn_eval_agree hv [] [] [r] (by simpa using evalStack_of_evalTokens h) rw [evalStack.eq_1] at h2 simpa using h2 /-- On valid input the checker accepts exactly the specified outputs. -/ theorem evalRPN_check_iff_spec (input : Input) (result : Output) (h : isValidInput input) : evalRPN_check input result ↔ evalRPN_spec input result := by unfold evalRPN_check evalRPN_spec simp only [decide_eq_true_eq] have hs : (evalTokens input).isSome = true := by unfold isValidInput at h simp only [Bool.and_eq_true] at h exact h.2 obtain ⟨r0, hr0⟩ := Option.isSome_iff_exists.mp hs constructor · intro hc exact ⟨evalTokens_sound hc, fun v hv => evalTokens_unique hc hv⟩ · rintro ⟨hv, huniq⟩ have hr : r0 = result := huniq r0 (evalTokens_sound hr0) rw [← hr] exact hr0 /-! ### Main algorithm (impl) -/ /-- Linear stack evaluation of the RPN token list via `evalTokens`, with `0` as the unreachable fallback. -/ def evaluateReversePolishNotation (input : Input) : Output := (evalTokens input).getD 0 /-! ### Correctness -/ /-- On valid input the algorithm meets the specification. -/ theorem evaluateReversePolishNotation_correct (input : Input) (h : isValidInput input) : evalRPN_spec input (evaluateReversePolishNotation input) := by sorry /-! ## Unit tests -/ /-! ### L1 — Validity guard (V accepts the provided examples) -/ #guard isValidInput ["2", "1", "+", "3", "*"] #guard isValidInput ["4", "13", "5", "/", "+"] #guard isValidInput ["10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"] /-! ### L1b — Negative validity (V rejects invalid input) -/ #guard !(isValidInput []) #guard !(isValidInput ["201", "1", "+"]) #guard !(isValidInput ["1.5", "1", "+"]) /-! ### L2 — Specification guard (P_check accepts the correct output) -/ #guard evalRPN_check ["2", "1", "+", "3", "*"] 9 #guard evalRPN_check ["4", "13", "5", "/", "+"] 6 #guard evalRPN_check ["10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"] 22 /-! ### L2b — Negative specification (P_check rejects a wrong output) -/ #guard !(evalRPN_check ["2", "1", "+", "3", "*"] 5) #guard !(evalRPN_check ["4", "13", "5", "/", "+"] 7) #guard !(evalRPN_check ["10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"] 12) /-! ### L3 — Algorithm output (impl matches the expected output) -/ #guard evaluateReversePolishNotation ["2", "1", "+", "3", "*"] == 9 #guard evaluateReversePolishNotation ["4", "13", "5", "/", "+"] == 6 #guard evaluateReversePolishNotation ["10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"] == 22 /-! ### L4 — Integration (P_check certifies the output of impl) -/ #guard evalRPN_check ["2", "1", "+", "3", "*"] (evaluateReversePolishNotation ["2", "1", "+", "3", "*"]) #guard evalRPN_check ["4", "13", "5", "/", "+"] (evaluateReversePolishNotation ["4", "13", "5", "/", "+"]) #guard evalRPN_check ["10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"] (evaluateReversePolishNotation ["10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"]) end PEvaluateReversePolishNotation