Using the right algorithm

Using the correct algorithm can make a difference between a happy afternoon coding and a mental breakdown. This applies to other aspects of life… The baker needs to apply the right mix and technique for the bread; unless you want to make your life miserable you need the correct sequence of steps to change the motorbike oil; the list goes on and on. ​

This analogy is especially true for programming problems. I will illustrate this concept by means of a simple example problem:

Write a function “evaluate” that accepts an infix expression “expr” as a string and returns the expression evaluated as a double.

Function signature:

• evaluate(expr: String): Double

Examples:

• ​evaluate("1 + 1") returns 2
• evaluate("1 + 3 * 3 + 1") returns 11
• evaluate("2 + ( 5 * 454 ) / 44 - 231") returns -177.4090909090909

Limitations:

• To make it a bit easier, each operator and operand are always separated by a space
• Operands are integers
• Expression may contain parenthesis
• Assume that expression is always correct (no need for validations)
• Valid operators are + - * /
• Precedence is brackets, division, multiplication, addition, subtraction.

​

Right… So there are now two kinds of people reading this post. The first kind most likely met this problem before maybe during their university course and know the general idea of the algorithm. The second type is thinking “How hard can this be?!”. I dare the second kind of readers to try it out without googling for a solution or using libraries. Come on, stop reading this post and come back once you’re finished. I know you want to.

You’re back? How did it go? How many grey hairs have you grown? Is Trump still President?

If you belong to the first kind and you’ve seen the solution before, you’ll be able to solve it in about an hour or two maybe after brushing up on some specifics on the algorithm. For the rest, I will now show you the solution using Scala, because Scala is awesome.

First some definitions. Infix refers to the way we normally write expressions. I.e. when the operator is the middle between two operands.  
Infix: operand1 operator operand2
Examples: 

• 1 + 2
• (4 + 5) * 3 + 3

Postfix is another way to represent an expression. In postfix the operator is after the operands. Postfix expressions don’t support (or need) parentheses.Postfix: operand1 operand2 operator
Examples:

• 1 2 +
• 4 5 + 3 * 3 +

Although it doesn’t feel like it, it’s way easier to evaluate a postfix expression. When evaluating infix expressions, you need to take care to evaluate it in the right sequence, doing the parenthesis first, then division and so on. Using postfix the natural sequence of the expression dictates the precedence.

A postfix is evaluated by traversing the expression left to right and whenever you meet an operator you replace the operator and the two previous operands with the result. For example consider the expression 1 + 2 * 3  + 4 which translates and evaluates to:

• 1 2 3 * + 4 +
• 1 6 + 4 +
• 7 4 +
• 11

The algorithm for evaluating a postfix expression is pretty simple:

• Initialise an empty stack
• foreach(item C in expression)
  • If C is an operand, Push C on stack
  • Else
    • Pop stack twice and assign to vars A and B
    • var X = B operator(C) A
    • Push X on stack
• Pop stack to get result

Writing the above in Scala in a more functional way leads to something like:

Notice how easy it is to implement this using foldLeft and Scala’s pattern matching. The foldLeft is initialized with an empty list representing the stack. Matching is then done on the two top stack elements and operator type. The result is found and pushed on top of the stack. At the end we simply read the top of the stack to get the final result.

Ok, so now we have a way to evaluate a postfix expression. All we need now is a way to convert infix to postfix and we are done. The algorithm is also quite simple:

• Initialise an empty stack
• Initialise an empty list for final postfix expression
• foreach(item C in expression)
  • If C is an operand, add C to end of list
  • Else if C is "(" push C on stack
  • Else if C is ")" 
    • pop stack until value is "(”
    • append values to the end of list
  • Else if C is an operator
    • pop stack while value has higher or equal precedence to C
    • append values to end of list
    • push C on stack
• Pop all values on stack and put them at the end of list

Easy right? Here is the Scala equivalent:

Again, notice the versatility of pattern matching in Scala. In the above algorithm we start the foldleft with an empty postFix list and an empty stack. We then match on the input infix operands and operators and perform the required logic in each case. The “span” function was used here to split the stack in two. This can be described as popping the stack until the given condition is no longer met.
For example:

Would keep on removing items from the top of the stack until the left parenthesis is found:

( List(*, +), List((, -, +) )

All that is left now is to call the two functions in sequence:

There… Job done. This problem is a good example that transforming the input into a different encoding and solving turns out to be more simple than trying to evaluate the expression using the original infix notation. For reference the above algorithm is a simplified version of the “Shunting-yard” algorithm by Edsger Dijkstra.

Make sure you run your motorbike for a few minutes before changing the oil. This warms up the oil and helps it flow when draining.