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.
|