The Museum of HP Calculators

HP Forum Archive 08

[ Return to Index | Top of Index ]

RPN
Message #1 Posted by fred on 30 Apr 2002, 2:47 a.m.

Hello !!! I'm searching for an algorithm of transcription from algebric to Reverse Polish Notation (Visual Basic or Pseudo code). Someone can help me , please ?

      
Re: RPN
Message #2 Posted by Vieira, Luiz C. (Brazil) on 30 Apr 2002, 7:12 a.m.,
in response to message #1 by fred

Hi;

about four years ago I worked with something realated to this, say, a syntax error-checking for algebraic expressions. It was written in (gasp!) C++, but there is something in ML or CLEAN (I worked only in C++). I prefer C++, but must admit ML and CLEAN final codes are faster and lighter.

Anyway, I'll have to look for them in my (gasp!-II) nine HD's (>150 GBytes)! Time to seek for lost stuff...

Cheers.

      
Re: RPN
Message #3 Posted by Holger Veit (DE) on 30 Apr 2002, 11:04 a.m.,
in response to message #1 by fred

Parse the algebraic expression into a tree - easily done with a parser generator like YACC - and traverse the tree in postfix order. Stuff one usually writes down from scratch in half an hour. Basic stuff from almost any algorithmic CS course, usually asked for as a homework.

      
Re: RPN
Message #4 Posted by Keith on 2 May 2002, 12:02 p.m.,
in response to message #1 by fred

The rules below are a rewrite of those given in old Burroughs large systems manuals. They have worked for me in both Algol and Cobol. I do not know what "simplified" means.

Burroughs large computer systems (starting in the early 1960's) and their Unisys successors are true stack machines. All arithmetic (and other) operations are done on the top of the stack. RPN is native to the machines.

The system manuals used to (they no longer do) describe the process for converting to RPN because this approach was novel to most users. Since a user cannot program the stack directly (no assembler), but only via compilers, this process was just background information for most users.

Simplified Rules for the Generation of a Polish String:

Tokens are pulled from the algebraic expression from left to right.

Tokens are placed in the Polish string from left to right.

The delimiter list is a last in, first out stack.

Apply the following rules until the end of the algebraic expression is reached.

1. Pull a token from the algebraic expression.

2. If the token is a variable or a constant, then place the token in the Polish string and go to step 1.

3. If the token is a "(", then place it in the delimiter list and go to step 1.

4. If the token is an arithmetic or boolean operator and the last-entered delimiter list token is an operator of lower priority, or a "(", or the delimiter list is empty, then place the token in the delimiter list and go to step 1.

5. If the token is an arithmetic or boolean operator and the last-entered delimiter list token is an operator of equal or greater priority, then remove the token from the delimiter list and place it in the Polish string. Continuing to consider the operator token from the algebraic expression, go to step 4.

6. If the token is a ")", then remove tokens from the delimiter list and place them in the Polish expression until the matching "(" in the delimiter list is encountered. Discard the "(" from the delimiter list and the ")". Go to step 1.

If there are any tokens remaining in the delimiter list, remove the tokens from the delimiter list and place them in the Polish string.

The Polish expression is complete.


[ Return to Index | Top of Index ]

Go back to the main exhibit hall