Skip to content
Tutorials Center
My learning

Topics

Lesson 185 of 201 ยท Projects

Project: Scientific Calculator

Build a Java scientific calculator that parses expressions like sin(pi / 2) + 2 ^ 3 with a tokenizer, the shunting-yard algorithm, sealed token types and Math functions.

Type 2 + 3 * 4 into a calculator and you expect 14, not 20. Type -2 ^ 2 and a good one answers -4. Type sin(30) and it has to know whether you meant degrees or radians. A calculator that understands all of this has to do something a beginner's switch can't: it must read a whole expression, understand its structure and only then compute the answer.

That is the job of a parser, and this project builds one from scratch. You'll write a tokenizer that cuts text into pieces, use Edsger Dijkstra's shunting-yard algorithm to reorder those pieces so that precedence and parentheses take care of themselves, and evaluate the result with a simple stack. The result handles operators, unary minus, parentheses, constants, a dozen Math functions, degree and radian modes and a memory of the last answer.

You'll practice sealed types, records, pattern matching, switch expressions, deques as stacks and the Math class. Everything is one Main file with the commands in the Input box, as in the other projects.

The big idea: infix to postfix

People write infix notation: the operator sits between its operands (3 + 4). It's compact but ambiguous, so we need rules about precedence, associativity and parentheses to decode it. Postfix notation (also called reverse Polish notation, RPN) puts the operator after its operands: 3 4 +. It needs no rules at all. You can evaluate it with one stack:

  • see a number: push it
  • see an operator: pop two numbers, apply the operator, push the result

Here is 2 + 3 * 4 in postfix, and how the stack evolves:

flowchart LR
    A["Infix: 2 + 3 * 4"] -->|"shunting-yard"| B["Postfix: 2 3 4 * +"]
    B -->|"evaluate with a stack"| C["14"]

The shunting-yard algorithm converts the expression once; evaluation is then a trivial loop.

For 2 3 4 * +: push 2, push 3, push 4, then * pops 4 and 3 and pushes 12, then + pops 12 and 2 and pushes 14. Notice that precedence has vanished: the order of tokens already says what to do first.

The shunting-yard algorithm does the conversion with an output list and an operator stack, like a railway yard that sorts trains. It reads tokens left to right:

  1. A number goes straight to the output.
  2. An operator first pops operators off the stack to the output as long as the stack's top operator binds tighter (or equally tight, for left-associative operators), then it is pushed.
  3. An opening parenthesis is pushed. A closing parenthesis pops operators to the output until the matching opening parenthesis, which is discarded.
  4. At the end, everything left on the stack goes to the output.

Stage 1: arithmetic with the four operators and power

Start small: numbers, + - * / ^ and parentheses. Tokens are a sealed interface with three record types, so the compiler checks that every switch over tokens covers every case.

Java Stage 1: tokenizer, shunting-yard and evaluation

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

Study the postfix lines:

  • 2 + 3 * 4 becomes 2 3 4 * +. When * arrives, the top of the stack is +, which binds looser, so nothing is popped and * sits on top. It leaves the stack first, which means it is applied first.
  • 10 - 4 - 3 becomes 10 4 - 3 -, which is (10 - 4) - 3 = 3. For two operators of equal precedence the algorithm pops the earlier one first. That's left associativity.
  • 2 ^ 3 ^ 2 becomes 2 3 2 ^ ^, which is 2 ^ (3 ^ 2) = 512. Power is right associative, so on a tie it does not pop. That one boolean, rightAssociative, is the whole difference.
  • Parentheses never reach the output. They only change when things are popped.

Why is the Deque the right stack? ArrayDeque.push and pop work at the front and run in constant time. The older Stack class is synchronized and based on Vector, so the deque lesson recommends ArrayDeque for every new stack.

What stage 1 can't do

It falls over on almost anything else: -5 (unary minus), sin(2) (functions with names), pi (constants), max(3, 7) (several arguments, separated by commas), and 2 + (broken input, which crashes with an exception from pop). A calculator that crashes on a typo is not a calculator. The final stage fixes every one of these.

Stage 2: the scientific calculator

