Skip to content
Tutorials Center
My learning

Topics

Lesson 54 of 61 ยท Projects

Project: Expression Evaluator

Build a calculator engine in Dart: tokenize text, parse it with recursive descent into a sealed AST, evaluate it with pattern matching and simplify it.

When you type 2 + 3 * 4 into a calculator, something has to know that the answer is 14, not 20. That something is a small language implementation: it reads text, understands its structure, and computes a result. Every compiler, spreadsheet formula bar and query language does the same three jobs, just at larger scale.

In this project you build an evaluator for arithmetic expressions with + - * / ^, unary minus, parentheses, variables and a few functions such as sqrt. It is the best showcase for Dart 3 features: records for tokens, a sealed class hierarchy for the syntax tree, enums with fields for operators, and pattern matching for evaluation and simplification.

The Dart code is read-only because Dart is not installed on the site; the TypeScript stand-ins implement the same design and run here.

The pipeline

flowchart LR
    A["Source text<br/>1 + 2 * 3"] --> B["Tokenizer"]
    B --> C["Tokens<br/>1 + 2 * 3"]
    C --> D["Parser"]
    D --> E["AST<br/>a tree"]
    E --> F["Evaluator"]
    F --> G["Value 7"]
    E --> H["Simplifier"]
    H --> E

Each stage has one job and hands a simpler-to-use structure to the next.

Separating the stages is what makes the program manageable. The tokenizer does not know about precedence, the parser does not do arithmetic, and the evaluator never looks at characters.

Stage 1: the tokenizer

A token is the smallest meaningful piece: a number, a name, an operator, a parenthesis. A record is all we need to hold one, plus its position in the text so errors can point at the right place.

DART
enum TokenKind { number, name, plus, minus, star, slash, caret, leftParen, rightParen, end }

typedef Token = ({TokenKind kind, String text, int position});

class ParseError implements Exception {
  ParseError(this.message, this.position);
  final String message;
  final int position;

  @override
  String toString() => 'ParseError at $position: $message';
}

bool _isDigit(String ch) => '0123456789.'.contains(ch);
bool _isLetter(String ch) => RegExp(r'[A-Za-z_]').hasMatch(ch);

List<Token> tokenize(String source) {
  final tokens = <Token>[];
  var i = 0;
  while (i < source.length) {
    final ch = source[i];
    if (ch == ' ') {
      i++;
    } else if (_isDigit(ch)) {
      final start = i;
      while (i < source.length && _isDigit(source[i])) {
        i++;
      }
      tokens.add((kind: TokenKind.number, text: source.substring(start, i), position: start));
    } else if (_isLetter(ch)) {
      final start = i;
      while (i < source.length && (_isLetter(source[i]) || _isDigit(source[i]))) {
        i++;
      }
      tokens.add((kind: TokenKind.name, text: source.substring(start, i), position: start));
    } else {
      final kind = switch (ch) {
        '+' => TokenKind.plus,
        '-' => TokenKind.minus,
        '*' => TokenKind.star,
        '/' => TokenKind.slash,
        '^' => TokenKind.caret,
        '(' => TokenKind.leftParen,
        ')' => TokenKind.rightParen,
        _ => throw ParseError("Unexpected character '$ch'", i),
      };
      tokens.add((kind: kind, text: ch, position: i));
      i++;
    }
  }
  tokens.add((kind: TokenKind.end, text: '', position: source.length));
  return tokens;
}

The final end token is a sentinel: the parser can always look at the current token without checking for the end of the list first. A raw string r'[A-Za-z_]' keeps the backslash-free regex readable, as you saw in strings.

TypeScript Stage 1: the tokenizer (stand-in)

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with node:readline or readFileSync(0)), it gets the next line from this box.

Stage 2: the syntax tree

The parser produces a tree whose nodes are the meaningful parts of the expression. In Dart 3 the natural model is a sealed class with one final class per kind of node:

DART
enum BinaryOp {
  add('+'), subtract('-'), multiply('*'), divide('/'), power('^');

  const BinaryOp(this.symbol);
  final String symbol;
}

sealed class Expr {
  const Expr();
}

final class Number extends Expr {
  const Number(this.value);
  final double value;
}

final class Variable extends Expr {
  const Variable(this.name);
  final String name;
}

final class Negate extends Expr {
  const Negate(this.operand);
  final Expr operand;
}

final class Binary extends Expr {
  const Binary(this.op, this.left, this.right);
  final BinaryOp op;
  final Expr left;
  final Expr right;
}

final class Call extends Expr {
  const Call(this.name, this.argument);
  final String name;
  final Expr argument;
}

