{"id":475,"date":"2010-02-04T11:43:27","date_gmt":"2010-02-04T18:43:27","guid":{"rendered":"https:\/\/actionsnippet.com\/?p=2701"},"modified":"2010-02-04T11:43:27","modified_gmt":"2010-02-04T18:43:27","slug":"prefix-notation-lisp-style","status":"publish","type":"post","link":"https:\/\/actionsnippet.com\/?p=475","title":{"rendered":"Prefix Notation (Lisp Style)"},"content":{"rendered":"

Today’s quiz is not multiple choice. Instead, your task is to write a lisp<\/a> 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).<\/em><\/p>\n

Lisp uses prefix notation… where the operator is placed before the operands:<\/p>\n

10 * 10 <\/p>\n

becomes:<\/p>\n

* 10 10 <\/p>\n

You could think of this as a function “*” with two arguments (10, 10). In Lisp this is enclosed with parens:<\/p>\n

(* 10 10)<\/p>\n

Let’s see a few more examples:<\/p>\n

100 \/ 2 + 10<\/p>\n

becomes:<\/p>\n

(+ (\/ 100 2) 10)<\/p>\n

…
\n2 * 4 * 6 * 7<\/p>\n

becomes:<\/p>\n

(* 2 4 6 7)<\/p>\n

…<\/p>\n

(2 + 2) * (10 – 2) * 2<\/p>\n

becomes <\/p>\n

(* (+ 2 2) (- 10 2) 2)<\/p>\n

Remember, thinking “functions” really helps. The above can be though of as:<\/p>\n

multiply( add(2, 2), subtract(10 , 2), 2)<\/p>\n

You should create a function called parsePrefix() that takes a string and returns a number:<\/p>\n

Here is some code to test if your parser works properly:<\/p>\n

\r\ntrace(parsePrefix("(* 10 10)"));\r\n\r\ntrace(parsePrefix("(* 1 (+ 20 2 (* 2 7) 1) 2)"));\r\n\r\ntrace(parsePrefix("(\/ 22 7)"));\r\n\r\ntrace(parsePrefix("(+ (\/ 1 1) (\/ 1 2) (\/ 1 3) (\/ 1 4))"));\r\n\r\n\/* Should trace out:\r\n100\r\n74\r\n3.142857142857143\r\n2.083333333333333\r\n*\/\r\n<\/pre>\n
I highly recommend giving this a try, it was one of those cases where I assumed it would be much trickier than it was.<\/p>\n
I’ve posted my solution here<\/a>.<\/p>\n","protected":false},"excerpt":{"rendered":"
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: * […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[121,146],"tags":[3,14,4,149,147],"class_list":["post-475","post","type-post","status-publish","format-standard","hentry","category-math","category-quiz","tag-actionscript","tag-as3","tag-flash","tag-lisp","tag-quiz"],"_links":{"self":[{"href":"https:\/\/actionsnippet.com\/index.php?rest_route=\/wp\/v2\/posts\/475","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/actionsnippet.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/actionsnippet.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/actionsnippet.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/actionsnippet.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=475"}],"version-history":[{"count":0,"href":"https:\/\/actionsnippet.com\/index.php?rest_route=\/wp\/v2\/posts\/475\/revisions"}],"wp:attachment":[{"href":"https:\/\/actionsnippet.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=475"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/actionsnippet.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=475"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/actionsnippet.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=475"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}