# RPN Calculator Specification

The following text provides a sufficiently detailed specification of the problem chosen to illustrate a considerable portion of the programming languages presented on this site. The specification is needed to ensure a common basis for doing implementations with the same functionality.

Within the restrictions imposed by the specification, there is a number of possible algorithmic options – of which some are depending on the language – that can be taken in a particular implementation. For an account of these, and to read and examine the implementations themselves follow the corresponding links at the top of the page.

For a general discussion on why this problem was chosen see the rationale section.

————————

An RPN calculator program computes expressions written in RPN (Reverse Polish Notation).

An RPN expression (or a postfix expression) is one of the following:

• a number X, in which case the value of the expression is that of X;
• a sequence of the form E1 E2 O, where E1 and E2 are postfix expressions and O is an arithmetic operation; in this case, the value of the expression is that of  E1 O E2.

Note that an RPN expression neither contains parentheses nor involves rules of precedence and associativiy among the operations. Note also that the hierarchy of computation within the expression (and thus its value) is unambiguously determined by the above definition.

The following are RPN expressions:

-52.980765
3 5 /
3 +5 8 * -7 + *

The value of the last of the above expressions is  `3*(((+5)*8)+(-7)) = 99`.

An RPN calculator program reads lines of text from the standard input. If a line is not empty, the program responds with printing one line on the standard output as follows, before it reads the next line or stops:

• if the input line contains a valid RPN expression, the program outputs the value of that expression;
• otherwise, an error message is output.

Empty input lines (including those containing only blanks) are accepted with no response.

The program stops when end-of-input (‘end-of-file’) is encountered.

In the above definition of RPN expression, I have deliberately chosen to consider only dyadic operations. I will furthermore assume that an RPN calculator program only accepts `+` (addition), `-` (subtraction), `*` (multiplication), and `/` (division) as operators, and that for an expression to be considered valid there must be at least one blank character between each two tokens. Leading and trailing blanks are admissible in an expression, as well as more than one such character between tokens.

If possible within the programming language used, the program must exhibit no explicit limitations, such as placing a restriction on the length of the lines that can be read, or on the size of the expressions (measured as number of tokens) that can be handled. This means, for example, that if the implementation uses a stack or some other data container to hold intermediate values in the process of evaluating an expression, that container must not be (explicitly) limited in size, because for arbitrarily long expressions a container of arbitrary capacity may be needed.

The format of the numbers accepted should include reasonable representations of whole and fractional (with a decimal dot) numbers. E.g., if a decimal dot is present, it can occupy a leading or trailing position, and a number can have arithmetic sign, such as in `271.`, `-0`, or `+.0`. Exponential notation is admissible but not required to handle. (Some programming languages only permit restricted forms of representing numbers, so reading numbers according to a language's specific rules does not necessarily lead to a calculator that conforms to our specificaion.)

The above specification of an RPN calculator program intentionally leaves out some possibilities, such as letting an expression be written across several lines of input, or introducing commands for manipulating (the values of) parts of the expression etc. – say, in the style of the traditional dc utility in Unix. These would have probably complicated the specification of the calculator, as well as the program implementations, without really making the problem more challenging, or the implementations more worth doing, in any interesting way.