The RPN calculator (see previous post) was quite easy to implement, but in order to use it, everything must be written backwards. Re-gaining infix notation would be sweet.
Luckily, it looks like Dijkstra might have us covered with his shunting-yard algorithm.
Because the * operator has precedence over the + operator. It binds more strongly, the operator with the highest precedence groups its operands, enclosing them in invisible parentheses.
Another consideration is associativity1. Generally speaking, associativity defines the grouping of sub-expressions within the same level of precedence.
Because + is associative, it can associate to the left and the right without changing the meaning or result.
Both produce the same result: 6.
However, if we try the same with -, which is non-associative, it will not produce consistent results.
Left associativity produces 0, right associativity produces 2.
Conclusion: The correct associativity in this case is left, and the result we would expect is 0.
In addition to the implicit grouping between terms and expressions there can also be explicit grouping through parentheses, that supersedes the two previous forms of grouping.
These must also be taken into account when interpreting an expression.
Enough math already. Let's talk about compilers.
A compiler takes a high-level language and translates it into some sort of low-level machine code. Mathematical expressions are a subset of many high-level programming languages.
In 1960, the dutch computer scientist Edsger Dijkstra was working on a compiler for ALGOL60. Back then he referred to it as a "translator". When faced with the challenge of precedence, he came up with an algorithm for resolving the precedence of these expressions.
This algorithm is known as the shunting-yard algorithm.
What it does is translate an expression from infix notation to something that is easier to understand for a machine: Reverse-polish notation, or postfix notation.
What this means is that we can take an expression as an input, then use shunting-yard to compile that expression into RPN, and finally use the existing RPN calculator to run it!
The translation process shows much resemblance to shunting at a three way railroad junction in the following form.
I will not describe the shunting-yard algorithm in detail here. I will however try to give a high-level description of what it does.
The process starts with a set of input tokens, an empty stack for temporarily stashing tokens and an output queue for placing the output.
Based on pre-configured precedence and associativity rules, the tokens are shunted from infix to postfix in a very memory efficient way.
Read the Wikipedia page or the original paper for a more thorough explanation.
In this case, $operators is a mapping of operator symbols to some metadata describing their precedence and associativity. A higher precedence number means higher priority.
While all of those associate to the left, there are operations that commonly associate to the right, such as exponentiation. 2 ^ 3 ^ 4 should be interpreted as (2 ^ (3 ^ 4))2.
Another common right-associative operator in programming languages is the conditional ternary operator ?:3.
Time for an actual test run of this shunting yard infix to postfix compiler!
It produces the sequence: 1 2 3 * +. This looks correct, it should evaluate to 7.
But let's feed it to the existing calculator and see what happens.
Now we have a fully-functional infix calculator that is the composition of an infix-to-postfix compiler and a postfix calculator!
You will find that it supports not only the operators +, -, *, / and %, but also parentheses that are completely removed from the resulting RPN.
In addition to that, adding support for new operators is as easy as adding an entry to $operators and an implementation to the switch statement in execute.
Shunting-yard translates infix to postfix.
Hey, look! It's a little compiler!