Skip to content
Tutorials Center
My learning

Topics

Lesson 122 of 134 ยท Projects

Project: Expression Calculator

Build a calculator in Kotlin step by step - a tokenizer, a recursive descent parser, a sealed syntax tree, an evaluator with clear errors, and small tests, all runnable in your browser.

In this project you build a program that reads a text like 2 + 3 * (4 - 1) and prints 11. It sounds small, but it is the classic exercise behind every interpreter, spreadsheet formula bar and query language. You will meet the three stages that real compilers use: a tokenizer that cuts text into pieces, a parser that finds the structure in those pieces, and an evaluator that computes the answer.

Along the way you use many things from earlier lessons: sealed classes and interfaces, data classes, exhaustive when, custom exceptions, reading input and lists. Every step below runs on its own, so you can edit and experiment. The next project is the to-do manager.

The plan

We split the job into three small programs that pass data to each other:

TEXT
"2 + 3 * 4"  --tokenizer-->  [2] [+] [3] [*] [4]
             --parser----->  Plus(2, Times(3, 4))     (a tree)
             --evaluator-->  14.0

Why a tree? Because 2 + 3 * 4 does not mean "go left to right". Multiplication binds tighter, so the 3 * 4 part must be calculated first. A tree makes that visible: the deepest parts are calculated first.

The grammar (the rules of what is allowed) is written like this, from weakest to strongest binding:

TEXT
expression = term   (("+" | "-") term)*
term       = power  (("*" | "/" | "%") power)*
power      = unary  ("^" power)?
unary      = "-" unary | primary
primary    = number | "(" expression ")" | name "(" expression ")"

Each rule becomes one Kotlin function. That is the whole trick of recursive descent: the code mirrors the grammar.

Step 1: tokens and the tokenizer

A token is one meaningful piece of the input. We model tokens with a sealed interface, so that when can later check that we handled every kind.

Kotlin Step 1 - the tokenizer

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 readln()), it gets the next line from this box.

The loop keeps an index i and looks at one character at a time. Whitespace is skipped. A digit or dot starts a number, so we keep reading while the characters still belong to it, then convert the slice with toDoubleOrNull(). A string like 1.2.3 is cut as one literal but cannot be converted, so we report it with its position. A letter starts a name (used for function names such as sqrt). Anything else is reported as an unexpected character.

Notice three design decisions that make the later steps easier:

  • Every token remembers its position. Good error messages say where the problem is.
  • CalcException is our own type. The caller can catch calculator mistakes without hiding real bugs such as a NullPointerException.
  • The tokenizer knows nothing about meaning. It does not care whether + + makes sense; that is the parser's job.

The tokenizer creates Double numbers. A real calculator might prefer BigDecimal for money, but Double keeps the project short. See working with numbers for the trade-offs.

Step 2: the syntax tree and the parser

Now we define the shape of the tree. Another sealed interface describes every node that can occur:

  • a number,
  • a negation of one node,
  • a binary operation with a left and a right node,
  • a function call with one argument.

The parser holds the token list and a position pos. Helper functions peek() and next() look at and consume the current token. Then each grammar rule is one function.

Kotlin Step 2 - parse into a tree

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 readln()), it gets the next line from this box.

Read the printed trees carefully, they are the heart of the lesson. 2 + 3 * 4 has the * node inside the + node, so it is calculated first. Parentheses override this because primary() calls expression() again for whatever is inside them.

Two details deserve attention:

  1. Left associativity. 10 - 4 - 3 must mean (10 - 4) - 3. The while loop in expression() builds the tree leaning to the left. If you wrote it with plain recursion on the right, you would get 10 - (4 - 3), a wrong answer that is easy to miss.
  2. Right associativity of ^. In mathematics 2^3^2 means 2^(3^2). So power() calls itself for the right side instead of looping.

Notice how primary() is a single when expression with a subject that is also declared (when (val token = next())). The null branch handles the end of input; the else branch catches every other token, such as a stray operator.

Step 3: evaluating the tree

An evaluator is a short recursive function with one when over the sealed Node. Because the interface is sealed, the compiler guarantees that every node kind is handled, and no else branch is needed.

