174 Advanced

Arithmetic Expression Evaluator

Functional Programming

Tutorial

The Problem

An arithmetic evaluator combines parsing and immediate evaluation: it reads an expression like (3 + 4) * 2 - 1 and produces 13.0 without constructing an AST. This is the classic recursive descent evaluator, foundational to expression evaluation in spreadsheets, calculator apps, scripting engines, and configuration processors. Understanding it requires grasping how grammar levels correspond to function call levels.

🎯 Learning Outcomes

• Implement a complete recursive descent arithmetic evaluator with correct precedence

• Understand how grammar rules map to mutually recursive functions: expr, term, factor, number

• See how parentheses are handled naturally by recursion (factor calls expr)

• Appreciate why parsing-and-evaluating together is simpler than building an AST first

Code Example

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))
}

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)

Key Differences

Input threading: Rust threads &str slices through functions explicitly; OCaml can use a ref for the input position (imperative style) or tuples (functional style).

Float arithmetic: Both use floating-point (f64/float) by default; integer arithmetic requires more careful parsing of the grammar.

Error handling: Rust propagates Result; OCaml typically raises exceptions for malformed input in simple evaluators.

AST vs. direct evaluation: Both examples evaluate directly; building an AST (examples 168-169) separates the concerns.

OCaml Approach

OCaml's recursive descent evaluator is structurally identical:

let rec expr () = ...
and term () = ...
and factor () = ...

let rec ... and ... provides mutual recursion naturally. OCaml's reference-based input scanning (let input_ref = ref s) or functional threading (let (v, rest) = expr s) mirrors the Rust approach. The evaluator is a classic exercise in OCaml courses.

Full Source

#![allow(clippy::all)]
// 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)),
    }
}

#[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"

✓ Tests Rust test suite

#[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));
    }
}

Deep Comparison

Comparison: Example 174 — Arithmetic Evaluator

Additive level

OCaml:

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:

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())) }
}

Exercises

Add the modulo operator % between term and factor precedence levels.

Support named constants: pi → 3.14159..., e → 2.71828... in the factor rule.

Add function calls: sin(x), cos(x), sqrt(x) as valid factor expressions.

Open Source Repos

functional-rust

View the source for this example on GitHub — OCaml and Rust side by side in the repo.

Rust