The reverse Polish record: algorithm, methods and examples

The reverse Polish record was once the basis of the world of the computer programmer. Today it is not so well known. Therefore, a comic illustration depicting the "reverse" Polish sausage outside the bun, may still be misunderstood by some knowledgeable programmers. It is not very good to explain the joke, but in this case it will be fully justified.

Infix entry

All programmers and most students are familiar with the use of operators. For example, in the expression x + y, the addition sign is used to sum the values of the variables x and y. Less well known is that this borrowed from mathematics designation, called infix notation, is actually a big problem for machines. Such an operator takes as input two values written to the left and right of it. In programming, it is not necessary to use a notation with operation signs. For example, x + y can be written as a function to add (x, y), to which the compiler eventually converts the infix notation. However, everyone knows mathematics too well not to use arithmetic expressions, which form a kind of internal mini-language in almost every programming language.

Translators of formulas

The first truly successful Fortran programming language became so basically because the arithmetic expressions (i.e., the formulas) in it were converted (translated) into code, hence its name - FORmula TRANslation. Before, they had to be written, for example, in the form of functions add (a, multiply (b, c)). In Kobol, the problem of implementing automatic formula conversion was considered very difficult, since programmers had to write things like Add A To B Mutliply By C.

What's wrong with the infix?

The problem is that operators have properties such as priority and associativity. Because of this, the definition of the function of the infix becomes a nontrivial task. For example, the multiplication priority is higher than the addition or subtraction, and this means that the expression 2 + 3 * 4 is not equal to the sum of 2 and 3 multiplied by 4, as would be the case when executing operators from left to right. In fact, multiply 3 by 4 and add 2. This example illustrates that evaluating an infix expression often requires changing the order of the operators and their operands. In addition, we have to use parentheses to make the notation look clearer. For example, (2 + 3) * (4 + 5) can not be written without brackets, because 2 + 3 * 4 + 5 means that you must multiply 3 by 4 and add 2 and 5.

The order in which operators are to be calculated requires a long memorization. Because of this, students starting to learn arithmetic often get wrong results, even if in fact the operations are performed correctly. It is necessary to learn the order of the operators' actions by heart. First, the actions in brackets, then multiplication and division, and finally addition and subtraction must be performed. But there are other ways of writing mathematical expressions, because infix notation is just one of the possible "small languages" that can be added to more.

Prefix and postfix notation

The two most popular alternatives are the recording of an operator before or after its operands. They are known as prefix and postfix notations. Logician Jan Lukasevich invented the first of them in the 1920s. He lived in Poland, so the record is called Polish. Postfix version, respectively, was called the reverse Polish notation (OPN). The only difference between the two methods is in the direction in which the entry should be read (left to right or right to left), so it's enough to consider only one of them in detail. In OPN, the operator is written after its operands. Thus, the expression AB + is an example of a reverse Polish record for A + B.

Unlimited number of operands

The immediate advantage of notation is that it is generalized by the n-adic operator, and the infix notation actually works with only two operands, that is, it is by its nature only suitable for binary operations. For example, ABC @ is an inverse Polish expression using the triadic sign, which finds the maximum value from A, B and C. In this case, the operator acts on the 3 operands to the left of itself and corresponds to the call of the function @ (A, B, C). If you try to write the @ symbol as an infix, for example A @ BC or something like that, then it becomes clear that this simply does not work.

Priority is given by the order

An inverse Polish record has one more advantage in that the priority of operators can be represented by the order of their appearance. Parentheses will never be needed, although they can be included as transaction symbols to facilitate conversion with an infix notation. For example, AB + C * is a single-valued equivalent (A + B) * C, since multiplication can not be calculated until addition is completed, which gives the second operand for the multiplication operation. That is, if AB + C * is calculated for one operator at a time, then we get AB + C * -> (AB +) * C -> (A + B) * C.

The calculation algorithm

