| PLACE |
| spec |
| solutions |
An RPN calculator as described here should not be very hard to implement. Still, arriving at a particular solution in a programming language requires making some algorithmic decisions on the directions to take. There are a number of possibilities, although not all of them are really available in all languages. One might be surprised (I was, at some point) of the variety of ways to solve such a seemingly simple problem.
I am going to list the design options that seem worth mentioning to me. The implementation pages show many examples of actually making use of these options.
An RPN expression is a string with a formally defined structure. Therefore, an immediately obvious option is to employ a parser generator instead of implementing an expression parser by directly programming it. This approach requires constructing a formal grammar for RPN expressions as well as a language tool that understands it. That tool will have then to either generate the respective code in some programming language, or run the parser itself. Lex and yacc and TXL exemplify these two possible ways: while lex and yacc generate a C code that serves as the actual RPN expression evaluator, the TXL script is itself run as an RPN calculator.
Even when reading and parsing are not fully automated by means of a grammar interpreter, parts of this work can still be done ‘for free’ for us by the language in which the calculator is being implemented. For example, splitting the input into lines (as well as reading the input in the first place) can be implicit. Obtaining individual tokens can also be implicit. awk, for example, does both of these, maintaining special variables to provide access to the currently read line and the tokens of which it consists. On the other hand, in Logo one has to execute a line reading command explicitly, but the output of such a command is a list of tokens, i.e. tokenizing a line is an implicit consequence of reading. Many languages provide a command or a library routine for splitting up a string into tokens.
A major choice to be made in a program whose input is line-oriented is whether to read a whole line and then process it or read and process a part of a line at a time. The latter option is more economical in the sense that it does not require accepting arbitrarily long input, while the former opens a number of algorithmic possibilities for implementing an expression evaluator that are not available in the case of incremental reading. With an incremental reading and evaluating, a syntax error found in an RPN expression will save processing the remainder of a line where the error occurs (the line will still have to be read up to its end before moving to the next one, but nothing needs to be stored).
The way we defined an RPN expression suggests a recursive evaluation. Unless the expression consists of a single number, its last token must be an operator, the evaluation of which produces that expressions's result. To evaluate an operator one must first obtain the values of its arguments – two consecutive sub-expressions – and this is where the recursion steps in.
Note that it makes sense to evaluate the second (right) argument first: this way the sequence of tokens that constitutes the expression is traversed strictly in right-to-left order. For reasons of convenience, that sequence can be reversed, so that it is traversed left-to-right instead. Whatever the actual order, the important thing is that the traversal is linear, which makes it trivial to keep track of the currently reached point in the course of recursive evaluation.
If an RPN expression contains at least one operation, there is also at least one operation with immediately available arguments, i.e. an immediately evaluatable operation. (An argument is immediately available either if it is present in the expression as a number, or if it is the result of an already computed sub-expression.) One particular such operation is the first in order (from start to end), but, in general, there may be more than one.
From the above observation it follows that the operations in an RPN expression can be evaluated from start-to-end, using an abstract stack machine. All tokens are processed in order. Processing a number means pushing it onto the stack. An operator is applied on the two topmost numbers in the stack and the obtained result is pushed back in their place. As soon as there are no more tokens to process, the computation concludes with the result as a single element on the stack.
This is the traditional way of implementing an RPN evaluator: recall that evaluating by means of a stack was the main reason the RPN was introduced in computing.
Explicitly constructing a stack of arbitrarily large capacity might be inconvenient and even impossible in a language. The stack-based approach is still applicable, provided that recursive calls are possible.
Suppose we have a procedure gettoken, which normally returns a currently read token – a number or an operator. It also should return an end-of-line flag to signify the end of the expression, and an error flag in case an incorrect token is found. We can construct a recursive procedure evalrpn for computing an RPN expression as follows.
In the first place, we want evalrpn to be able to return everything gettoken can. Within a call of itself, evalrpn shall also be able to return a pair of the kind <operator,number>. A local variable x within evalrpn will store a currently returned number by gettoken. Thus, the instances of the x variables within the unfinished recursive calls of evalrpn at any moment form the stack of intermediate values in the course of the RPN expression evaluation.
More precisely, if the current token obtained from gettoken is a number, evalrpn stores it in its x and calls itself. If the token is an operator, evalrpn returns it. When evalrpn obtains an operator from a call to itself, it attaches its x to that operator and returns the so constructed pair. As the calling instance of evalrpn gets this result, it applies the operator on the attached number and its own x. The result of this application becomes the new value of the x. In this way, an operator is propagated up the sequence of calls of evalrpn until it gets applied.
Here is the text of evalrpn in pseudocode; indentation is for nesting.
evalrpn =
t ← gettoken
if t is an operator or an end-of-line: return t
if t is a number:
x ← t
loop:
res ← evalrpn
if res is not <o,y>: exit loop
x ← x o y
if res is end-of-line: return x
if res is an operator: return <res,x>
return error
Returning <operator,number> is only possible within evalrpn itself, and returning a number – only when an end-of-line is encountered. Thus, returning a number within a recursive call (not from the main call) is transformed into an error signal, because of more than one numbers been left on the stack. Returning an operator from the main call of evalrpn also signifies an error, as this means that an operator is encountered that has no arguments to apply on.
Eventually, the evaluation of the RPN expression is successful if the main call of evalrpn returns a number, and unsuccessful if either an error or an operator is returned. Returning an end-of-line shows that the input line was empty.
This evaluation strategy is implemented in
Another option is to process an expression by replacing already evaluated sub-expressions in it with their respective results. Thus the expression is transformed to gradually simpler RPN expressions and eventually reduces to a single number. This approach applies equally well regardless of whether the expression is represented as a text string or as a sequence of tokens, themselves being strings or numbers and operations.
The order in which the operations within a specific RPN expression are evaluated is to an extent arbitrary: it suffices each time to pick an operation for which the respective arguments are available. Moreover, nothing prevents concurrent evaluation of any number of such operations. Arbitrary ordering and concurrent evaluation fit well the reduction approach, but also are an important computational model of its own.
In the processing of an RPN expression, we can exploit concurrency in two ways. We can evaluate the portion of the expression already read while at the same time reading the rest of it, and we can evaluate different parts of the expression in parallel.
Concurrent evaluation of parts of the expression requires identifying those parts and synchronizing their evaluation with respect to nesting expressions within each other.
…
Some programming languages themselves make use of postfix notation. In such a language it might be a good idea to evaluate RPN expressions by letting them to be interpreted – just as they are, or after light pre-processing – in the language itself. This might require that the correctness of the expression is already ensured before evaluating it. The Factor implementation is an example of this reflexive scheme of evaluation.
Part of the functionality of an RPN calculator is to tell a syntactically wrong RPN expression from a correct one. Ensuring correctness can be achieved in various ways and is related to the strategy chosen for expression processing.
If an RPN calculator program reads an entire line of input before it starts to evaluate it, that makes it possible the corresponding expressions to be syntax-checked and otherwise processed before they get evaluated. Eventually, the RPN expressions can be even ‘compiled’ in a form or another as a means of making them evaluate according to a certain method more conveniently.
While the syntax correctness of RPN expressions is fully defined by the specification, we need a more workable formulation of it. Based on an observation that we made above, it is easy to see that the following is true. There are three ways in which the syntax of an RPN expression can be wrong. Besides there being an incorrect token – one that is neither a number nor an operator – it may be that:
It also follows that an RPN expression is correct if and only if there are more numbers than operators in each initial sub-sequence of tokens, and in the entire expression there are exactly one more numbers than operators.
…
…
…
boykobbatgmaildotcom