🦀 Functional Rust

174: Arithmetic Expression Evaluator

Difficulty: 3 Level: Advanced Evaluate `3 + 4 * (2 - 1)` directly during parsing — no AST, no intermediate representation, just a number.

The Problem This Solves

Example 168 built a Pratt parser that produces an AST. Sometimes you don't need the tree — you just want the answer. A calculator, a config file with computed values, a constraint checker: they all want `eval(parse("3 + 4 * 2"))` to return `11.0`. Classic recursive descent handles this elegantly with grammar-level precedence: each precedence level is a separate function. `parse_additive` calls `parse_multiplicative` to get operands, which calls `parse_unary`, which calls `parse_primary`. The call stack is the precedence structure. No binding power tables needed. This approach also makes it easy to add error handling: detect division by zero, check for incomplete expressions, and return `Result<f64, String>` from every parser function. Compare this with the Pratt approach from 168-169 to see two valid paths to the same destination.

The Intuition

Each grammar level handles one class of operators. Higher functions call lower functions to get their operands, which naturally enforces precedence: `parse_additive` gets its operands from `parse_multiplicative`, so multiplication always binds tighter. 
"3 + 4 * 2"
parse_additive →
lhs = parse_multiplicative("3 + 4 * 2") → 3.0 (stops at '+')
op = '+'
rhs = parse_multiplicative("4 * 2") → 8.0 (handles '*' internally)
result = 3.0 + 8.0 = 11.0

How It Works in Rust

// Entry point — handles + and -
fn parse_additive(input: &str) -> ParseResult<f64> {
 let (mut lhs, mut remaining) = parse_multiplicative(input)?;
 loop {
     let rest = remaining.trim_start();
     if rest.starts_with('+') {
         let (rhs, rest) = parse_multiplicative(&rest[1..])?;
         lhs += rhs;
         remaining = rest;
     } else if rest.starts_with('-') {
         let (rhs, rest) = parse_multiplicative(&rest[1..])?;
         lhs -= rhs;
         remaining = rest;
     } else {
         break;
     }
 }
 Ok((lhs, remaining))
}

// Handles * and /
fn parse_multiplicative(input: &str) -> ParseResult<f64> {
 let (mut lhs, mut remaining) = parse_unary(input)?;
 loop {
     let rest = remaining.trim_start();
     if rest.starts_with('*') {
         let (rhs, rest) = parse_unary(&rest[1..])?;
         lhs *= rhs;
         remaining = rest;
     } else if rest.starts_with('/') {
         let (rhs, rest) = parse_unary(&rest[1..])?;
         if rhs == 0.0 {
             return Err("division by zero".to_string());
         }
         lhs /= rhs;
         remaining = rest;
     } else {
         break;
     }
 }
 Ok((lhs, remaining))
}

// Handles unary minus
fn parse_unary(input: &str) -> ParseResult<f64> {
 let input = input.trim_start();
 if input.starts_with('-') {
     let (val, rest) = parse_unary(&input[1..])?;  // recursive: --- x works
     Ok((-val, rest))
 } else {
     parse_primary(input)
 }
}

// Handles numbers and parenthesized expressions
fn parse_primary(input: &str) -> ParseResult<f64> {
 let input = input.trim_start();
 if input.starts_with('(') {
     let (val, rest) = parse_additive(&input[1..])?;
     let rest = rest.trim_start()
         .strip_prefix(')')
         .ok_or("expected ')'")?;
     Ok((val, rest))
 } else {
     parse_number(input)
 }
}

What This Unlocks

Key Differences

ConceptOCamlRust
Mutual recursion`let rec eval_expr () = ... and eval_additive () = ...`Separate named functions — no `rec` annotation needed
Left-associative loopTail-recursive helper `loop lhs rest``loop` + `break`
Float operators`+.` `-.` `.` `/.` (distinct from int ops)`+` `-` `` `/` (same operators for all numeric types)
Error value`Error "division by zero"``Err("division by zero".to_string())`
// Example 174: Arithmetic Expression Evaluator
// Full arithmetic evaluator: +,-,*,/ with precedence, parens, unary minus

