Thursday, October 8, 2009

Evaluate mathematical expressions using RPN(Postfix/Reverse polish notation)

Have you ever wondered how mathematical expressions are evaluated by programs such as python, bc, etc.? For example (4+3)*6/2*3^2

The answer is Reverse Polish notation(RPN), also known as Postfix notation.

The "normal" way we write mathematical expressions is know as Infix notation:
e.g: (4+3)*6/2*3^2

In RPN, 3+4 becomes 3 4 +
At first sight, this may seem a silly thing to do to put the operator after the arguments, but you'll see how it helps in evaluating mathematical expressions.
There are no brackets '(' or ')' in RPN, the expression is already in a state where the operator precedence(that is, which operation must be carried out first) has been taken into consideration.

So, what we do is convert our expression from Infix to Postfix(RPN), and then evaluate it.

Let's take a concrete example:
We have to evaluate (4+3)*6/2*3^2
The conversion to postfix becomes: 4 3 + 6 * 2 / 3 2 ^ * (conversion is done using the Shunting yard algorithm) As you'll notice there are no brackets in the RPN expression.

To evaluate this expression is very simple:
We first look for the first operator(+/*-^) in the expression (which in this case is +):
4 3 + 6 * 2 / 3 2 ^ *

Now, we look at the 2 numbers just preceding the operator (4 and 3):
4 3 + 6 * 2 / 3 2 ^ *

Then, we evaluate the expression 4+3 and we replace the whole highlighted part by the result:

7 6 * 2 / 3 2 ^ *

Now, we start over again, that is we search for the first operator (in this case *) and again, we evaluate the 2 previous numbers with the operator:

7 6 * 2 / 3 2 ^ *
becomes:
42 2 / 3 2 ^ *

42 2 / 3 2 ^ *
becomes:
21 3 2 ^ *

21 3 2 ^ *
becomes:
21 9 *

and finally,
21 9 *
becomes:
189 (... the result!!)

Here's a small C program I've made which evaluates expressions using reverse polish notation:
http://0x1337.netne.net/rpn.c

Screenshot:

It also lists the steps taken during the conversion from Infix to Postfix notation and also how the RPN expression is evaluated. Compile with:
gcc rpn.c -o rpn -lm

No comments:

Post a Comment