# Prefix Notation (Lisp Style)

Today's quiz is not multiple choice. Instead, your task is to write a lisp style math parser. This may sound tricky, but it's surprisingly simple. (well... not simple exactly, it's just simple compared to what one might assume).

Lisp uses prefix notation... where the operator is placed before the operands:

10 * 10

becomes:

* 10 10

You could think of this as a function "*" with two arguments (10, 10). In Lisp this is enclosed with parens:

(* 10 10)

Let's see a few more examples:

100 / 2 + 10

becomes:

(+ (/ 100 2) 10)

...
2 * 4 * 6 * 7

becomes:

(* 2 4 6 7)

...

(2 + 2) * (10 - 2) * 2

becomes

(* (+ 2 2) (- 10 2) 2)

Remember, thinking "functions" really helps. The above can be though of as:

multiply( add(2, 2), subtract(10 , 2), 2)

You should create a function called parsePrefix() that takes a string and returns a number:

Here is some code to test if your parser works properly:

Actionscript:
1. trace(parsePrefix("(* 10 10)"));
2.
3. trace(parsePrefix("(* 1 (+ 20 2 (* 2 7) 1) 2)"));
4.
5. trace(parsePrefix("(/ 22 7)"));
6.
7. trace(parsePrefix("(+ (/ 1 1) (/ 1 2) (/ 1 3) (/ 1 4))"));
8.
9. /* Should trace out:
10. 100
11. 74
12. 3.142857142857143
13. 2.083333333333333
14. */

I highly recommend giving this a try, it was one of those cases where I assumed it would be much trickier than it was.

I've posted my solution here.

1. jax
Posted February 13, 2010 at 3:53 pm | Permalink

I know this isn’t the typical reply for your post, but is it possible to use isSensor option on an object with quickbox2d, because I want only to see if two object’s overlap, I don’t want them to cause any reaction, just to see if they are overlaping??

2. Ben J
Posted February 16, 2010 at 9:29 am | Permalink

I believe it’s called reverse Polish notation. They used to make a lot of calculators that way.

3. Posted March 13, 2010 at 12:36 am | Permalink

for some reason this post appears in http://actionsnippet.com/?cat=113 (quickbox)

4. Posted March 13, 2010 at 9:49 am | Permalink

thanks for pointing that out….