Tag Archives: Lisp

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.

Posted in Math, Quiz | Also tagged , , , | 4 Comments