Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

I teach computing to 18 year olds. After having reverse polish notation explained to them one asked why is it significant enough to be in the public exam. I explained the historical significance of 70s calculators but this failed to really address the issue. So are there and concurrent practical or theorhetical applications of RPN.

share|improve this question
3  
I have been programming for almost ten years and have completed a masters in CS but I don't think I have ever seen or used reverse polish in any serious context. Are you certain it is relevant, in particular for teaching students? –  Raphael Sep 23 '12 at 14:08
    
Here is an implementation of a regular expressions engine that uses postfix notation: swtch.com/~rsc/regexp/regexp1.html#thompson. Ken Thompson used it in his first implementation also. Also, it's a popular technique for evaluating expressions at run-time (if you are building a compiler). –  saadtaame Sep 23 '12 at 15:01
    
In RPN you can write down any expression without using brackets. –  Seg Fault Sep 23 '12 at 15:09
2  
The wikipedia article on RPN covers much ground. Logic texts sometimes refer to polish notation (because it is bracket free), when they explain what can be omitted from proofs as pure "syntactic sugar". However, RPN is important because of its close relationship to stacks. Understanding stacks is important for interactive debugging, because the famous "backtrace" is normally just a stack dump. Pure functional languages are still struggling to offer something comparable to a stack dump for debugging, even so they would have much more detailed information to offer (if they could represent it). –  Thomas Klimpel Sep 23 '12 at 15:54
    
I have to retract my former comment partially. I have seen somebody use post-fix notation to string-dump trees. It was horrible to read, but easy to code. So in very specific use cases, RP may be useful, but I am not sure whether this extends to education (in general). You can use it to show that syntax is not fixed, I guess. –  Raphael Sep 23 '12 at 16:15

8 Answers 8

up vote 8 down vote accepted

In computer reverse polish notation is often used in stack-based and concatenative programming languages. It is also common in dataflow and pipeline-based systems, including Unix pipelines.
computer uses stack for evaluate the arithmetic expressions
suppose following expression
3+4
in computer stack, it pushesh the element in following order

 3
 4
 + 

i.e. top pointer points to + symbol

  +   //top pointer points here
  4
  3


when computer starts to evaluate, it first pop the operator +, here computer checks, whether it is operator or any other characters, if it is operator then understand that it has to do addition operation, then it pop the two operands for arithmetic addition, i.e. these are the next elements of the stack. that is 4 & 3
here pop order is + 4 3
in short for solving complex expressions reverse polish notation is used

If there are multiple operations, the operator is given immediately after its second operand; so the expression written "3 − 4 + 5" in conventional infix notation would be written "3 4 − 5 +"in RPN: first subtract 4 from 3, then add 5 to that.