type ParseResult<'a, T> = Result<(T, &'a str), String>;

// ============================================================
// Approach 1: Recursive descent evaluator
// ============================================================

fn parse_number(input: &str) -> ParseResult<f64> {
    let s = input.trim_start();
    let bytes = s.as_bytes();
    let mut pos = 0;
    while pos < bytes.len() && (bytes[pos].is_ascii_digit() || bytes[pos] == b'.') {
        pos += 1;
    }
    if pos == 0 {
        return Err("Expected number".to_string());
    }
    let n: f64 = s[..pos].parse().map_err(|e: std::num::ParseFloatError| e.to_string())?;
    Ok((n, &s[pos..]))
}

fn eval_expr(input: &str) -> ParseResult<f64> {
    eval_additive(input)
}

fn eval_additive(input: &str) -> ParseResult<f64> {
    let (mut lhs, mut rest) = eval_multiplicative(input)?;
    loop {
        let s = rest.trim_start();
        if s.starts_with('+') {
            let (rhs, r) = eval_multiplicative(&s[1..])?;
            lhs += rhs;
            rest = r;
        } else if s.starts_with('-') {
            let (rhs, r) = eval_multiplicative(&s[1..])?;
            lhs -= rhs;
            rest = r;
        } else {
            break;
        }
    }
    Ok((lhs, rest))
}

fn eval_multiplicative(input: &str) -> ParseResult<f64> {
    let (mut lhs, mut rest) = eval_unary(input)?;
    loop {
        let s = rest.trim_start();
        if s.starts_with('*') {
            let (rhs, r) = eval_unary(&s[1..])?;
            lhs *= rhs;
            rest = r;
        } else if s.starts_with('/') {
            let (rhs, r) = eval_unary(&s[1..])?;
            if rhs == 0.0 {
                return Err("Division by zero".to_string());
            }
            lhs /= rhs;
            rest = r;
        } else {
            break;
        }
    }
    Ok((lhs, rest))
}

fn eval_unary(input: &str) -> ParseResult<f64> {
    let s = input.trim_start();
    if s.starts_with('-') {
        let (val, rest) = eval_unary(&s[1..])?;
        Ok((-val, rest))
    } else {
        eval_primary(s)
    }
}

fn eval_primary(input: &str) -> ParseResult<f64> {
    let s = input.trim_start();
    if s.starts_with('(') {
        let (val, rest) = eval_expr(&s[1..])?;
        let rest = rest.trim_start();
        if rest.starts_with(')') {
            Ok((val, &rest[1..]))
        } else {
            Err("Expected ')'".to_string())
        }
    } else {
        parse_number(s)
    }
}

// ============================================================
// Approach 2: Evaluate string completely
// ============================================================

fn evaluate(expr: &str) -> Result<f64, String> {
    let (val, rest) = eval_expr(expr)?;
    if rest.trim().is_empty() {
        Ok(val)
    } else {
        Err(format!("Unexpected trailing: \"{}\"", rest.trim()))
    }
}

// ============================================================
// Approach 3: With built-in functions
// ============================================================

fn eval_function(name: &str, arg: f64) -> Result<f64, String> {
    match name {
        "sqrt" => Ok(arg.sqrt()),
        "abs" => Ok(arg.abs()),
        "sin" => Ok(arg.sin()),
        "cos" => Ok(arg.cos()),
        "ln" => Ok(arg.ln()),
        _ => Err(format!("Unknown function: {}", name)),
    }
}