In OPN, the operator looks like a function that takes as arguments two values written to the left of it. In addition, this is a natural notation for use in programming languages, since the course of its calculations corresponds to stack operations and the need for parsing is eliminated. For example, in ARS the expression 5 + 6 * 7 will look like 5, 6, 7 *, +, and it can be calculated simply by scanning from left to right and writing values to the stack. Each time the operation sign is encountered, the 2 upper elements from the machine memory are selected, the operator is applied and the result is returned to the memory. When the end of the expression is reached, the result of the calculation will be at the top of the stack.

For example:

• S = () 5, 6, 7, *, + put 5 on the stack.
• S = (5) 6, 7, *, + put 6 on the stack.
• S = (5, 6) 7, *, + put 7 on the stack.
• S = (5, 6, 7) *, + select 2 values from the stack, apply * and put the result on the stack.
• S = (5, 6 * 7) = (5, 42) + select 2 values from the stack, apply + and put the result on the stack.
• S = (5 + 42) = (47) the calculation is complete, the result is at the top of the stack.

This algorithm of the reverse Polish entry can be checked many times, but each time it will work, no matter how complex the arithmetic expression is.

Arrester and stacks are closely related. The above example demonstrates how memory can be used to calculate the value in the inverse Polish notation. It is less obvious that you can use the stack by converting standard infix expressions to arrears.

Examples in programming languages

In the Pascal language, the reverse Polish record is implemented approximately like this (part of the program is given).

To read numbers and operators in a loop, a procedure is called that determines whether the token is a number or an operation sign. In the first case, the value is written to the stack, while in the second case, the corresponding action is performed on the top two numbers of the stack and the result is saved.

Toktype: = num;

Read (c);

If with in ['+', '-', '*', '/'] then begin

If eoln then cn: = '' else read (cn);

If cn = '' then

Case with of

'+': Toktype: = add; '-': toktype: = sub;

'*': Toktype: = mul; '/': Toktype: = div

End

Else begin

If c = '-' then sgn: = -1 else error: = c <> '+';

With: = cn

End

End;

If (not error) and (toktype = num) then getnumber;

If toktype <> num then begin

Y: = po; X: = po;

If not error then

Case toktype of

Add: z: = x + y; Sub: z: = x-y; Mul: z: = x * y; Div: z: = x / y

End

Push (z);

C-implementation of the reverse Polish record (part of the program is given):

For (s = strtok (s, w); s; s = strtok (0, w)) {

A = strtod (s, & e);

If (e> s) push (a);

#define rpnop (x) printf ("% s:", * s), b = pop (), a = pop (), push (x)

Else if (* s == '+') rpnop (a + b);

Else if (* s == '-') rpnop (a - b);

Else if (* s == '*') rpnop (a * b);

Else if (* s == '/') rpnop (a / b);

#undef rpnop

}

Hardware implementations

In those days, when computer technology was very expensive, it was considered a good idea to force people to use OPN. In the 1960s, like today, it was possible to buy calculators that work in reverse Polish recording. To add 2 and 3 in them, enter 2, then 3 and press the plus button. At first glance, the input of the operands to the operator seemed complicated and difficult to remember, but after a while some became addicted to this way of thinking and could not understand why others insist on a stupid infix record that is so complicated and so limited.

Burroughs even built a mainframe that did not have any other RAM, except the stack. The only thing that the machine did was apply algorithms and methods of reverse Polish writing to the central stack. All of its operations were regarded as OPN operators, whose action extended to n upper values. For example, the Return command took an address from the top of the stack, etc. The architecture of such a machine was simple, but not fast enough to compete with more general architectures. Many, however, still regret that such a simple and elegant approach to computation, where each program was an expression of the OPN, did not find its continuation.

At one time calculators with reverse Polish recording were popular, and some still prefer them. In addition, stack-oriented languages such as Forth have been developed. Today, it is little used, but still causes nostalgia on the part of its former users.

So what's the point of joking about the back Polish sausage?

If you consider the sausage operator, then in infix notation, it should be inside the roll, as in a normal hot dog. In the reverse Polish record, it is to the right of the two halves, ready to hit between them after the calculation. Now begins the most difficult part - mustard. It is already on the sausage, that is, it has already been calculated as a unary operator. There is an opinion that mustard should also be shown as undefined and, therefore, should be moved to the right of the sausage ... But perhaps it will take too much stack ...