(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:

## BEDMAS

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

**. 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_node***and use it to form a node from the last two nodes on**

*s_oper***.**

*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:

## BRACKETS

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.

## RELATED WORK

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.