Making A Calculator... The Harder Way.

Complexity: Intermediate

Foreword

This was created as part of an "Introduction to Programming" course I did for university. Since I have been programming for a while, I decided to take it a bit further and made something a bit more interesting to me.

Premise

I am working on creating a game to help people learn coding and problem-solving. For this, I need a simple scripting language that can interface with my game. Unfortunately, none of the programming languages I can use for this fit my requirements, which means I need to make my own. However, that is a bit complex for Introduction To Programming (and I intend on performing some bodges that I don't want people to judge), so I will do something similar, but less complicated and with real-world usability.

The assignment brief gave an example of creating a scientific calculator, I have determined that creating a stack-based calculator is very similar to a simple stack-based programming language, and also less complicated, making it much more appropriate for this unit, so I will make that to learn the basic principles.

It is important to note that some code in this article will be simplified to hopefully make it easier to understand.

The Basics

Before getting started on anything, I set out code style guidelines for the project, giving me rules to work on when laying out and writing code. This is helpful since I am mainly a C# developer and I find that rules reduce confusion.

I also set up a git repository on GitHub to allow me to back up my code and work on it on different machines.

After that, I created a basic wrapper around input and output, simplifying the process of reading user input (especially numbers) and allowing me to write coloured text to the console, for instance.

public static void example()
{
    // Display a message and then read console input
    String name = Input.readLine("What is your name? ");

    Output.setConsoleColour(ConsoleColour.Blue);

    // Output blue text to the console
    Output.print("Hello, " + name + "!");
}

Using this, I created a simple text-based menu system using inheritance that allows the user to choose from a few options to interact with the calculator.

@InteractiveMenu("Display all available operators")
public class MenuDisplayOperators extends Menu
{
    // Handles display and user interaction
    public void execute()
    {
        Output.printSuccess("This is an example page!");
    }
}

Postfix Notation

Also known as "Reverse Polish Notation", postfix notation is a format for representing expressions where an operator (the instruction) is written after its operands (the data) ^[1].

7 2 add   // (7 + 2)

This is useful as it is very easy to parse using a stack (a data structure where the last item input is the first item output), as the operands can be loaded onto the stack, and then popped off and executed when an instruction is reached.
This approach is especially useful as it does not need brackets to establish the order of operations due to the way items are allocated onto the stack.

6 8 1 subtract multiply   // 6 * (8 - 1)

Calculating...

Using postfix notation, it is quite easy to create a simple calculator ^[2].

public static Double evaluate(String[] input)
{
    var stack = new Stack<Double>();
    for (var token : input)
    {
        var num = tryConvertStringToDouble(token);
        if (num != null)
        {
            // Token is a Double
            stack.push(num);
        }
        else if (isFunction(token))
        {
            // Token is a function
            var parameter = stack.pop();
            runFunction(token, parameter);
        }
        else
        {
            // Token should be an operator
            var rightValue = stack.pop();
            var leftValue = stack.pop();
            runOperator(token, leftValue, rightValue);
        }
    }

    return stack.pop();
}

By iterating through the input expression, we can perform actions based on the type of a given element in the input. A stack-based calculator is relatively simple, only requiring actions relating to numbers (values), operators, and functions.

Numbers are consumed by functions and operators, so they are added to the stack to be popped off as needed.
The majority of non-complex functions used by calculators only take one parameter, so that is how I have designed the architecture for my functions, although it would theoretically not be much harder to have multiple parameters.

To run a function, I first retrieve the parameter from the stack, then I pass it into a method called runFunction along with the identifier, where the identifier is matched up with a method and executed, with the output being pushed onto the stack.

Operators work very similarly to functions, except that they need two parameters, one for either side of the operator. The result of that operation is also placed back onto the stack.

Parsing

Requiring the user to enter their expressions in postfix notation is not very user-friendly; we want the user to use this calculator exactly like any other normal calculator, entering their expressions in a normal manner.

To allow this, we need to parse the data, turning our input into a structured format that our calculator can understand.

Preprocessing

Unfortunately, users don't like putting data into programs the way that programmers often intend them to. To combat this, it is common to preprocess the user's input to try and remove or adjust for anything weird that the user might have done (within reason).
In my program, I use whitespace as a separator for instructions, therefore it is important that instructions do not accidentally get combined when whitespace is missing. To fix this, I wrote a small function that intelligently adds a space if two tokens need splitting. After that, I trim any extraneous whitespace and convert the input string to lowercase so it is easier to work with.

Tokens

To have more structured data, I created a custom "Token" data type.

public record Token(TokenType type, V value) { }

This is a simple immutable piece of data that contains basic information about an instruction, such as the type (either a literal, an operator, or a function) and the value. In the program (for now), the value can be a Double (a number) or a String (a function or operator), so it was important to be able to use one type that was able to represent both of these. I did that by using a generic, which is a flexible type that can work over a variety of data types.

The Shunting Yard Algorithm

At the moment, we still have an infix notation expression that our calculator is not able to understand. We need to convert it into a series of tokens in postfix notation so it can be correctly executed.

To parse the input string, there are multiple popular algorithms, each with advantages and disadvantages. However, if you research these for too long, you end up knowing far too much about programming languages from the 1960s ^[3].

From this, I determined that the two most popular ways to parse an expression are with recursive descent parsing ^[4] or the Shunting Yard algorithm ^[5].

The main advantages to recursive descent parsing are that it is much more flexible and you can create more complex logic as a result. However, the Shunting Yard algorithm is considered to have better performance, and it is often described as being less complex to implement. Since this is only a simple calculator, I determined that the Shunting Yard algorithm would be more appropriate to use.

The Shunting Yard algorithm is based on two main data structures, one of which is the token queue, which is used to construct the final postfix output of the algorithm - any numbers go straight onto it. The other is the operator stack, which keeps track of functions and operators in reverse order so they can be put onto the queue later in a valid order.

With this knowledge, here is a slightly simplified version of my implementation:

private static ArrayList<Token<?>> tokens = new ArrayList<>();
private static Stack<String> operators = new Stack<>();

public static ArrayList<Token<?>> tokenizeExpression(String[] input)
{
    for (var value : input)
    {
        // We don't want to add empty values
        if (value.isEmpty())
            continue;

        // If the value is a number, add it to the token queue
        var parsedDouble = tryParseDouble(value);
        if (parsedDouble != null)
            tokens.add(new Token<>(TokenType.Literal, parsedDouble));

        // If it is a opening bracket, add it to the operator stack
        else if (value.equals("("))
            operators.push(value);

        // Go back and add operators inside the brackets ("closing" them)
        else if (value.equals(")"))
        {
            while (!operators.isEmpty())
            {
                if (operators.peek().equals("("))
                    break;

                popOperatorToTokenQueue();
            }
        }

        // If it is a function, add it to the operator queue
        else if (isFunction(value))
            operators.push(value);

        // Hope that the expression is valid and add it as an operator
        else
        {
            // Add previous operators (inside this scope)
            while (!operators.empty() && !operators.peek().equals("("))
                popOperatorToTokenQueue();

            operators.push(value);
        }
    }

    // Add the rest of the operators to the queue
    while (!operators.isEmpty())
        popOperatorToTokenQueue();

    return tokens;
}

There are some issues with my implementation, for instance, it does not support functions with multiple parameters and it is relatively hard to extend. However, none of these issues are significant when creating a simple calculator.

Now, I can connect the tokenizer with the main calculator execution logic to evaluate expressions.

((4.3 + 5.7) / (9 - 5)) + floor(3.4)     // 5.5 - It works!

Running functions

Even though the calculator worked, it was inconvenient to add more functions or operators to it, because that was based on a very large switch statement that matched the function's name to the actual function in my Java code, which was not ideal.

To get around this, I used reflection, which is when a program inspects itself ^[6]. To do this, I used an annotation, which is like a tag the program can use to identify methods or fields inside itself.

@Retention(RetentionPolicy.RUNTIME)
@Target(ElementType.METHOD)
public @interface Function
{
    public String value();
}

After putting this annotation on the calculator functions, I used reflection to get a list of all of the methods with that tag on.

private static final HashMap<String, Method> functions = new HashMap<>();
public static void initializeFunctions()
{
    // Add all valid functions to the map
    for (Method method : Functions.class.getDeclaredMethods())
    {
        if (method.isAnnotationPresent(Function.class))
        {
            functions.put(
                method.getAnnotation(Function.class).value(), method);
        }
    }
}

From there, I could execute a user-requested function by searching through that list for the name of the function and invoking the method. With functions, I allowed the user to call them using the name of the method or a custom name specified in the annotation as I thought it made the calculator more user-friendly.

public static void evaluateFunction(String name) throws ExecutionException
{
    for (Map.Entry<String, Method> entry : functions.entrySet())
    {
        // Run the function if the user puts in either name
        if (name.equals(entry.getValue().getName()) ||
            name.equals(entry.getKey()))
        {
            entry.getValue().invoke(null);
        }
    }
}

I also repeated this process in a very similar manner with operators, as it made it much easier to work with them.

Testing

Aside from manually testing the calculator by evaluating and checking a wide variety of expressions, I also used the JUnit testing framework to design unit tests for the calculator. I ended up creating over 50 tests to ensure that my program worked correctly.

It was important to test each part of the program separately to ensure I could identify exactly where something could have potentially broken, so I made a wide suite of tests.

First, I created tests for the tokenizer, which is the part of my program responsible for parsing the expression input by the user into tokens for the evaluator to use later.

@Test
public void tokenizeBasicExpression()
{
    // (1 + 2)
    var expectedResult = new ArrayList<Token<?>>();
    expectedResult.add(new Token<>(TokenType.Literal, 1.0));
    expectedResult.add(new Token<>(TokenType.Literal, 2.0));
    expectedResult.add(new Token<>(TokenType.Operator, "+"));

    var result = Tokenizer.tokenizeExpression("(1 + 2)");

    assert expectedResult.equals(result);
}

From there, I created some tests for the evaluator, which is responsible for executing the tokenized list of instructions.

@Test
public void evaluateBasic() throws TokenException, ExecutionException
{
    // (1 + 2)
    var expectedResult = 1.0 + 2.0;

    var input = new ArrayList<Token<?>>();
    input.add(new Token<>(TokenType.Literal, 1.0));
    input.add(new Token<>(TokenType.Literal, 2.0));
    input.add(new Token<>(TokenType.Operator, "+"));

    var result = Evaluator.evaluate(input);

    assert expectedResult == result;
}

After that, I added a series of combined tests that ensure both of those work together correctly.

@Test
public void calculateExecutionErrorRPN()
{
    // Check that invalid input throws an error.
    var input = Tokenizer.tokenizeReversePolishNotation("Taste The Pain");

    try
    {
        Evaluator.evaluate(input);
    }
    catch (Exception ex)
    {
        assert ex instanceof ExecutionException;
        return;
    }

    // If we don't get an error, something is VERY wrong.
    assert false;
}

Conclusion

I am happy with this project and have ported this code over to C#, which is much more flexible and better for creating a system like this. I have integrated it with my custom game engine and added support for more data types and variables, and I am implementing user-defined functions.

References