An advantage of RPN is that it obviates the need for parentheses that are required by infix. While "3 − 4 * 5"` can also be written "3 − (4 * 5)", that means something quite different from "(3 − 4) * 5". In postfix, the former could be written "3 4 5 * −", which unambiguously means "3 (4 5 *) −" which reduces to "3 20 −"; the latter could be written "3 4 - 5 *" (or 5 3 4 - *, if you wish to keep similar formatting), which unambiguously means "(3 4 -) 5 *".

share|improve this answer
    
It's not obvious to me that RPN has anything to do with Unix pipelines. –  David Richerby 2 days ago
    
The only use for RPN in an introductory CS high-school class I would see is as an examplary notion to describe the actions performed on a stack. One further advantage of RPN (as well as prefix notion) over infix is that it doesn't require parentheses when every operator has fixed arity. This often cited advantage isn't true anymore when some opertors have multiple possible arities, finite or not. –  Franki yesterday

I've used RPN several times for rapid prototyping, e.g. of programs that have to read and interpret a user-supplied mathematical expression.

Whereas regular mathematical notation would require at least a recursive parser (think brackets, operator order, etc...), an RPN parser is basically a stack with a switch-like statement. I guess it's this combination of simplicity and expressive power that led HP to use it initially.

This is, however, usually for rapid prototyping and for convenience. I would never assume that a user can, or wants to, understand RPN.

share|improve this answer

Just to expand the previous answers/comments: don't forget that RPN is alive and on great form ... indeed it is currently used in stack machines like the Java virtual machine.

From Wikipedia: "... a stack machine implements a stack with registers. The operands of the arithmetic logic unit (ALU) are always the top two registers of the stack and the result from the ALU is stored in the top register of the stack. 'Stack machine' commonly refers to computers which use a Last-in, First-out stack to hold short-lived temporary values while executing individual program statements. The instruction set carries out most ALU actions with postfix (Reverse Polish notation) operations that work only on the expression stack, not on data registers or main memory cells ..."

The advantages/disadvantages of such approach are also described in the Wikipedia article.

share|improve this answer
    
Hm, looking at bytecode you don't see RPN per se; of course the instructions show up in "post-fix" order but that doesn't look like RPN in arithmetics, and its reason is rather clear. Register machines have to proceed in the same way: load values, then combine. –  Raphael Sep 24 '12 at 11:21

Forth and PostScript (and thus PDF which IIRC started as a binary encoding of a subset of PostScript) are more well known postfix languages that HP pocket calculator one.

Then it is also a relatively common choice as intermediate representation in simple compilers.

The simpler VM tend to have also a postfix "machine" language.

share|improve this answer
    
Incidentally, the phrase "simpler VM" includes the JVM. What's interesting about RPN is that it's the simplest useful stack machine. Stack machines are what's really interesting and useful and relevant. –  Pseudonym Jul 24 at 3:13

Your student was absolutely right. Reverse Polish Notation is not significant enough in computer science to be worth spending very limited class time on it. Instead, there are so many other wonderful conceptual ideas you could have taught, with deep intellectual ideas: stable marriage, cake-cutting, diagonalization and undecidability of the halting problem, interactive proofs and zero-knowledge proofs, etc., etc. Yes, all of those can be made accessible to 18-year-olds.

And, I do hope you praised your student for being brave enough to ask the question! They had to put themselves on a ledge to raise the issue. It speaks well for your teaching style that they felt comfortable asking you this question.

share|improve this answer

With regards to calculators: See What is RPN?

  • Benefits: RPN saves time and keystrokes. You avoid using and keeping track of parentheses while doing calculations. The process is similar to the way you learned math on paper.

  • You can see the intermediary results as you perform your computations rather than just the answer at the end. This is extremely helpful for learning the logic. Math teachers are using this feature to improve student understanding of mathematics.

  • An intermediate result allows the user to check the answer and correct errors more easily. It's easier to follow the stream of calculation. The user defines the priority of operators.

  • RPN is logical because the user first gives the number and then tells what to do with it.

share|improve this answer

Reverse Polish Notation was a good tool in my education for understanding parse trees and tree data structures in general. It's also useful if anyone has any interest at all in programming in any of the Lisp family of languages (Clojure, emacs-lisp, scheme etc..).

share|improve this answer
    
Why Lisp and Scheme ? They are full of parentheses. –  babou yesterday

As the name indicates, Reverse Polish Notation, or Direct Polish notation, are notations. They are syntax for representing something, and actually efficient syntax if you consider memory requirements. What they represent are rooted trees, which can be formulae, abstract syntax trees (AST), and other kinds of entities, that anyone has a constitutional right to consider absolutely useless.

Occasionally, one has to store such entities on file. For example there are systems that may edit or transform programs as AST, and may need to store such representations. Polish Form is convenient. It has limited readability for humans, especially for large trees, but it is a very convenient representation for machines.

Another aspect of it is that I believe the study of trees and their elementary uses and representation, as well as associated devices (stacks), to be pedagogically useful as an introduction to future studies of more advanced concepts (syntax, parsing, logic, linguistics, ...).

It has also the advantage of being conceptually rather simple, and easy to experiment on paper. It is also a nice occasion to discuss syntax and the fact that syntax is representation, and that representations may vary, while representing the same thing, and that different representations may be used depending on the need to be met (space optimization, easy modification, human readability, computer readability, ...).

But I am surprised that this question, and its answers, are considering only RPN, and none considers direct polish notation.

It is certainly excellent that students ask. But answering such question always has diverse aspects. Is it useful for the knowledge itself? I think it is. Is it useful as pedagogical exercise? I think it is, but that depends much on the intended audience, and only the teacher can assess what it is able to understand. Is it useful to understand some conceptual issues? I think it is, but again it depends on the teacher's assessment of what concepts can be explained to their students.

share|improve this answer

protected by FrankW yesterday

Thank you for your interest in this question. Because it has attracted low-quality answers, posting an answer now requires 10 reputation on this site.

Would you like to answer one of these unanswered questions instead?

Not the answer you're looking for? Browse other questions tagged or ask your own question.