Show HN: Parsing a Reverse Polish Expression | Hacker News Reader

Show HN: Parsing a Reverse Polish Expression

lambdaway.free.fr

41 pointsmartyalain15 comments

I've had to work with reverse polish notation on a regular basis for years yet to this day I still can't get my head around even the most basic expressions with more than a couple of operators. I've resorted to writing the required code in regular notation then using a script to reorder it to RPN; If I can't 'get it' after hundreds of hours I'm never going to 'get it'.

At the end of the 70's I bought (very expensive) a HP67 and discovered the inverse Polish notation, "1 2 +". Much later I came across LISP and discovered prefixed parenthesized expressions, {+ 1 2}, i.e. direct polish notation with parentheses. Then I thought that an HTML expression like "Hello World", written in the right way, would be better written in a LISPsish style, {b {i {u Hello World}}}, no more boring with the order of closing brackets. Finally I found that writing {b 1 2 3 4 5 6} displayed "1 2 3 4 5 6" in bold, writing {* 1 2 3 4 5 6} displayed the product, "720", and writing {b {* 1 2 3 4 5 6}} displayed "720" in bold. This made me want to write a language about these findings and its current state is here http://lambdaway.free.fr/lambdawalks/.

This is basically what jsx transpiles to, but in JavaScript. Like this: https://www.npmjs.com/package/hyperscript.

    h('b', h('i', h('u', 'Hello world')));

The big difference is that in lambdatalk you just write {b {i {u Hello world}}}. Without quoting b, i, u and Hello world. As in pure HTML!

Something that really clicked was taking physics and chemistry classes with an HP RPN calculator. You typically rearrange your equations, factor label, substitute values, and calculate: plug-and-chug. We had races and the HP's always beat the TI's and Casio's because you don't need to mess with parens. You might enter a parenthesized expression first and then work outwards.

A long time ago I was able to write on my HP67 a complete program for calculating the compression, tension and bending forces of a continuous beam on supports (for example a railway rail on sleepers), applying the equations I learned in my engineering school. In fact it was the first time I understood something about this equation. Until I translated it into code I only knew the music, not the details. That's why, when I explore a code, here the evaluation of an RPN expression, I try to keep the foundations to a minimum. The minimum minimorum is the lambda-calculus. Many code examples use the subtleties of this or that language, with the drawback of hiding the fundamental structure of the algorithm. For these reasons I prefer the "list" version to the "array" version. Basically nothing else than the three fundamental "cons, car, cdr". I am interested in your opinion.

I recently wrote a Reverse Polish Notation mode for my Ti-84+CE.

It's significantly more efficient when you have an entire page of calculations with tons of parentheses to get through. Try it out, especially if you're nostalgic for your old engineering calculator—this brings the best of both worlds.

https://github.com/arjvik/RPN-Ti84

Brings back memories ! One of the first parser you would write in any computer science class !

Any sufficiently complete explanation of RPN contains half of a poorly written Forth implementation. ;-)

Seriously, this is MUCH simpler than recursive descent compilers or lex/yacc/bison.

Add a good typing system to it, and you've got STOIC, a programming language from the 1970s.

Is this a reverse shunting-yard?

Not at all. It's essentially a simple basic play with the "cons, car, cdr" fundamental primitives given in a LISPlike language. I hope you can see it in the "calc" function's code given after the examples.

Please tlb, the website is not down. Alain Marty (marty.alain @ free.fr)

What is tlb?

tlb@ycombinator.com, a user with a high karma.

I see, thanks!

Reply on news.ycombinator.com