ProjectsCalculator
A program that takes an arithmetic expression as text, a mix of numbers, the four basic operators and parentheses, and prints its value. Getting every answer right teaches how any program reads a language with operators: breaking text into tokens, deciding which operator binds tighter, rewriting the expression into a form a stack can evaluate, and choosing how numbers and bad input are handled.
From Coding Challenges #7 ↗ by John Crickett
No sign-up. You tell the mentor your language: Java, Python or Node.js.
What you'll learn · 7 concepts
In the order the steps use them. Each one links to the best places to learn it, and you explain it in your own words once its steps are built.
Every expression arrives as one line of text, with or without spaces, and nothing in it marks whether a minus sign subtracts or negates.
Covers: characters into tokens · numbers with many digits and a decimal point · whitespace between tokens · unary minus versus subtraction · characters the calculator doesn't know
Crafting Interpreters: Scanning ↗ · Lexical analysis (Wikipedia) ↗
The first example on the page already mixes all four operators, so it needs multiplication and division before addition and subtraction, and step 2 adds parentheses to override that order.
Covers: precedence levels · left and right associativity · parentheses as an override · where a sign and a power meet
Order of operations (Wikipedia) ↗ · Operator associativity (Wikipedia) ↗ · Crafting Interpreters: Parsing Expressions, Ambiguity and the Parsing Game ↗
Step 2 recommends this route: convert the expression to postfix with the shunting-yard algorithm, then evaluate the postfix form.
Covers: infix, prefix and postfix notation · why postfix needs no parentheses · the operator stack and the output · popping by precedence and associativity · parentheses and functions on the stack · precedence climbing as another route
Shunting yard algorithm (Wikipedia) ↗ · Reverse Polish notation (Wikipedia) ↗ · Parsing expressions by precedence climbing (Eli Bendersky) ↗
Step 2 evaluates the shunting-yard output with a stack, and the whole challenge is meant as practice with that data structure.
Covers: push numbers, pop for operators · operand order · how many operands each operator takes · exactly one value at the end · building a syntax tree instead of a value
Stack (abstract data type) (Wikipedia) ↗ · Stack machine (Wikipedia) ↗ · Crafting Interpreters: A Virtual Machine ↗
Step 1 asks you to decide between whole and decimal results, and division is where the choice shows: 7 / 2 has to give 3 or 3.5 on purpose. The sine, cosine and tangent of step 3 only work in floating point.
Covers: whole versus decimal results · binary fractions and rounding error · how integer division rounds · division by zero · how many digits to print · comparing within a tolerance
The Floating-Point Guide ↗ · What Every Computer Scientist Should Know About Floating-Point Arithmetic (David Goldberg) ↗ · Modulo, including how integer division rounds (Wikipedia) ↗
Step 1 asks you to handle invalid input, and a calculator meets plenty of it: typos, missing numbers, stray brackets and division by zero.
Covers: which stage finds which error · unbalanced parentheses · missing operands and operators in a row · syntax errors versus arithmetic errors · a message, a position and a non-zero exit code
Crafting Interpreters: Parsing Expressions, Syntax Errors ↗ · Bash manual: Exit Status ↗
Step 3 asks for your own automated tests, and the page warns that the step 2 design will probably replace your first one, which is only safe with tests in place.
Covers: test first, then code, then clean up · a table of expressions and expected results · one case for each rule · expected values from outside your program · refactoring under tests
Test-driven development (Wikipedia) ↗ · Martin Fowler: Test Driven Development ↗ · Refactoring (Martin Fowler) ↗
What you'll build · 3 steps
Steps of 30 to 60 minutes, in your own editor and language. Each one has a check, so you know when it works.
Create the project and settle how the calculator runs: a command-line program that takes the whole expression as a single argument and prints the result.
Works whenAn expression passed in quotes reaches your program as one argument, multiplication sign included. Without the quotes, the shell may expand the star into file names.
Evaluate an expression made of numbers and the four basic operators, without parentheses, and print its value, doing multiplication and division before addition and subtraction. Decide whether results are whole numbers or decimals, and reject input that isn't a valid expression with a clear message.
Works when2 * 3 gives 6, and the page's longer example, 1 + 22 - 12 * 33 / 2, gives -175. Input such as two operators in a row gives an error message instead of a number.
Concepts: tokenising an expression · operator precedence and associativity · numbers · reporting malformed expressions
Support parentheses, so that grouping can override the usual order of operators. The challenge suggests converting the expression to postfix with the shunting-yard algorithm, then evaluating the postfix form with a stack.
Works when1 + 1 * 5 gives 6 and (1 + 1) * 5 gives 10, worked out by hand since the page gives no answers for them. The page's opening examples also hold: 2 * 3 + 4 gives 10 and 10 / (6 - 1) gives 2.
Concepts: operator precedence and associativity · infix, postfix and the shunting-yard algorithm · evaluating with a stack
Go further on your own: write and automate your own test cases, handle parentheses nested several levels deep, and add functions such as sine, cosine and tangent.
Works whenYour automated tests pass, with at least one case for each rule and each kind of bad input, and expressions with functions match a trusted calculator such as bc with its maths library, which works in radians, within a small tolerance.
Concepts: infix, postfix and the shunting-yard algorithm · numbers · tests that let you change the design