Kotlin Step 3 - evaluate

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 readln()), it gets the next line from this box.

The division check is deliberate. With Double, 1.0 / 0.0 does not crash but gives Infinity, which is rarely what a user of a calculator wants. Choosing to turn it into an error is a design decision, and it belongs in the evaluator.

Because evaluate and the parser are separate, you can also write other things that walk the tree: a pretty printer, a simplifier (x * 1 becomes x), or a compiler to stack-machine instructions. This is why interpreters build a tree at all.

Step 4: a sealed when that the compiler checks

Suppose you extend the language later with a new node, say a Var for variables, but forget to teach the evaluator about it. Because Node is sealed, the compiler refuses the code. This TryIt fails on purpose.

Kotlin A forgotten node kind (fails on purpose)

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 readln()), it gets the next line from this box.

The compiler reports that the when expression must be exhaustive and names the missing case is Var. Add the branch (is Node.Var -> throw CalcException("No variables yet") or a lookup in a map) and the program compiles again. This is the biggest advantage of sealed hierarchies: a missing case is a compile error today instead of a crash in production later.

Step 5: the whole program with a read loop

Now we put everything together. The program reads lines until it reaches an empty line or the end of input, evaluates each, and prints either the result or the error. A small format function prints whole numbers without .0.

Kotlin Step 5 - the finished calculator

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 readln()), it gets the next line from this box.

The input box above is preset with ten lines. Look at which ones succeed and what each failure says. The try is used as an expression (see exceptions): both branches produce a String, so one variable receives either the result or the message.

Step 6: testing it

A calculator is a perfect candidate for tests, because the inputs and expected outputs are simple. The runner has no kotlin.test, so we write a tiny helper. The pattern is the same as in a real test framework: a table of cases, and a message when one fails. The helper below checks the expression to answer pairs and the expression to error pairs separately.

Kotlin A tiny test suite

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 readln()), it gets the next line from this box.

One test fails, and that is intended: 100 / 8 is 12.5, so the failing line shows the expected and the actual value side by side. A good failure message tells you what you expected and what you got. Fix the expectation to 12.5 and all tests pass. In a real project, put the same cases in a kotlin.test file (testing in Kotlin), and run them on every change.

Ideas to extend it

  • Variables. Add Node.Var and an environment Map<String, Double> passed to evaluate. Let the user write x = 5.
  • More functions. min(a, b) needs a comma token and a list of arguments in Call.
  • Better errors. Keep the source text and print a caret under the failing position.
  • A pretty printer. Walk the tree and print it fully parenthesized, to confirm the precedence you intended.
  • Exact decimals. Replace Double by BigDecimal so that 0.1 + 0.2 prints 0.3.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. Why does the calculator build a tree instead of calculating while it reads?

    A tree shows the structure of the expression. In 2 + 3 * 4 the multiplication is below the addition, so it is evaluated first.
  2. 2. What makes 10 - 4 - 3 come out as 3 instead of 9?

    A while loop that keeps wrapping the left side gives left associativity. Recursing on the right side would produce 10 - (4 - 3) = 9.
  3. 3. What happens if a new subtype is added to the sealed Node interface and an exhaustive when without else is not updated?

    For sealed types, a when used as an expression must cover all subtypes, so the compiler reports the missing case.
  4. 4. Why is CalcException a custom exception class?

    A dedicated type separates expected user mistakes from programming errors such as a NullPointerException.
  5. 5. Why does power() call itself for the right-hand side instead of looping?

    Exponentiation is right-associative, so the right operand is parsed by the same rule again.

Summary

  • A calculator has three stages: tokenizer (text to tokens), parser (tokens to a tree), evaluator (tree to a value).
  • Recursive descent turns each grammar rule into one function; precedence comes from which function calls which.
  • Loops give left associativity (-, /); self-recursion gives right associativity (^).
  • Sealed interfaces plus when make the compiler check that every node kind is handled.
  • A custom exception with positions in its messages makes errors useful.
  • Separating the stages lets you test each one and add new tools (printers, simplifiers) without touching the others.

Next: Project: Command-Line To-Do Manager