fn main() {
    let expressions = vec![
        "2 + 3", "2 + 3 * 4", "(2 + 3) * 4", "10 / 2 - 3",
        "-5", "-(2 + 3)", "2 * -3", "1.5 + 2.5",
    ];
    for expr in expressions {
        match evaluate(expr) {
            Ok(val) => println!("{} = {}", expr, val),
            Err(e) => println!("{} → Error: {}", expr, e),
        }
    }

    // Function examples
    println!("\nsqrt(16) = {:?}", eval_function("sqrt", 16.0));
    println!("abs(-5) = {:?}", eval_function("abs", -5.0));

    println!("\n✓ All examples completed");
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_addition() {
        assert_eq!(evaluate("2 + 3"), Ok(5.0));
    }

    #[test]
    fn test_precedence() {
        assert_eq!(evaluate("2 + 3 * 4"), Ok(14.0));
    }

    #[test]
    fn test_parens() {
        assert_eq!(evaluate("(2 + 3) * 4"), Ok(20.0));
    }

    #[test]
    fn test_subtraction_division() {
        assert_eq!(evaluate("10 / 2 - 3"), Ok(2.0));
    }

    #[test]
    fn test_unary_minus() {
        assert_eq!(evaluate("-5"), Ok(-5.0));
    }

    #[test]
    fn test_unary_in_parens() {
        assert_eq!(evaluate("-(2 + 3)"), Ok(-5.0));
    }

    #[test]
    fn test_multiply_negative() {
        assert_eq!(evaluate("2 * -3"), Ok(-6.0));
    }

    #[test]
    fn test_float() {
        assert_eq!(evaluate("1.5 + 2.5"), Ok(4.0));
    }

    #[test]
    fn test_division_by_zero() {
        assert!(evaluate("1 / 0").is_err());
    }

    #[test]
    fn test_incomplete_expr() {
        assert!(evaluate("2 +").is_err());
    }

    #[test]
    fn test_complex() {
        let val = evaluate("(1 + 2) * (3 + 4) / 7").unwrap();
        assert!((val - 3.0).abs() < 1e-10);
    }

    #[test]
    fn test_functions() {
        assert!((eval_function("sqrt", 16.0).unwrap() - 4.0).abs() < 1e-10);
        assert_eq!(eval_function("abs", -5.0), Ok(5.0));
    }
}

(* Example 174: Arithmetic Expression Evaluator *)
(* Full arithmetic evaluator: +,-,*,/ with precedence, parens, unary minus *)

type 'a parse_result = ('a * string, string) result
type 'a parser = string -> 'a parse_result

let ws0 input =
  let rec skip i = if i < String.length input &&
    (input.[i] = ' ' || input.[i] = '\t') then skip (i+1) else i in
  let i = skip 0 in String.sub input i (String.length input - i)

(* Approach 1: Recursive descent evaluator *)
let parse_number input =
  let s = ws0 input in
  let len = String.length s in
  let pos = ref 0 in
  while !pos < len && (s.[!pos] >= '0' && s.[!pos] <= '9' || s.[!pos] = '.') do incr pos done;
  if !pos = 0 then Error "Expected number"
  else Ok (float_of_string (String.sub s 0 !pos), String.sub s !pos (len - !pos))

let rec eval_expr input = eval_additive input

and eval_additive input =
  match eval_multiplicative input with
  | Error e -> Error e
  | Ok (lhs, rest) -> eval_additive_loop lhs rest

and eval_additive_loop lhs input =
  let s = ws0 input in
  if String.length s > 0 && s.[0] = '+' then
    match eval_multiplicative (String.sub s 1 (String.length s - 1)) with
    | Ok (rhs, rest) -> eval_additive_loop (lhs +. rhs) rest
    | Error e -> Error e
  else if String.length s > 0 && s.[0] = '-' then
    match eval_multiplicative (String.sub s 1 (String.length s - 1)) with
    | Ok (rhs, rest) -> eval_additive_loop (lhs -. rhs) rest
    | Error e -> Error e
  else Ok (lhs, s)

and eval_multiplicative input =
  match eval_unary input with
  | Error e -> Error e
  | Ok (lhs, rest) -> eval_multiplicative_loop lhs rest

and eval_multiplicative_loop lhs input =
  let s = ws0 input in
  if String.length s > 0 && s.[0] = '*' then
    match eval_unary (String.sub s 1 (String.length s - 1)) with
    | Ok (rhs, rest) -> eval_multiplicative_loop (lhs *. rhs) rest
    | Error e -> Error e
  else if String.length s > 0 && s.[0] = '/' then
    match eval_unary (String.sub s 1 (String.length s - 1)) with
    | Ok (rhs, rest) ->
      if rhs = 0.0 then Error "Division by zero"
      else eval_multiplicative_loop (lhs /. rhs) rest
    | Error e -> Error e
  else Ok (lhs, s)

