Building an Expression Calculator in Rust — Pratt Parsing Turns Precedence into Two Numbers, and Rationals Kill Float Error

expr   → term (('+' | '-') term)*
term   → factor (('*' | '/') factor)*
factor → power ('^' power)*
power  → atom | '(' expr ')'

fn expr(rbp):
  left = nud(token)          // prefix / atom
  while lbp(peek) > rbp:
    left = led(left, next)   // infix: left OP expr(op.rbp)

fn expr(&mut self, rbp: u8) -> Result<Expr, ParseError> {
    let mut left = self.nud()?;             // prefix (number, paren, unary minus)
    while let Some(tok) = self.peek() {
        let (op, lbp, op_rbp) = match infix_bp(tok) {
            Some(x) => x,
            None => break,
        };
        if lbp <= rbp { break; }            // weaker operator → stop
        self.next();                        // consume operator
        let right = self.expr(op_rbp)?;     // right operand, recursively
        left = Expr::Bin(op, Box::new(left), Box::new(right));
    }
    Ok(left)
}

fn infix_bp(t: &Token) -> Option<(BinOp, u8, u8)> {
    match t {
        Token::Plus  => Some((BinOp::Add, 1, 2)),
        Token::Star  => Some((BinOp::Mul, 3, 4)),
        Token::Caret => Some((BinOp::Pow, 7, 6)), // right-assoc
        // ...
    }
}

#[test]
fn pow_is_right_associative() {
    assert_eq!(ev("2^3^2"), "512"); // 2^(3^2), NOT (2^3)^2
}

#[test]
fn ast_shape_for_precedence() {
    let ast = Parser::new(tokenize("1 + 2 * 3").unwrap()).parse().unwrap();
    match ast {
        Expr::Bin(BinOp::Add, _, right) =>
            assert!(matches!(*right, Expr::Bin(BinOp::Mul, _, _))),
        _ => panic!("expected Add at the root"),
    }
}

const PREFIX_RBP: u8 = 5;
// nud (prefix):
Some(Token::Minus) => Ok(Expr::Neg(Box::new(self.expr(PREFIX_RBP)?))),

#[test]
fn unary_minus_binding() {
    assert_eq!(ev("-2^2"), "-4");  // looser than ^
    assert_eq!(ev("-2*3"), "-6");  // tighter than *
    assert_eq!(ev("--5"), "5");    // double negation
}

#[derive(Clone, Copy, PartialEq, Eq)]
pub struct Rational {
    num: i128,
    den: i128, // invariant: den > 0, gcd(|num|, den) == 1
}

impl Rational {
    pub fn new(num: i128, den: i128) -> Result<Self, RErr> {
        if den == 0 { return Err(RErr::DivZero); }
        let sign = if den < 0 { -1 } else { 1 };
        let g = gcd(num, den).max(1);
        Ok(Rational { num: sign * (num / g), den: (den / g).abs() })
    }
}

#[test]
fn exact_arithmetic_no_float_error() {
    let a = Rational::parse_decimal("0.1").unwrap();
    let b = Rational::parse_decimal("0.2").unwrap();
    assert_eq!(a.add(b).unwrap(), Rational::new(3, 10).unwrap());
}

pub fn mul(self, o: Rational) -> Result<Rational, RErr> {
    let num = self.num.checked_mul(o.num).ok_or(RErr::Overflow)?;
    let den = self.den.checked_mul(o.den).ok_or(RErr::Overflow)?;
    Rational::new(num, den)
}

#[test]
fn overflow_guarded() {
    assert_eq!(
        Rational::from_int(i128::MAX).mul(Rational::from_int(2)),
        Err(RErr::Overflow)); // no wrapping to a wrong answer
}

while rem != 0 && digits.len() < max_digits {
    if let Some(&(_, pos)) = seen.iter().find(|(r, _)| *r == rem) {
        repeat_at = Some(pos); break;
    }
    seen.push((rem, digits.len()));
    rem *= 10;
    digits.push(char::from(b'0' + (rem / den) as u8));
    rem %= den;
}

$ pcalc --decimal "1/7"
1/7  = 0.(142857) (repeating)
$ pcalc --decimal "1/6"
1/6  = 0.1(6) (repeating)

src/lexer.rs    — tokenizer
src/parser.rs   — Pratt parser → AST → eval
src/rational.rs — i128 rational arithmetic
src/main.rs     — clap CLI (arg or stdin REPL)

cargo run -- "1/3 + 1/6"      # 1/2
cargo test
# or Docker (static Alpine, non-root)
docker build -t pcalc . && docker run --rm pcalc "2^3^2"   # 512