Ping-Pong algorithm or criticism of the Reverse Polish Notation

This article is written due to the perturbation that students in our universities offer a simple analysis of mathematical expressions on the basis of just the Reverse Polish Notation (ARF), which is a blatant perversion of normal human logic.

The source of the description of arresters will be the description from Laforet R .: L29 Data structures and algorithms in Java. Classic Computers Science. 2nd ed. - SPb .: Peter, 2013. - 704 s, recommended as the most popular and adequate on this issue, however, as well as on other frequently used algorithms.

Well, that is, we compare different algorithms with different ideologies.

To visualize the sequence of work on the formula (arrester) on p.158 the following graph is given:
')


Already here one can see the adjustment of the algorithm for the property of sequential reading of symbolic information that is incorrect for a person. For a person, the priority selection of expression fragments and the construction of a further calculation scheme for the priorities of these fragments are more characteristic. Therefore, in this case, the scheme will look like in reality:



As we see, an incorrect initial message for character-by-expression parsing of the expression not only distorts the processing of the infix notation, but also significantly complicates the picture of the real analysis of complex formulas with multiple attachments of brackets. After all, the second scheme (Fig. 1) is both clearer and significantly shorter than that shown in Fig. 4.15 of the analyzed source.

Next, I am forced to cite a fairly lengthy quotation from a source in which the owl is being pulled onto the globe.

“As you can see, in the process of calculating the result of an infix arithmetic expression, one has to move along the expression in the forward and reverse directions. First, from left to right, operands and operators are read. When you accumulate enough information to apply the operator, you begin to move in the opposite direction, “remember” two operands and an operator, and perform an arithmetic operation. If an operator is followed by another operator with a higher priority or parenthesis, the application of the operator is postponed. In this case, first apply the next, higher priority statement, and then you go back (left) and apply earlier statements.

Of course, the algorithm for performing such processing could be programmed directly, and yet, as mentioned earlier, it is easier to first convert the expression to a postfix notation. ”(End of quotation)

Let's start with moving in the forward and reverse direction. The fact is that APN apologists usually focus on the last stage of calculations, when already reassorted characters are stacked and removed from there in a row, which of course makes this stage very effective, sort of like. But, as we remember, the work on surge arresters consists of TWO stages (p. 153):

"one. Convert an arithmetic expression to another format called postfix notation.

2. Calculation of the result by postfix notation. ”(End of quotation)

Oops! It turns out the advantages of the second stage are trying to stick out, but the first headache with the first stage is simply modestly mentioning. This is not reproached to the author, the author writes cool - this is a misunderstanding of why this, rather muddy, method is considered basic when parsing formulas and is taught in relevant specialties.

However, let's look closely at the first stage. Fortunately, the author provides a smart table for this (p. 153):



Most of all I liked the last line. Tell me, for God's sake, how it can be consistently pulled out of the STACK here and get a sane result. The system of two stacks, separately for operands and separately for operations, will still work, but with one stack ...

But it is not even about that. How many and what sortings need to be done to make a postfix from an infix (familiar to us) record? Why so break the normal human logic of students in favor of the ancient method? I'm afraid to even imagine how this formula will look, for example: (A + B * C / D) + (EF * ((G / (HJ * (- 1) + I) -L * (MN) -R) + S ) Did you manage to present it at once?

Thus, it can be said that the conversion from infix to postfix recording itself already carries with it an unjustifiably high cost of implementing complex, obscure algorithms for sorting the original data. Moreover, the number of returns at this stage will clearly exceed the resources required for processing the infix (normal) record. Well, the processing of such a postfix entry itself is somehow not limited to primitive pulling out in a row from the stack, but requires an appropriate handler and additional resources.

We illustrate the sequence of required operations (ARF) on a small example.


Tabl. The procedure for calculating a fragment of the formula

But that's not all, because if the numbers are not one digit, then you need to put a buffer to assemble the numbers from individual digits before putting them on the stack or the output string.

I have no task to retell the method of calculating the arrester, so those who are particularly interested can read about it in the original source, especially since it is really cool written. Therefore, we turn to the method (algorithm) Ping-Pong, announced in the title of the article.

At once I will make a reservation, there are quite a lot of methods (algorithms) for parsing formulas. You can call the method of recursive descent and methods of building trees and others. I did not find Ping-Pong on the net, although I think it is used quite often. Why he got this name will be clear from the illustrations.

So, go to the analysis of the algorithm. We start with some definitions for ease of presentation.

Priority - the dominance of one operation or group over the other. The algorithm uses three priorities: 0 - operations "±"; 1 - operations "* /%"; 2 - grouping with parentheses "()". Note: the functions and work with them in this article are not considered. Functions - just a separate layer, which does not affect the priority of operations.

A fragment is a part of a formula that can be transferred for a lower level calculation. That is, a fragment is both a part of a formula framed by brackets and containing operations of the 0th and 1th levels, as well as a trivial fragment containing two operands and an operation sign between them.

For convenience of illustration, we will use the same formula that was proposed above for calculating the arrester: (A + B * C / D) + (EF * ((G / (HJ * (- 1) + I) -L * (MN ) -R) + S) * W). To make it more visual in the process of illustration of the algorithm, I will replace the letters with numbers. Go.

We have a formula line in the input.



Operands are pulled out relative to the sign of the operation, one to the left, the other to the right. The sequence of operations within a fragment is directly protected by the priority of the processing sequence with the substitution by the result. Unary and binary “-” questions are solved inside the addition / subtraction block.

So I think that there is not even a lot of clarification. Well, it is also clear where the name comes from. As you can see, there are no sortings as a class, restrictions on the length of the formula and the number of nested groups are not. All at the level of trivial searches and replacements. In order not to produce fragments of strings, it is enough to use StringBuilder (java) instead of String, which allows you to transform the string without fruiting extra entities. But the main thing is that everything is clear at the level of simple intuitive perception.

For comparison, the algorithms will present them in the same notation.

The algorithm for arresters is taken from the wiki



Ping-Pong algorithm



Thus, the Ping-Pong algorithm is as close as possible to human perception and requires a minimum amount of resources. It also requires minimal analysis of symbols and decision-making procedures, does not require a buffer for assembling numbers from numbers.

I think there are quite a few such intuitive algorithms. So why are students still being tormented by any crap invented in time immemorial?

I would be glad if someone this algorithm is useful.