Evaluating math expressions with Swift (Part 1)

From a scientific calculator to a spreadsheet app

Expression forms

Arithmetic Expressions can be written in one of three forms:

• Infix Notation
  Operators are written between the operands: 2 + 3
• Prefix Notation
  Operators are written before the operands: + 2 3
• Postfix Notation
  Operators are written after the operands: 2 3 +

Let’s take a look at the infix expression “(A + B) * C”. In this case, the infix form requires the parentheses to perform the addition before the multiplication. However, when “A + B” is written in postfix form, the addition operator is right after the operands “A B +”. The result of this operation becomes the first operand for the multiplication “A B + C *”. Same for the prefix form, it can be created easily, resulting in “* + A B C”. The order of operations within prefix and postfix expressions is completely determined by the position of the operator, so the parentheses are no longer needed.

Different expression forms

Even though infix notation is the hardest to process by computers, it represents how expressions are written and recognised by humans. That is why it is still the most common input for evaluation. However, as the infix expressions are unsuitable for a simple evaluation, they should be converted to either prefix or postfix notation.

Reverse Polish Notation (history)

Reverse Polish Notation (aka postfix notation) is called after polish logician Jan Łukasiewicz, who created the Polish 🇮🇩 (prefix) notation in 1924.

Mostly, what he developed, was a formal logic system that allowed mathematical expressions to be specified without parentheses by placing the operators before or after the operands. This logic system later became a base idea of the recursive stack, a last-in, first-out (LIFO) computer memory store.

During the 1970s and 1980s, Hewlett-Packard also used Reverse Polish Notation in all of their calculators and has continued to use it in some models into the 2020s. According to some tests, Reverse Polish Notation was discovered to help make calculations faster, as it does not need expressions to be parenthesised, so fewer operations need to be entered to perform calculations.

Reverse Polish Notation (conversion)

The conversion from infix notation to postfix notation must take into consideration the operator precedence.
There are 3 levels of precedence for 5 main binary operators as it is shown below:

Low - 0: Addition (+) and Subtraction (-)
Medium - 1: Multiplication (*) and division (/)
High - 2: Exponentiation (^)

The given number values are used for convenience, however, what should be taken into account is the difference between operators’ priorities.

Let’s take a look at the example, to understand the basics of conversion from infix to postfix:

Infix: A + B * C
Postfix (RPN): A B C * +

To convert an infix expression into a postfix one, the operands and operators (tokens) in the expression should be processed one by one. As shown above, “A B C * +” is the postfix equivalent of the “A + B * C” expression. After conversion, the operands A, B, and C should stay in their relative positions. Only the operators should change position.
In the infix expression, the first operator from left to right is “+”. However, in the postfix expression, “+” is at the end of the expression, as the next operator, “*”, has higher priority comparing to addition.

As we process the expression, the operators have to be saved somewhere until their corresponding operands are processed. The order of the saved operators should correlate with their precedence. As the addition operator comes before the multiplication operator and has lower precedence, it needs to appear after the multiplication operator is used. Because of this order, it is convenient to use a stack to keep the operators until they are needed.

This conversion algorithm is straightforward and easy to follow by a computer. It is called the shunting yard algorithm.

Shunting yard algorithm

Complexity and performance:

Worst-case performance: O(n)
Worst-case space complexity: O(n)

To perform the algorithm, we need the following:

• 1 stack for operations
• 1 queue (or string) of the output
• 1 array (or another list) of tokens

A pseudocode of the algorithm:

While there are tokens to be read:
        Read a token
        If token is an operator (x)
           While there is an operator (y) at the top of the operators stack and either (x) is left-associative and its precedence is less or equal to that of (y), or (x) is right-associative and its precedence is less than (y)
             Pop (y) from the stack
             Add (y) to output
           Push (x) to the stack
        Else if token is a left parenthesis ("(")
           Push token to the stack
        Else if token is a right parenthesis (")")
           Until the top token in the stack is left parenthesis, pop from the stack to the output
           Also pop the left parenthesis but don’t include it in the output
        Else add token to output (as it's an operand)
Pop all the remaining operators from the stack to the output

Let’s take a look at a more complicated example!

Implementing shunting yard algorithm with Swift

Note: The following implementation of the shunting yard algorithm does not contain any input validations.

To perform the correct processing of the expression, the algorithm should be able to distinguish the input tokens correctly. That’s why the input should be either in the form of a list or it can be a string where all the tokens are separated by whitespaces (so it can be converted to a list).

Operators
Operators can have either left associativity (+, -, *, /, %) or right associativity (^), so we are going to create an Enum with two possible values to represent these values.

Each operator has its value, associativity, and precedence; moreover, the operators should be compared using these values. For the operators, we are going to create a protocol with all needed properties, and a Struct conforming to this protocol.

Useful structures

As it was mentioned before, we need some prepared structures to implement the algorithm:

• Input and output — you can use any type of list you like, we will use Strings for better understanding;
• Operation stack — you can use any stack implementation you like; for this example, we are using a simple array-based stack.

We also need an array of pre-defined operators, which we’re going to use later. To simplify the algorithm, we provide an Array extension with some useful methods, so you can use them if you find them suitable.
Moreover, you can add some other operators to the array or even create your own (but don’t forget to set the correct associativity and precedence).

Algorithm

Let’s try to implement the pseudocode provided above. Comments in the code describe each step of the algorithm.
Before each token, we add whitespace to the output, so it looks nice and clean; however, it is optional, so feel free to remove it.
There is also a custom Error enum (RPNError), to highlight specific errors. You can create your own or don’t throw any errors at all.

Now it’s time to see how the algorithm works!

You can easily embed it into your iOS/MacOS app, or simply run it in the playground.

Improving the algorithm

Reverse Polish Notation works the same for functions (including trigonometry) as it does for operators. However, functions may have a different amount of arguments, so they should be taken into account. For example, in trigonometric functions, there is only a single argument (unlike operators, which generally have two).

Great news: the notions of precedence and associativity are only needed for the operators. Function tokens already use prefix notation, so they simply don’t have that problem, although it is still more convenient to put functions’ arguments inside the parentheses.

To allow the shunting yard algorithm to work with functions, slight amendments should be done to the code.

Firstly, the protocol and the Struct for the Function type should be created.

We also need an array of pre-defined functions, which we’re going to use. To simplify the algorithm, we provide an Array extension with some useful methods, so you can use them if you find them suitable.

Finally, the algorithm should be updated correspondingly.

While there are tokens to be read:
        Read a token
        If token is an operator
           ...
        If token is a function
           Push token to the stack
        Else if token is a left parenthesis
           ...
        Else if token is a right parenthesis
           ...
           if there is a function token at the top of the operator stack
           then: pop the function from the operator stack into the output queue
           ...
         Else add token to output (as it's an operand)
Pop all the remaining operators from the stack to the output

This update helps us convert more complex expressions.

Conclusion

In this part, we’ve covered a conversion from infix expressions to postfix expressions. This is a useful task from Computer Science, however, it is still not the evaluation of these expressions.

In the next part, we’re going to create an evaluation function for RPN, and also take a look at some other ways to evaluate math expressions with Swift.

Part II: https://medium.com/mobilepeople/evaluating-math-expressions-with-swift-part-2-62f3d5ea5ce8