Skip to content
Tutorials Center
My learning

Topics

Lesson 33 of 40 ยท Projects

Project: A Stack-Based Calculator

Build a postfix (RPN) calculator in toy assembly that uses the stack to evaluate expressions, handles errors, and is tested against JavaScript.

The stack is the CPU's scratch pad for things that nest: return addresses, saved registers, and, as it happens, half-finished arithmetic. In this project you will use it for the last job. You will write a program in toy assembly that evaluates arithmetic written in postfix notation (also called reverse Polish notation, RPN), where 3 4 + 2 * means (3 + 4) * 2. Postfix needs no parentheses and no precedence rules, and a stack evaluates it in a single left-to-right pass, which makes it a perfect first real program.

You should be comfortable with the stack, CALL and RET, compare and jump and loops. The programs run on the toy CPU from Meet the Toy CPU. As in the other TryIts, the interpreter is included in the code (it takes one extra option, data, to preload memory); the assembly is in a template string you can edit.

Postfix and the stack

In ordinary (infix) notation the operator sits between its operands, so you need parentheses and precedence to know the order. In postfix the operator comes after both operands, so the order is simply the order you read:

Infix Postfix
3 + 4 3 4 +
(3 + 4) * 2 3 4 + 2 *
2 + 3 * 4 2 3 4 * +

The evaluation rule has only two cases:

  1. A number: push it on the stack.
  2. An operator: pop the right operand, pop the left operand, compute, push the result.

At the end the stack holds exactly one value, the answer. Here is 3 4 + 2 * step by step:

Token Action Stack (top on the right)
3 push 3
4 push 3 4
+ pop 4 and 3, push 7 7
2 push 7 2
* pop 2 and 7, push 14 14
flowchart TD
  A["read next token"] --> B{"number?"}
  B -- "yes" --> C["push it"]
  C --> A
  B -- "no, operator" --> D["pop right operand<br/>pop left operand"]
  D --> E["compute"]
  E --> F["push result"]
  F --> A
  A -- "no tokens left" --> G["pop the answer"]

The whole calculator is this one loop; assembly just spells out every box.

One detail matters for subtraction and division: the operand popped first is the right one. For 5 8 - the stack holds 5 then 8, so the first pop gives 8 and the second gives 5, and the result must be 5 - 8, not 8 - 5.

The design

Our toy CPU has no text input, so the JavaScript around the program does the tokenizing and stores one token per memory cell starting at address 0x2000. We need a way to tell numbers from operators within one array of numbers. The simple trick: numbers are at most 1,000,000, and the operators are the codes 1000001 (+), 1000002 (-), 1000003 (*) and 1000004 (/). One unsigned comparison, cmp rax, 1000000 then ja, sorts them apart.

The registers have fixed jobs, which is how you keep an assembly program readable:

  • rsi: address of the next token; rcx: how many tokens remain.
  • rax: the current token; rbx and rdx: the right and left operands.
  • rdi: the exit status, 0 for success, 1 for division by zero, 2 for leftover operands (similar to a process exit code).

The toy CPU has no div, so the program divides the slow way, by counting how many times the divisor can be subtracted, the same way you would do long division in unary. Its stack is checked, too: popping from an empty stack stops the CPU with an error, which is how a malformed expression like 1 + is caught.

Run it with a trace

First run the shortest interesting expression, 3 4 +, and watch the stack pointer. The trace prints each instruction as it is about to run, with rax, rbx, rdx and rsp before it. Every push lowers rsp by 8 (from 4096 to 4088 to 4080) and every pop raises it again.

JS The calculator, one instruction at a time

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

No output.

Scroll through the trace and find three moments: the two push rax instructions loading 3 and 4 (the stack pointer drops twice), the pair pop rbx, pop rdx at the operator (it rises twice), and the final push rdx of the result (it drops once). The out rax at the end prints 7.

A test suite against JavaScript

