View Source: ReversePolish - Waikato Linux Users Group

Edit PageHistory Diff Info LikePages

Styles of syntax used for writing expressions or tree-structured data:


!!!Infix

In infix notation you write the operator between the arguments:

 c - (5 + a + x) * b

Infix notation is the usual. It needs precedence rules and/or brackets to make the order of operations unambiguous. Polish and Reverse Polish don't have that problem, providing the number arguments to each operator is fixed.

!!!Reverse Polish

In Reverse Polish, or __postfix__, notation you write the operator after the arguments.

 c 5 a + x +  b *  -

It's very easy to interpret expressions in this notation, you need just a single stack to place intermediate values on, this is why [Forth] and PostScript (which was based on Forth?) use it.

!!!Polish

In Polish, or __prefix__, notation you write the operator before the arguments.

 - c * + 5 + a x b

Polish notation is called that because a famous Polish mathematician first used it for Boolean algebra, and nobody can either remember or pronounce his name without looking it up first. (''You'' go look it up.)

!!!S-expressions

In S-expression, or [LISP], notation you write the operator before the arguments, enclosed in brackets:

 (- c (* (+ 5 a x) b))

[LISP] operators take any number of arguments so [LISP] expressions need brackets to associate arguments with operators.

It's very easy to parse this notation into tree structures, which is why [LISP] uses it.

!!!XML

In XML notation you bracket the arguments with the operator:

 <subtract>
     <variable name="c"/>
     <multiply>
         <add>
             <constant value="5"/>
             <variable name="a"/>
             <variable name="x"/>
         </add>
         <variable name="b"/>
     </multiply>
 </subtract>

Whoever came up with this had good intentions, I'm sure...

One page links to ReversePolish:

Forth

Last edited on Saturday, November 1, 2003 3:22:25 pm by JohnMcPherson

Edit PageHistory Diff Info LikePages