Because Expr is sealed, every switch over an Expr must handle all five node types, or the program does not compile. When you add a sixth node later, the compiler walks you to every place that needs updating.

Stage 3: the parser

Precedence, "* binds tighter than +", is the heart of parsing. The classic technique is recursive descent: one function per precedence level, each calling the next-tighter level. The grammar, from loosest to tightest, is:

TEXT
expression = term   { ("+" | "-") term }
term       = unary  { ("*" | "/") unary }
unary      = "-" unary | power
power      = primary [ "^" unary ]
primary    = number | name | name "(" expression ")" | "(" expression ")"

Each { ... } means "repeat", which becomes a while loop, and that loop makes + and - left-associative: 10 - 3 - 2 is (10 - 3) - 2. The power rule recurses through unary on its right side, which makes ^ right-associative: 2 ^ 3 ^ 2 is 2 ^ (3 ^ 2). And because unary sits above power, -2 ^ 2 means -(2 ^ 2), which is -4, just as in mathematics.

flowchart TD
    A["Binary +"] --> B["Number 1"]
    A --> C["Binary *"]
    C --> D["Number 2"]
    C --> E["Number 3"]

The tree for 1 + 2 * 3: the multiplication is deeper, so it is evaluated first.

DART
class Parser {
  Parser(this._tokens);

  final List<Token> _tokens;
  var _pos = 0;

  Token get _current => _tokens[_pos];

  Token _advance() {
    final token = _tokens[_pos];
    if (token.kind != TokenKind.end) _pos++;
    return token;
  }

  void _expect(TokenKind kind, String symbol) {
    if (_current.kind != kind) {
      throw ParseError("Expected '$symbol'", _current.position);
    }
    _advance();
  }

  Expr parse() {
    final expr = _expression();
    if (_current.kind != TokenKind.end) {
      throw ParseError("Unexpected '${_current.text}'", _current.position);
    }
    return expr;
  }

  Expr _expression() {
    var left = _term();
    while (_current.kind == TokenKind.plus || _current.kind == TokenKind.minus) {
      final op = _advance().kind == TokenKind.plus ? BinaryOp.add : BinaryOp.subtract;
      left = Binary(op, left, _term());
    }
    return left;
  }

  Expr _term() {
    var left = _unary();
    while (_current.kind == TokenKind.star || _current.kind == TokenKind.slash) {
      final op = _advance().kind == TokenKind.star ? BinaryOp.multiply : BinaryOp.divide;
      left = Binary(op, left, _unary());
    }
    return left;
  }

  Expr _unary() {
    if (_current.kind == TokenKind.minus) {
      _advance();
      return Negate(_unary());
    }
    return _power();
  }

  Expr _power() {
    final base = _primary();
    if (_current.kind == TokenKind.caret) {
      _advance();
      return Binary(BinaryOp.power, base, _unary());
    }
    return base;
  }

  Expr _primary() {
    final token = _advance();
    switch (token.kind) {
      case TokenKind.number:
        final value = double.tryParse(token.text);
        if (value == null) throw ParseError("Bad number '${token.text}'", token.position);
        return Number(value);
      case TokenKind.name:
        if (_current.kind != TokenKind.leftParen) return Variable(token.text);
        _advance();
        final argument = _expression();
        _expect(TokenKind.rightParen, ')');
        return Call(token.text, argument);
      case TokenKind.leftParen:
        final inner = _expression();
        _expect(TokenKind.rightParen, ')');
        return inner;
      case TokenKind.end:
        throw ParseError('Unexpected end of input', token.position);
      default:
        throw ParseError("Unexpected '${token.text}'", token.position);
    }
  }
}

Notice the _advance guard: it never moves past the end token, so a broken input like 3 + produces a clear "unexpected end of input" instead of a RangeError. In the stand-in below, a tree function prints the structure so you can see precedence and associativity for yourself.

TypeScript Stage 3: the parser prints trees (stand-in)

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with node:readline or readFileSync(0)), it gets the next line from this box.

Stage 4: evaluation and simplification with patterns

With a sealed AST, evaluation is a single switch expression. Each arm destructures one node type with an object pattern and recursively evaluates the pieces.

DART
import 'dart:math' as math;

class EvalError implements Exception {
  EvalError(this.message);
  final String message;

  @override
  String toString() => 'EvalError: $message';
}

double evaluate(Expr expr, Map<String, double> variables) => switch (expr) {
      Number(:final value) => value,
      Variable(:final name) =>
        variables[name] ?? (throw EvalError('Unknown variable "$name"')),
      Negate(:final operand) => -evaluate(operand, variables),
      Binary(:final op, :final left, :final right) =>
        _apply(op, evaluate(left, variables), evaluate(right, variables)),
      Call(:final name, :final argument) => _call(name, evaluate(argument, variables)),
    };

