Reverse Polish notation once formed the basis of the world of computer programmer. Today she is not so well known. Therefore, a comic illustration depicting the “reverse” Polish sausage outside the bun can still be misunderstood by some knowledgeable programmers. It is not good to explain the joke, but in this case it will be fully justified.
Infix entry
All programmers and most students are familiar with using 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 mathematical notation, called infix notation, actually poses a big problem for machines. Such an operator takes as input two values written to the left and to the right of it. In programming, using notation with operation signs is optional. For example, x + y can be written as a function to add (x, y), into which the compiler eventually converts 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.
Formula translators
The first truly successful Fortran programming language became so mainly because arithmetic expressions (i.e. formulas) were converted (translated) into code in it, where its name came from - FORmula TRANslation. Before that, they had to be written down, for example, in the form of functions to add (a, multiply (b, c)). In Kobol, the problem of implementing automatic formula conversion was considered very difficult, because programmers had to write things like Add A To B Mutliply By C.
What is wrong with infix?
The problem is that operators have properties such as priority and associativity. Because of this, defining the infix function becomes a non-trivial task. For example, the priority of multiplication is higher than addition or subtraction, and this means that the expression 2 + 3 * 4 is not equal to the sum of 2 and 3 times 4, as would be the case when executing the operators from left to right. In fact, you should multiply 3 by 4 and add 2. This example illustrates that calculating an infix expression often requires changing the order of the operators and their operands. In addition, you have to use parentheses to make the notation look more clear. For example, (2 + 3) * (4 + 5) cannot be written without brackets, because 2 + 3 * 4 + 5 means that you need to multiply 3 by 4 and add 2 and 5.
The order in which operators need to be calculated requires a lot of memorization. Because of this, students starting to learn arithmetic often get the wrong results, even if the operations are actually performed correctly. It is necessary to learn the order of operators by heart. First, actions in brackets must be performed, then multiplication and division, and finally, addition and subtraction. But there are other ways to write mathematical expressions, since infix notation is just one of the possible “small languages” that can be added to the larger one.
Prefix and Postfix Notation
The two best-known alternatives are to write an operator before or after its operands. They are known as prefix and postfix notations. Logic Jan Lukasevich invented the first of them in the 1920s. He lived in Poland, so the record is called Polish. The postfix version, respectively, was called reverse Polish notation (OPN). The only difference between these two methods is in the direction in which the record should be read (from left to right or from right to left), therefore it is enough to consider only one of them in detail. In an arrester, an operator is written after its operands. So, the expression AB + is an example of the reverse Polish notation for A + B.
Unlimited number of operands
The direct advantage of the notation is that it is generalized by the n-adic operator, and infix notation actually works only with two operands, i.e., by its nature, it is suitable only for binary operations. So, for example, ABC @ is the inverse Polish expression using a triadic sign, which finds the maximum value from A, B and C. In this case, the operator acts on 3 operands to its left and corresponds to calling the function @ (A, B, C). If you try to write the @ symbol as an infix, for example A @ BC or something like that, it becomes clear that this simply does not work.
Priority is set in order.
The reverse Polish entry has another advantage in that the priority of the operators can be represented by the order in which they appear. In this case, brackets will never be needed, although they can be included as operation signs to facilitate conversion with infix notation. For example, AB + C * is the unambiguous equivalent of (A + B) * C, since multiplication cannot be calculated until addition is performed, which gives the second operand for the multiplication operation. That is, if AB + C * is calculated one operator at a time, then we get AB + C * -> (AB +) * C -> (A + B) * C.
Calculation algorithm
In an arrester, an operator looks like a function that takes two values as arguments to the left of it. In addition, this is a natural notation for use in programming languages, since its computation corresponds to stack operations and there is no need for parsing. For example, in an arrester, 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 the values to the stack. Each time an 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. Upon reaching the end of the expression, the result of the calculation will be at the top of the stack.
For instance:
- 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 push the result onto the stack.
- S = (5, 6 * 7) = (5, 42) + select 2 values from the stack, apply + and push the result onto the stack.
- S = (5 + 42) = (47) the calculation is completed, the result is at the top of the stack.
This reverse Polish notation algorithm can be tested many times, but each time it will work, no matter how complicated the arithmetic expression is.
OPN and stacks are closely related. The above example demonstrates how you can use memory to calculate the value in reverse Polish notation. It’s less obvious that you can use the stack by converting standard infix expressions to OPN.
Examples in programming languages
In Pascal, the reverse Polish entry 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 a sign of an operation. In the first case, the value is written onto the stack, and in the second, the corresponding action is performed above the two upper numbers of the stack and the result is saved.
toktype: = num;
read (s);
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 <> '+';
c: = cn
end
end;
if (not error) and (toktype = num) then getnumber;
if toktype <> num then begin
y: = pore; x: = pore;
if not error then
case toktype of
add: z: = x + y; sub: z: = xy; mul: z: = x * y; div: z: = x / y
end
push (z);
C-implementation of reverse Polish notation (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 ("% c:", * 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 get people to use surge arrester. In the 1960s, as today, it was possible to buy calculators that work in reverse Polish notation. To add 2 and 3 to them, enter 2, then 3 and press the plus button. At first glance, inputting operands to an operator seemed complicated and difficult to remember, but after some time some became addicted to such a way of thinking and could not understand why others insisted on a silly infix notation, which is so complicated and so limited.
Burroughs even built a mainframe that didn't have any other RAM besides a stack. The only thing the machine did was apply algorithms and methods of reverse Polish writing to the central stack. All its operations were regarded as OPN operators, whose action extended to n upper values. For example, the Return command took the 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 computing, where each program was an expression of an arrester, did not find its continuation.
At one time, reverse Polish calculators were popular, and some still prefer them. In addition, stack-oriented languages such as Forth have been developed. Today it is not used much, but still causes nostalgia from its former users.
So what's the point of a joke about reverse polish sausage?
If we consider a sausage to be an operator, then in infix notation it should be inside the bread, as in an ordinary hot dog. In the reverse Polish entry, it is to the right of the two halves, ready to fall between them after calculation. Now begins the hardest 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 uncounted and, therefore, should be moved to the right of the sausage ... But perhaps this will require too large a stack ...