A calculator you cannot trust is worse than none, so test it. The script below evaluates a list of expressions on the toy CPU and compares each result to a tiny JavaScript postfix evaluator that follows the same rules (integer division, no negative division). It also feeds in four broken expressions to confirm each one is rejected for the right reason.

JS Test the assembly against JavaScript

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

No output.

Every good expression matches. The bad ones show the three failure modes. 7 0 / reaches the explicit zero check and exits with status 1. 1 + pops two operands from a stack that holds one, so the CPU's own stack check stops it. 1 2 leaves two values behind, which the final cmp rsp, 0x1000 detects. A real calculator would print friendlier messages and a real CPU would not check for you: popping an empty stack on x86-64 just reads whatever bytes happen to be there, which is why high-level languages (and careful assembly programmers) make that check explicit.

The test suite is also a good habit for the whole track: a program is "correct" only relative to something you can compare it with. Here that is a four-line reference implementation.

Accepting normal arithmetic

Nobody types postfix. The standard bridge is the shunting-yard algorithm, which converts infix to postfix using an operator stack of its own: numbers go straight to the output, an operator first pops any waiting operators of higher or equal precedence, and parentheses fence off groups. It does not need assembly (it is parsing, not calculating), so it lives in the JavaScript around the program. The calculator itself is untouched.

JS Infix to postfix to the toy CPU

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

No output.

Notice 10 - 4 - 3 becomes 10 4 - 3 - and gives 3, not 9: operators of equal precedence group from the left, which the >= in the algorithm encodes. Check 2 + 3 * 4 too: the postfix form 2 3 4 * + multiplies first without any rule in the assembly, because the order of tokens already carries the precedence.

Ideas to extend it

  • Add % (remainder) by reusing the division loop: the remainder is what is left in rdx when the loop ends.
  • Add a unary neg operator, or support negative numbers; the division loop currently assumes non-negative operands because jb is an unsigned compare.
  • Replace the 1,000,000 limit with a tag in a second memory cell per token.
  • Turn the operator block into a small subroutine table using call, in the style of Calling Conventions, so adding an operator means adding one routine.
  • Think about what the same program looks like in x86-64: push and pop are the real instructions, imul rdx, rbx and add are unchanged, and a div instruction replaces the division loop (it divides rdx:rax by its operand; see Arithmetic: ADD, SUB, MUL, DIV).

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What does a postfix evaluator do when it reads an operator such as +?

    Numbers are pushed; an operator consumes the two most recent values and leaves one result in their place.
  2. 2. For the postfix expression 9 2 -, which pop gives which operand?

    The right operand was pushed last, so it is popped first. Getting this backwards silently turns 9 - 2 into 2 - 9.
  3. 3. How does the program tell a number from an operator in one array of integers?

    The tokens are plain numbers, so the encoding has to make the two kinds distinguishable. cmp rax, 1000000 followed by ja does the job.
  4. 4. Why does 1 + fail, and how is it detected in this project?

    An operator needs two operands. The toy CPU refuses to pop from an empty stack; on real hardware the program would silently read stale memory unless it checked.
  5. 5. Why does 10 - 4 - 3 convert to 10 4 - 3 -?

    When the second minus arrives, the waiting minus has equal precedence and is popped to the output first. That makes the expression (10 - 4) - 3 = 3.

Summary

  • Postfix evaluation is a single loop: push numbers; for an operator pop the right operand, pop the left operand, compute and push the result.
  • The stack is exactly the right structure for nested, unfinished work; rsp visibly moves by 8 per push or pop in the trace.
  • Encode kinds of tokens so one compare can tell them apart, and give each register a fixed job and document it.
  • Division without a div instruction is repeated subtraction; zero divisors, stack underflow and leftover operands must be checked explicitly.
  • Test assembly against a small reference implementation in a high-level language.
  • Infix input needs only a front end (shunting-yard); the assembly core stays the same.

Next: arrays and nested loops in Project: Prime Sieve in Toy Assembly.