double _apply(BinaryOp op, double a, double b) => switch (op) {
      BinaryOp.add => a + b,
      BinaryOp.subtract => a - b,
      BinaryOp.multiply => a * b,
      BinaryOp.divide => b == 0 ? throw EvalError('Division by zero') : a / b,
      BinaryOp.power => math.pow(a, b).toDouble(),
    };

double _call(String name, double x) => switch (name) {
      'sqrt' => x < 0 ? throw EvalError('sqrt of a negative number') : math.sqrt(x),
      'abs' => x.abs(),
      'floor' => x.floorToDouble(),
      _ => throw EvalError('Unknown function "$name"'),
    };

Two things to notice. throw is an expression in Dart, so it can sit in the middle of a switch arm or after ??. And math.pow returns num, so .toDouble() keeps the declared return type.

The same pattern style gives a tiny simplifier that removes work before evaluation: fold constants, drop + 0 and * 1, and turn * 0 into 0. A record of the operator and both sides lets one switch express all the rules:

DART
Expr simplify(Expr expr) => switch (expr) {
      Binary(:final op, :final left, :final right) =>
        _simplifyBinary(op, simplify(left), simplify(right)),
      Negate(:final operand) => switch (simplify(operand)) {
          Number(:final value) => Number(-value),
          final inner => Negate(inner),
        },
      Call(:final name, :final argument) => Call(name, simplify(argument)),
      _ => expr,
    };

Expr _simplifyBinary(BinaryOp op, Expr left, Expr right) => switch ((op, left, right)) {
      (_, Number(value: final a), Number(value: final b))
          when !(op == BinaryOp.divide && b == 0) =>
        Number(_apply(op, a, b)),
      (BinaryOp.add, final x, Number(value: 0.0)) => x,
      (BinaryOp.add, Number(value: 0.0), final x) => x,
      (BinaryOp.multiply, final x, Number(value: 1.0)) => x,
      (BinaryOp.multiply, Number(value: 1.0), final x) => x,
      (BinaryOp.multiply, _, Number(value: 0.0)) => const Number(0),
      (BinaryOp.multiply, Number(value: 0.0), _) => const Number(0),
      (BinaryOp.power, final x, Number(value: 1.0)) => x,
      _ => Binary(op, left, right),
    };

The guard on the first case keeps 1 / 0 from being folded, so the error still appears at evaluation time. Patterns are tried top to bottom, so order matters: general constant folding first, then the identity rules.

The last stand-in assembles everything (tokenizer, parser, evaluator, simplifier) and also prints errors with a caret under the faulty position, a small touch that makes a parser feel professional.

TypeScript Stage 4: evaluate, simplify and report errors (stand-in)

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with node:readline or readFileSync(0)), it gets the next line from this box.

Ideas to extend it

  • Add more functions (min/max need several arguments, so change Call to hold a List<Expr> and parse commas).
  • Implicit multiplication such as 2x or 3(1 + 2).
  • A derive(Expr, String variable) function that returns the symbolic derivative, using the same style of switch, then run it through simplify.
  • A small read-eval-print loop with stdin.readLineSync() (see files and command-line programs) that keeps variables between lines.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Why does a recursive descent parser have one function per precedence level?

    expression calls term, which calls unary, and so on. The operators handled deepest, such as * and ^, group their operands first, which gives the right precedence.
  2. 2. How does the parser make 2 ^ 3 ^ 2 mean 2 ^ (3 ^ 2)?

    power parses its right side with unary, which leads back to power. Nesting to the right makes ^ right-associative, while the while loops in expression and term nest to the left.
  3. 3. What is the main benefit of making Expr a sealed class?

    The set of subtypes is known to the compiler, so exhaustiveness is checked. Adding a node type points to each switch that needs a new case.
  4. 4. Why does the simplifier skip constant folding for 1 / 0?

    Folding would raise an error during simplification, changing when and where the problem shows up. The guard leaves the division in the tree.

Summary

  • A small language implementation has a tokenizer, a parser that builds a tree, and passes (evaluate, simplify) that walk the tree.
  • Tokens fit in records; syntax nodes fit in a sealed class hierarchy; operators fit in an enum with fields.
  • Recursive descent gives one function per precedence level; loops make operators left-associative, recursion on the right side makes ^ right-associative.
  • Pattern matching with object and record patterns turns each tree transformation into a short switch, and exhaustiveness checking keeps it complete.
  • Carry positions in tokens and errors so messages can point at the problem.

Next: Project: Async Event Pipeline.