Capstone B: evaluation
Evaluation is the smallest part of the calculator and the one with the surprises: the tree is walked once, every number is a double, and division by zero is not an exception there. The program below evaluates six expressions, then asks a guarded evaluator the same question, and finally divides a decimal by zero to show what that type does instead.
The evaluator
Eval is one switch expression: a number is its value, a unary node negates the value of its operand, and a binary node switches again on the operator. Both children are evaluated where they are used, which is the order a reader expects and the order the tree states.
Console.WriteLine("calc 1.0");
Show("1 + 2 * 3");
Show("(1 + 2) * 3");
Show("10 / 4");
Show("1 / 0");
Show("0 / 0");
Show("-7 + 2");
foreach (var text in new[] { "10 / 4", "1 / 0", "0 / 0", "2 +" })
{
var line = TryEval(text, out var value, out var error) ? $"ok {value}" : $"error {error}";
Console.WriteLine($"{text,-8} {line}");
}
try
{
var zero = 0m;
var d = 1m / zero;
Console.WriteLine(d);
}
catch (DivideByZeroException ex)
{
Console.WriteLine($"decimal {ex.Message}");
}
static void Show(string input)
{
try
{
Console.WriteLine($"{input,-10} {Eval(Parse(Lex(input)))}");
}
catch (FormatException ex)
{
Console.WriteLine($"{input,-10} error {ex.Message}");
}
}
static bool TryEval(string text, out double value, out string error)
{
value = 0;
error = "";
try
{
value = Eval(Parse(Lex(text)));
}
catch (FormatException ex)
{
error = ex.Message;
return false;
}
if (double.IsNaN(value))
{
error = "not a number";
return false;
}
if (double.IsInfinity(value))
{
error = "division by zero";
return false;
}
return true;
}
static double Eval(Node node) => node switch
{
Number number => number.Value,
Unary unary => -Eval(unary.Operand),
Binary binary => binary.Op switch
{
'+' => Eval(binary.Left) + Eval(binary.Right),
'-' => Eval(binary.Left) - Eval(binary.Right),
'*' => Eval(binary.Left) * Eval(binary.Right),
_ => Eval(binary.Left) / Eval(binary.Right),
},
_ => throw new FormatException("unknown node"),
};
static List<Token> Lex(string text)
{
var tokens = new List<Token>();
var i = 0;
while (i < text.Length)
{
var c = text[i];
if (char.IsWhiteSpace(c))
{
i++;
continue;
}
if (char.IsDigit(c) || c == '.')
{
var start = i;
while (i < text.Length && (char.IsDigit(text[i]) || text[i] == '.'))
{
i++;
}
var number = text[start..i];
var value = double.Parse(number, System.Globalization.CultureInfo.InvariantCulture);
tokens.Add(new Token(TokenKind.Number, value, start, number));
continue;
}
if (c is '+' or '-' or '*' or '/' or '(' or ')')
{
tokens.Add(new Token(TokenKind.Operator, 0, i, c.ToString()));
i++;
continue;
}
throw new FormatException($"unexpected '{c}' at {i}");
}
tokens.Add(new Token(TokenKind.End, 0, text.Length, "end"));
return tokens;
}
static Node Parse(List<Token> tokens) => Parser.Parse(tokens);
enum TokenKind
{
Number,
Operator,
End,
}
record Token(TokenKind Kind, double Value, int Position, string Text);
abstract record Node;
sealed record Number(double Value) : Node;
sealed record Unary(char Op, Node Operand) : Node;
sealed record Binary(char Op, Node Left, Node Right) : Node;
sealed class Parser
{
private readonly List<Token> _tokens;
private int _index;
private Parser(List<Token> tokens) => _tokens = tokens;
public static Node Parse(List<Token> tokens) => new Parser(tokens).Expression();
private Token Current => _tokens[_index];
private Node Expression()
{
var left = Term();
while (Current.Kind == TokenKind.Operator && Current.Text is "+" or "-")
{
var op = Current.Text[0];
_index++;
left = new Binary(op, left, Term());
}
return left;
}
private Node Term()
{
var left = Factor();
while (Current.Kind == TokenKind.Operator && Current.Text is "*" or "/")
{
var op = Current.Text[0];
_index++;
left = new Binary(op, left, Factor());
}
return left;
}
private Node Factor()
{
var token = Current;
switch (token.Kind)
{
case TokenKind.Number:
_index++;
return new Number(token.Value);
case TokenKind.Operator when token.Text == "-":
_index++;
return new Unary('-', Factor());
case TokenKind.Operator when token.Text == "(":
_index++;
var inner = Expression();
Expect(")");
return inner;
default:
throw new FormatException($"expected a number at {token.Position}");
}
}
private void Expect(string text)
{
if (Current.Kind != TokenKind.Operator || Current.Text != text)
{
throw new FormatException($"expected '{text}' at {Current.Position}");
}
_index++;
}
}
dotnet run
echo "status: $?"
calc 1.0
1 + 2 * 3 7
(1 + 2) * 3 9
10 / 4 2.5
1 / 0 Infinity
0 / 0 NaN
-7 + 2 -5
10 / 4 ok 2.5
1 / 0 error division by zero
0 / 0 error not a number
2 + error expected a number at 3
decimal Attempted to divide by zero.
status: 0
The first six lines are the values. 10 / 4 is 2.5 and not 2, because the values are double and the division is a floating point division; an integer calculator would need int and a decision about the remainder.
Division by zero
In floating point arithmetic, dividing by zero is a defined operation: 1 / 0 is positive infinity and 0 / 0 is not a number. Neither throws, and both answers are printed by the plain evaluator, because both are valid double values. That is why a calculator cannot report a division by zero by waiting for an exception: there is none.
- double.IsInfinity(value) answers true for both infinities, and the guarded evaluator uses it as the mark of a division by zero.
- double.IsNaN(value) answers true for the result of 0 / 0, which the guarded evaluator reports with its own message.
- Infinity propagates: any later addition or multiplication keeps it, so the check is done once, at the end, and not at every operator.
decimal is not double
The same division in decimal is different in both directions. 1m / 0m is refused by the compiler, with the real line error CS0020: Division by constant zero, because both operands are constants and the compiler refuses to write an infinity into a type that has none. With a variable the program compiles and the division throws, which is the last line the program prints:
decimal Attempted to divide by zero.
The message is the one of DivideByZeroException, which the catch of the program prints. A program that keeps money in decimal can therefore rely on an exception for a division by zero, while a program that keeps measurements in double must check for an infinity.
A result the caller can check
TryEval is the shape a calculator exposes: a bool for success, an out value and an out message. It catches the FormatException of the parser, then refuses NaN and an infinity, and each refusal has its own words. The four lines under the values are its answers:
- 10 / 4 ok 2.5 is a success, and the value is printed.
- 1 / 0 error division by zero and 0 / 0 error not a number are the two guards.
- 2 + error expected a number at 3 is the parser speaking, caught and passed on, with the position in its message.
The next lesson gives those messages a place on the line: the position becomes a property of a custom exception, and the program draws a caret under the character that failed.
Exercises
- Add an evaluator that counts how many times each operator was used and print the counts for one expression.
- Add a guard for a division by a very small number, where the result is finite but larger than the largest representable integer.
- Change the evaluator to decimal and find out which inputs now throw.
- Return a record EvalResult(bool Ok, double Value, string Error) instead of the two out parameters and compare the two call shapes.
Questions
A new set of questions in a new order every time. Choose one answer for each, then check.
-
What is 1 / 0 for a double?
Answer
Positive infinity, with no exception
The measured line reads 1 / 0 Infinity.
-
What is 0 / 0 for a double?
Answer
NaN, which is not a number
The guarded evaluator reports it as not a number.
-
What does this program print?
Console.WriteLine(double.IsInfinity(1.0 / 0.0));Answer
True
The division gives an infinity, which the check recognises.
-
What does 1m / 0m do?
Answer
It does not compile: error CS0020, division by constant zero
Both operands are constants and decimal has no infinity.
-
What does this program print?
var zero = 0m; try { Console.WriteLine(1m / zero); } catch (DivideByZeroException ex) { Console.WriteLine(ex.Message); }Answer
Attempted to divide by zero.
A variable hides the zero from the compiler, so the division throws.
-
Why does TryEval check for NaN and for an infinity after evaluating?
Answer
Neither is an exception, so the check has to be explicit
Floating point division by zero returns a value and does not throw.
-
What does this program print?
Console.WriteLine(double.NaN == double.NaN);Answer
False
NaN is not equal to anything, itself included, which is why IsNaN exists.
-
What does 10 / 4 print for two doubles?
Answer
2.5
The measured line reads 2.5, because the values are floating point.
-
What does this program print?
Console.WriteLine(-(2 + 3) * 4);Answer
-20
The sign applies to the sum and the multiplication comes after.
-
Which error string does TryEval give for 2 + ?
Answer
expected a number at 3
The parser message is passed on unchanged, and the measured line shows it.
The code on this page was built with the .NET SDK 10.0.303 and run on Alpine Linux 3.24.3 (x86_64) in a Docker container.
Article author: Arthur Isaev