and eval_unary input =
  let s = ws0 input in
  if String.length s > 0 && s.[0] = '-' then
    match eval_unary (String.sub s 1 (String.length s - 1)) with
    | Ok (v, rest) -> Ok (-. v, rest)
    | Error e -> Error e
  else eval_primary s

and eval_primary input =
  let s = ws0 input in
  if String.length s > 0 && s.[0] = '(' then
    match eval_expr (String.sub s 1 (String.length s - 1)) with
    | Ok (v, rest) ->
      let r = ws0 rest in
      if String.length r > 0 && r.[0] = ')' then
        Ok (v, String.sub r 1 (String.length r - 1))
      else Error "Expected ')'"
    | Error e -> Error e
  else parse_number s

(* Approach 2: Evaluate string directly *)
let evaluate (expr : string) : (float, string) result =
  match eval_expr expr with
  | Ok (v, rest) ->
    if String.length (ws0 rest) = 0 then Ok v
    else Error (Printf.sprintf "Unexpected trailing: \"%s\"" rest)
  | Error e -> Error e

(* Approach 3: With function support *)
let eval_function name arg =
  match name with
  | "sqrt" -> Ok (sqrt arg)
  | "abs" -> Ok (abs_float arg)
  | "sin" -> Ok (sin arg)
  | "cos" -> Ok (cos arg)
  | _ -> Error (Printf.sprintf "Unknown function: %s" name)

(* Tests *)
let () =
  assert (evaluate "2 + 3" = Ok 5.0);
  assert (evaluate "2 + 3 * 4" = Ok 14.0);
  assert (evaluate "(2 + 3) * 4" = Ok 20.0);
  assert (evaluate "10 / 2 - 3" = Ok 2.0);
  assert (evaluate "-5" = Ok (-5.0));
  assert (evaluate "-(2 + 3)" = Ok (-5.0));
  assert (evaluate "2 * -3" = Ok (-6.0));
  assert (evaluate "1.5 + 2.5" = Ok 4.0);
  assert (Result.is_error (evaluate "1 / 0"));
  assert (Result.is_error (evaluate "2 +"));

  print_endline "✓ All tests passed"

📊 Detailed Comparison

Comparison: Example 174 — Arithmetic Evaluator

Additive level

OCaml:

🐪 Show OCaml equivalent
and eval_additive input =
match eval_multiplicative input with
| Error e -> Error e
| Ok (lhs, rest) -> eval_additive_loop lhs rest

and eval_additive_loop lhs input =
let s = ws0 input in
if String.length s > 0 && s.[0] = '+' then
 match eval_multiplicative (String.sub s 1 ...) with
 | Ok (rhs, rest) -> eval_additive_loop (lhs +. rhs) rest
else Ok (lhs, s)

Rust: 

fn eval_additive(input: &str) -> ParseResult<f64> {
 let (mut lhs, mut rest) = eval_multiplicative(input)?;
 loop {
     let s = rest.trim_start();
     if s.starts_with('+') {
         let (rhs, r) = eval_multiplicative(&s[1..])?;
         lhs += rhs; rest = r;
     } else if s.starts_with('-') {
         let (rhs, r) = eval_multiplicative(&s[1..])?;
         lhs -= rhs; rest = r;
     } else { break; }
 }
 Ok((lhs, rest))
}

evaluate wrapper

OCaml:

🐪 Show OCaml equivalent
let evaluate expr =
match eval_expr expr with
| Ok (v, rest) ->
 if String.length (ws0 rest) = 0 then Ok v
 else Error (Printf.sprintf "Unexpected trailing: \"%s\"" rest)

Rust: 

fn evaluate(expr: &str) -> Result<f64, String> {
 let (val, rest) = eval_expr(expr)?;
 if rest.trim().is_empty() { Ok(val) }
 else { Err(format!("Unexpected trailing: \"{}\"", rest.trim())) }
}

Related Examples

#173 173: Lisp / S-expression Parser 🌱 #175 175: Complete JSON Parser 🌱 #172 172: INI File Parser 🌱 #176 176: Introduction to GADTs 🌱
All Examples