hard Algorithms & Recursion

Recursive Descent Calculator

The Brief

A spreadsheet vendor is building a formula engine and needs the maths layer first. Build a calculator that takes a string expression and returns its numeric value. Operator precedence, parentheses, unary minus, and named functions are all in scope.

Supported operators: +, -, *, /, // (integer division), %, ** (right-associative). Parentheses for grouping. Unary plus and minus. Named function calls: sqrt, abs, min, max, floor, ceil, round, sin, cos, log. Constants: pi, e.

No eval(). No ast.literal_eval(). No third-party parser libraries. Tokenize the input yourself, then parse and evaluate with recursive descent.

Acceptance Criteria

Tap a criterion to mark it off as you work. Tap a category header to expand or collapse.

1 Array

2 Array

3 Array

4 Array

💡 Hints 0 / 6

Guest Mode Attempt this challenge freely, or log in to earn EXP & CodeCoins.

solution.py

Python 3

import math
import re


FUNCS = {
    "sqrt": math.sqrt, "abs": abs, "min": min, "max": max,
    "floor": math.floor, "ceil": math.ceil, "round": round,
    "sin": math.sin, "cos": math.cos, "log": math.log,
}
CONSTS = {"pi": math.pi, "e": math.e}


def tokenize(expr):
    """Return list of (kind, value) tokens, ending with ("EOF", None)."""
    # TODO: build using re.finditer with a pattern that captures NUMBER, IDENT, OP
    pass


class Parser:
    def __init__(self, tokens):
        self.tokens = tokens
        self.pos = 0

    # TODO: parse_expr / parse_term / parse_factor / parse_unary / parse_primary


def evaluate(expression):
    """Tokenize, parse, and return the numeric result."""
    pass

Console