(Originally published April 2011.)
When it comes to notation, we’re used to seeing things in the form of x+y, 1*1, etc. This is an austere contrast to what, as programmers, we’re used to working with: functions. In most languages, for example, we might invoke a function we’ve created to perform addition in some line resembling Add(a,b). Notice the difference yet?
AN INTRODUCTION TO NOTATION DIFFERENCES
In everyday mathematics, we typically represent equations in a form called “infix notation”, a notation where the operator comes between its operands. An addition function in a language based on infix notation might be invoked as 1 add 2. If this looks odd to you, it is: few languages support this (haskell comes to mind), and even in those which do, few people use it. Infix notation is fundamentally difficult for a computer to use — in order to perform a function on arguments the computer, at some level, needs to push the arguments into a stack in memory before calling a function — and so whenever we write a mathematical equation in a programming language the computer is at some point converting this into a notation with the arguments and the function as two discrete groups.
Given that infix notation has the operator in the arguments, the other two notations are obvious: prefix notation — where the operator prefixes the arguments — and postfix notation — where the operator follows its operands. You may be more familiar with these two notations as Polish Notation and Reverse Polish Notation (or rpn), respectively. The equation a+b*x in infix notation would be represented as (+a(*bx)) in prefix notation, and (a(bx*)+) in postfix notation.
AUTOMATING THE CONVERSION
Because each standard mathematical operator (+, -, *, /, ^, %) has exactly two operands (we say that they have “arity” 2, more commonly known as binary), we can consider an equation as a binary abstract syntax tree. A simple equation, a+b, would be represented as such:
Similarly, 2+(3x/5)*(4+(3/2))-1 would be:
Converting an equation to this form is easy in principal. Each operator applies to exactly two values: the one before and the one after. So, for a simple left-to-right mathematical system, we can think of the steps to convert to a tree as such:
Read the first operand, and store it as the left child of a new node n1.
Read the operator, and store it as the root of n1
Read the second operand, and store it as the right child of n1
Store this new node as the left child of the node n2
Repeat steps 2 and 3 for this new node.
Repeat 2-4 until you run out of equation to parse.
Here’s an example of this in action:
As we all know, math isn’t read simply left-to-right — some terms are evaluated before others in an order defined by the precedence rule. In order to parse infix, we need to consider the problem in order of Brackets, Exponents, Division/Multiplication, and Addition/Subtraction. This rather complicates things.
The solution is something known as the shunting-yard algorythm, and it’s unlikely that I could do a better job explaining it than the linked Wikipedia page. Without going into how it works, what we need to do is push the operators onto a stack, s_oper, as we read them. Likewise, we push our operands onto a stack we’ll call s_node.
Whenever we encounter an operator which has a equal or lesser precedence than the top operator on s_oper, we pop the previous operator off the stack, and use it to generate a node with the previous two nodes from s_node. This new node then replaces these last two nodes in s_node. When we’ve processed the entire equation, we pop each remaining element off s_oper and use it to form a node from the last two nodes on s_node.
For any well-formed equation we’ll end up with exactly one node in s_node which contains the entire tree.
Here’s an example of how this works:
The only remaining piece we haven’t dealt with is brackets. You can think of the equation contained in the brackets as a separate equation. You can simply deal with this recursively, or simply pop s_oper to form nodes until you reach the first open-bracket in s_oper.
FROM A TREE TO A FORM
Finally, we can go from a tree to a mathematical equation of any form recursively. To print out any given node:
In prefix: print the operator, then the left child, then the right child
In infix: print the left child, then the operator, then the right child
In postfix: print the left child, then the right child, then the operator
Finally, as the base-case for this recursive function, when we reach a node which is only a variable or number we print that result.
This post was inspired by an interview question at JustinTV, which contains a second part: to reduce the equation as much as possible. This is actually quite easy now that our equation is represented by a tree. I’ll explore the methods of reducing a function in a later post.