RPN Scientific Calculator

A scientific calculator that converts infix expressions into Reverse Polish Notation (RPN) and visualizes the underlying Abstract Syntax Tree (AST) as a labeled diagram image.

Standard math writes operators between operands — this is called infix notation:

3 + 4
(3 + 4) * 2
sin(3 + 4) * 2

Reverse Polish Notation (RPN), also called postfix notation, places operators after their operands. No parentheses are needed because the position of operands already encodes the evaluation structure:

3 4 +
3 4 + 2 *
3 4 + sin 2 *

RPN was introduced by Australian philosopher Charles Hamblin in 1957, building on the work of Polish logician Jan Łukasiewicz, who invented prefix (Polish) notation in the 1920s. The name "Reverse Polish" reflects that operators come after operands, the reverse of Łukasiewicz's scheme.

This calculator is powered by two classic algorithms, both rooted in Dijkstra's work.

Invented by Edsger W. Dijkstra in 1961, the Shunting-yard algorithm converts an infix expression to RPN (or an AST) in a single left-to-right pass using an operator stack and an output queue.

Input:  3 + 4 * 2

Result RPN: 3 4 2 * + = 3 + (4 × 2) = 11 ✓

The key rule: before pushing an operator o1, pop all operators o2 from the stack where:

• prec(o2) > prec(o1), or
• prec(o2) == prec(o1) and o1 is left-associative

This naturally handles precedence and associativity without any look-ahead.

For the right-associative ^, the rule is reversed — equal precedence does not trigger a pop:

Input:  2 ^ 3 ^ 2

Result: 2 3 2 ^ ^ = 2^(3^2) = 2^9 = 512 ✓

This project uses a Pratt parser (recursive descent with precedence climbing) to build an AST directly, then derives RPN via post-order traversal. Pratt parsing and Shunting-yard are equivalent in power — they both encode the same precedence and associativity rules; Pratt operates top-down on the call stack while Shunting-yard operates bottom-up on an explicit stack.

Once an expression is in RPN form, evaluation is a single linear pass with a stack:

1. Read tokens left to right
2. Number → push onto stack
3. Operator / function → pop operands, compute, push result

For 3 4 2 * +:

token  stack
3      [3]
4      [3, 4]
2      [3, 4, 2]
*      [3, 8]      ← pop 4, 2 → push 4*2
+      [11]        ← pop 3, 8 → push 3+8

Result: 11

For 3 4 + sin 2 *:

token  stack
3      [3]
4      [3, 4]
+      [7]         ← pop 3, 4 → push 7
sin    [0.6570]    ← pop 7 → push sin(7)
2      [0.6570, 2]
*      [1.3140]    ← pop 0.6570, 2 → push result

Result: 1.3140

No parentheses, no precedence rules needed — the stack handles everything automatically. This is why RPN was widely used in early calculators and stack-based virtual machines (Forth, JVM, CPython bytecode).

Input string  →  Tokenizer  →  Parser  →  AST
                                            │
                              ┌─────────────┤
                              │             │
                         RPN Converter  Evaluator
                              │
                          Visualizer → JPG

Right-associativity of ^ means 2 ^ 3 ^ 2 parses as 2 ^ (3 ^ 2) = 512, not (2 ^ 3) ^ 2 = 64.

log is the base-10 logarithm (common log, log₁₀). log(10) = 1, log(100) = 2. It is not the natural logarithm (ln).

Every calculation produces a .jpg image saved to output/trees/.

The image has three header lines:

sin(3 + 4) * 2          ← original infix expression
RPN:    3 4 + sin 2 *   ← reverse polish notation
Result: 1.31397         ← computed value
──────────────────────────────
         [tree diagram]

• Orange rounded rectangles — operators and functions (internal nodes)
• Blue circles — numbers (leaf nodes)
• Arrows — parent → child direction

           *
          / \
        sin   2
         |
         +
        / \
       3   4

The tree encodes evaluation order: to compute *, we need sin first; to compute sin, we need + first; + needs 3 and 4. Post-order traversal of this tree yields the RPN string directly.

git clone https://github.com/<you>/Reverse-Polish-Notation-Calculator.git
cd Reverse-Polish-Notation-Calculator
pip install -r requirements.txt

python -m src.ui.calculator

RPN Scientific Calculator  (type 'quit' to exit)
Supported: + - * / ^ sin cos tan log and parentheses

>> sin(3 + 4) * 2

  Expression : sin(3 + 4) * 2
  RPN        : 3 4 + sin 2 *
  Result     : 1.3139731974375781
  AST image  : output/trees/sin(3_+_4)_*_2.jpg

>> (2 + 3) * (4 - 1) ^ 2

  Expression : (2 + 3) * (4 - 1) ^ 2
  RPN        : 2 3 + 4 1 - 2 ^ *
  Result     : 45.0
  AST image  : output/trees/(2_+_3)_*_(4_-_1)_^_2.jpg

>> quit

python -m src.ui.calculator "log(100) + 2"

  Expression : log(100) + 2
  RPN        : 100 log 2 +
  Result     : 4.0
  AST image  : output/trees/log(100)_+_2.jpg

from src.ui.calculator import calculate

result = calculate("(2 + 3) * (4 - 1) ^ 2")
print(result["rpn"])        # 2 3 + 4 1 - 2 ^ *
print(result["result"])     # 45.0
print(result["image_path"]) # output/trees/(2_+_3)_*_(4_-_1)_^_2.jpg

Or use individual stages:

from src.core.parser       import parse
from src.core.rpn_converter import ast_to_rpn
from src.core.evaluator    import evaluate_rpn
from src.ast_tree.visualizer import render_ast

ast    = parse("2 ^ 3 ^ 2")
rpn    = ast_to_rpn(ast)          # "2 3 2 ^ ^"
result = evaluate_rpn(rpn)        # 512.0
render_ast(ast, "2 ^ 3 ^ 2", rpn, "output/trees/power.jpg", result=result)

# All tests with coverage report
python -m pytest tests/ -v

# Single module
python -m pytest tests/test_rpn_converter.py -v

107 tests cover every module: tokenizer, parser, RPN converter, evaluator, and visualizer.

src/
├── core/
│   ├── operators.py       ← single source of truth: precedence & associativity
│   ├── tokenizer.py       ← string → token list
│   ├── parser.py          ← token list → AST (Pratt / recursive descent)
│   ├── rpn_converter.py   ← AST → RPN string (post-order traversal)
│   └── evaluator.py       ← RPN string → float (stack machine)
├── ast_tree/
│   ├── nodes.py           ← NumberNode / OperatorNode / FunctionNode
│   └── visualizer.py      ← AST → JPG (matplotlib)
└── ui/
    └── calculator.py      ← CLI entry point

tests/
├── test_operators.py
├── test_tokenizer.py
├── test_parser.py
├── test_rpn_converter.py
├── test_evaluator.py
└── test_visualizer.py

output/
└── trees/                 ← generated JPG images (one per expression)