A calculator

A calculator can't work with 12 + 3.5 as one piece of text. Its first job is to split the line into tokens: the numbers and the symbols. Each token also keeps its column, the place in the line where it starts, counted from 1, so that error messages can point at it in the last milestone.

The token types are ready. Token.java is a sealed interface, and NumberToken.java and SymbolToken.java are its two records. In Lexer.java, write tokenize(String line). It goes through the line one character at a time and returns the tokens in a list, in order:

• A space is skipped.
• A digit or a . starts a number, which goes on as long as digits and dots follow. Double.parseDouble turns the number's text into a double, and it becomes a NumberToken with the column of its first character.
• +, -, * and / each become a SymbolToken.
• For any other character, throw an IllegalArgumentException. The last milestone gives it a proper message.

Character.isDigit(c) is true when the character c is a digit, such as 0 to 9. main is ready: it prints the tokens of each line it reads. The check runs:

System.out.println(Lexer.tokenize("12 + 3.5"));

and expects this (a record's toString shows the values of its parts):

[NumberToken[value=12.0, column=1], SymbolToken[symbol=+, column=4], NumberToken[value=3.5, column=6]]

Now the calculator calculates. Calculator.java is new. Its format is ready: it turns a result into text without .0 on whole numbers, so 15.0 becomes 15 and 3.5 stays 3.5.

1. In Calculator.java, write a method apply(char operator, double left, double right) with a switch expression: it returns left + right for '+', left - right for '-', and so on for * and /.
2. Write calculate(String line). It splits the line into tokens and works through them from left to right: the first number, then an operator and a number, again and again, using apply each time. It returns the result as text, made by format. For now, 2 + 3 * 4 gives 20, as (2 + 3) * 4 is. The next milestone teaches the calculator that multiplication comes first.
3. Change main: it creates one Calculator, and prints what calculate returns for each line it reads. It skips blank lines: line.trim().isEmpty() is true for a line with nothing but spaces.

You may assume for now that every line is a correct calculation of numbers and the four operators. With the input:

12 + 3.5
10 - 4 - 3
7 / 2
2 * 3 * 4

the program prints:

15.5
3
3.5
24

In math, 2 + 3 * 4 is 14, because * and / come before + and -. Going from left to right can't do that. So the calculator first builds a tree of the expression, and then calculates the tree.

Three new files hold the tree: Expr.java is a sealed interface, and its records are Literal(double value) for a number and Operation(char operator, Expr left, Expr right). The tree of 2 + 3 * 4 is:

new Operation('+', new Literal(2), new Operation('*', new Literal(3), new Literal(4)))

Parser.java is new too. It reads the tokens with next, the index of the next token, and has one method per level:

• expression() reads a term. Then, as long as the next token is + or -, it steps past that operator, reads another term, and joins the two: result = new Operation(operator, result, term()).
• term() does the same one level lower: numbers joined by * and /.
• number() and nextSymbol() are ready.

term() reads all of 3 * 4 before expression() sees the rest, so the multiplication ends up lower in the tree, as one part of the addition.

Then in Calculator.java:

• Write eval(Expr expr), which returns the value of a tree, with a switch over record patterns. An operation's value is apply on its operator and the values of its two parts.
• Change calculate so that it returns format(eval(new Parser(tokens).parse())). The left-to-right loop isn't needed any more: delete it, and any helper method only it used.

With the input:

2 + 3 * 4
10 - 6 / 2 - 1
8 / 4 / 2

the program prints:

14
6
1

Parentheses say what is calculated first: (2 + 3) * 4 is 20. And a minus sign can stand in front of a number or a parenthesis: -5, 2 - -3, -(2 + 3).

• In Lexer.java, ( and ) become SymbolTokens too.
• Negate.java is new: the record Negate(Expr inner) is a part of the tree with a minus in front. The program doesn't compile when this milestone starts: javac says that Negate isn't allowed to implement Expr. Add it to Expr's permits list. Then javac says that the switch in eval doesn't cover all possible input values: give it a case for Negate, whose value is minus the value of inner.
• In Parser.java, rename number() to factor() (term() calls it), and teach it two more things before it looks for a number:
  • (: step past it, read a whole expression(), and then a ) must come: step past that too. The expression inside is the factor's tree. If the ) is missing, throw an IllegalArgumentException for now.
  • -: step past it and return new Negate(factor()), the factor after it with a minus in front.

The parser now calls itself in a circle: expression() calls term(), term() calls factor(), and factor() calls expression() for the part in parentheses. That's recursion, as in module 55, and a number is its base case.

With the input:

(2 + 3) * 4
2 * (10 - (3 + 1))
(1 + 2) / (4 - 1.5)

the program prints:

20
12
1.2

A line such as rate = 12.5 saves a value under a name, and later lines can use the name: rate * 8.

• Tokens. NameToken.java is new: NameToken(String name, int column). Add it to Token's permits list. In Lexer.java, a letter starts a name, which goes on as long as letters and digits follow, so side2 is one name. Character.isLetter(c) is true for a letter, and Character.isLetterOrDigit(c) for a letter or a digit. = becomes a SymbolToken.
• The tree. Variable.java is new: Variable(String name). Add it to Expr's permits list. In factor(), a NameToken becomes a Variable.
• The values. Calculator keeps them in a field, a map (a HashMap<String, Double>) created in a constructor, so that each line can use what the lines before it saved.
• Saving. In calculate: when the first token is a name and the second is =, the tokens after them are an expression. Calculate it, save the value under the name, and return the name, = and the value, such as pay = 80. A name can get a new value, and its expression can use the old one: x = x * 3. tokens.subList(2, tokens.size()) gives the tokens from index 2 on. Any other line is calculated as before.
• Using. In eval, a Variable's value is the one saved under its name. For a name that has no value yet, throw an IllegalArgumentException for now.

Names are case sensitive: Total and total are two variables. With the input:

rate = 12.5
hours = 8
rate * hours
pay = rate * hours - 20
pay / 2

the program prints:

rate = 12.5
hours = 8
100
pay = 80
40

Right now a typing mistake crashes the calculator. A good one says what's wrong and where, and goes on with the next line.

CalcException.java is new: an unchecked exception that carries a message. Throw it instead of IllegalArgumentException, everywhere, with exactly these messages (the numbers and texts in them are examples):

• unexpected character # at column 5: the lexer meets a character that can't be part of any token.
• bad number 1.2.3 at column 1: Double.parseDouble can't read a number's text. It throws a NumberFormatException then: catch it in the lexer.
• expected a number at column 5: factor() finds no number, name, ( or -. When the line has ended, it's expected a number at the end. This also holds for x =, which is a save with nothing after the =.
• expected ) at column 8, or expected ) at the end: a parenthesis isn't closed.
• expected an operator at column 3: parse() has read a whole expression, but there are tokens left, as in 2 3. Make parse() check for that.
• division by zero: the right side of a / is 0.
• unknown variable cost: a name without a value.

The column is the column of the token where the problem is. To ask any token for its column, add the method int column(); to the Token interface: each of the three records already has a method of that name, so they implement it as they are.

main catches CalcException, prints Error: and the message, and goes on with the next line. A line with an error saves nothing. With the input:

2 + # 3
2 + * 3
2 +
(2 + 3
2 3

the program prints:

Error: unexpected character # at column 5
Error: expected a number at column 5
Error: expected a number at the end
Error: expected ) at the end
Error: expected an operator at column 3