The extensions, in the order they appear in the code:

  • Unary minus. The tokenizer decides whether a - is binary (subtraction) or prefix (negation) by looking at the previous token: at the start, after another operator, after a comma or after an opening parenthesis, it must be a negation, because there's no left operand. Negation becomes its own operator neg with precedence between * and ^. That makes -2 ^ 2 equal to -4 (power first, then negate) while -2 * 3 is (-2) * 3. Prefix operators have no left operand, so when one arrives nothing is popped.
  • Functions. A word followed by ( is a function name. It goes on the stack like an operator; when its closing parenthesis is found it moves to the output right after its arguments. Each function has a known arity (number of arguments), which the evaluator uses to pop the right number of values.
  • Commas. Inside a function call, a comma separates arguments. It pops operators to the output until the enclosing parenthesis, so every argument is complete before the next begins.
  • Constants. pi, e, tau and ans (the last result) are replaced by numbers in the tokenizer.
  • Angle modes. Trigonometric functions take radians in Java. A degrees flag converts on the way in (toRadians) and out (toDegrees for inverse functions).
  • Error handling. Every problem throws a CalcException with a plain message: unknown names, missing or extra parentheses, missing operands, division by zero, results that aren't real numbers, wrong argument counts.
  • Display. Doubles are rounded to 12 significant digits with BigDecimal so 0.1 + 0.2 shows 0.3, and anything smaller than 1e-12 shows as 0 so sin(pi) isn't 1.2246467991473532E-16. The calculation itself stays in double; only the display is rounded.
Java Stage 2: the complete 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 IO.readln() or a Scanner), it gets the next line from this box.

Go through the output in groups:

  • Precedence and associativity: 2 + 3 * 4 is 14, (2 + 3) * 4 is 20, 2 ^ 3 ^ 2 is 512.
  • Unary minus: -2 ^ 2 is -4 because neg ranks below ^, and 2 ^ -2 is 0.25 because the negation applies to the 2 after the ^.
  • Display rounding: 0.1 + 0.2 shows 0.3, and sin(pi) shows 0 instead of a speck of floating-point noise.
  • Angle modes: after deg, sin(30) is 0.5, cos(60) is 0.5 and atan(1) is 45. In radian mode sin(pi / 2) was 1.
  • Functions with two arguments: max(3, 7) * min(2, 9) is 14, and the comma handling makes each argument a complete sub-expression.
  • ans: fact(5) is 120, so 2 * ans is 240.
  • rpn command: shows the postfix form of -sin(30) + 2 ^ 3, which is a great way to debug a parser.
  • The error lines: each broken input is caught with its own message, and ans isn't changed by a failed calculation.

Design notes

  • A sealed interface makes switch safe. Add a new token type and every switch without a default stops compiling until you handle it. The evaluator uses default for token kinds that can't appear in postfix output, which is a deliberate trade-off.
  • Pattern-matching instanceof loops like while (stack.peek() instanceof Op top && shouldPop(top, op)) read almost like the algorithm's description. peek() returns null on an empty stack, and null instanceof Op is false, so the loop ends by itself.
  • The tokenizer knows about context. Deciding whether - is unary needs the previous token. That's the standard place to handle it, and it keeps the parser free of special cases.
  • Wrong argument counts are caught late. sin(1, 2) produces 1 2 sin: sin takes the 2, leaving the 1, and the final "more than one value" check reports a malformed expression. A stricter parser would count arguments per call.

Ideas to extend it

  • Allow implicit multiplication (2pi, 3(4 + 1)) by inserting a * token when a number is followed by a name or an opening parenthesis.
  • Add variables: x = 5 stores a value in a Map<String, Double>, and later expressions can use x.
  • Use BigDecimal for the whole calculation, with a precision setting, and compare it to double on 0.1 + 0.2.
  • Add sinh, cosh, gamma, nCr and nPr, and a history command.
  • Build a Swing front end with a display and buttons that call the same evaluate method.
  • Print the parse as a tree instead of postfix by building nodes in the evaluator.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Why is postfix notation easy to evaluate?

    In postfix the order of tokens already says what to compute first. Numbers are pushed; each operator pops its operands and pushes the result.
  2. 2. In the shunting-yard algorithm, what makes 2 ^ 3 ^ 2 equal 2 ^ (3 ^ 2) while 10 - 4 - 3 equals (10 - 4) - 3?

    On a precedence tie, left-associative operators (like minus) pop the earlier operator first. Right-associative ones (like power) do not pop, so the rightmost operator is applied first.
  3. 3. How does the tokenizer decide that the - in 2 * -3 is a negation and not a subtraction?

    A binary minus needs a value on its left. If the previous token can't end an operand, the minus must be a prefix operator.
  4. 4. Why does -2 ^ 2 evaluate to -4 in this calculator?

    The neg operator ranks below ^, so ^ is applied to the 2 first and the result is negated, matching the usual mathematical convention.

Summary

  • A parser turns text into structure in stages: a tokenizer produces tokens, shunting-yard converts infix to postfix, and a stack evaluates the postfix list.
  • Precedence and associativity live in two tiny functions, and parentheses only change when operators are popped.
  • Sealed token records and pattern-matching switch make every token case explicit and compiler-checked.
  • Unary minus, function calls, commas and constants are handled by looking at context in the tokenizer and by a few extra rules in the algorithm.
  • Report every user mistake with a precise CalcException instead of letting a stack operation crash.
  • Keep calculation in double and round only for display.

Next: Project: Memory Card Game, where you'll model a matching game, drive it with timers, and wrap it in a Swing window.