Reverse Polish notation: how to cook a hot dog?
Being an amateur in the field of application development, I experienced difficulties with understanding the algorithm of the reverse Polish notation, and to be more precise, the stack preparation algorithm. Cases as little helped articles in the "Internet".
It all started with the fact that I started creating a simple interpreter for my own project. To solve complex expressions, there were two algorithms to choose from: recursive descent and reverse Polish notation. The obvious simplicity and approach to solving the problem (and perhaps the name itself) allowed the latter to become a subject for study.
The case was helped by two articles. One of them is on Wikipedia , and the second was written by a wonderful user of Habr, GORKOFF , who literally explained everything on his fingers.
')
However, until the end I did not understand that important question: how to build the stack?
I will not beat around the bush, let's start in order. Imagine that we have a certain array with operations and operands in which the following expression is written: 5 * 2 + 10 . We translate this expression into the form that "eats" the algorithm of the reverse Polish notation. For this we need a stack of operations and an output array. Next, it is important to determine the priority of operations. This is necessary for the correct distribution of the order of mathematical operations, for example, to give preference to multiplication over addition.
High priority (1): here, following the laws of mathematics, we place multiplication and division.
Low priority (2): add and subtract here.
Once we have decided on priorities, we will proceed to the construction itself. Before starting, I have to explain something:
all numbers are operands. They are always written to the output array. The signs of addition, subtraction, and so on - are operations. But they can be both in the stack of operations, and in the output array. Where they go - depends on what is the last in the stack. Go in order, from left to right:
We read "5".
Operand, put in the output array.
Add 5 to the output array.
Output array: 5.
Stack of operations: empty.
We read "*".
Operation. There is nothing in the stack of operations, so we put it on the stack of operations.
Add * to the stack of operations.
Output array: 5.
Stack of operations: *.
We read "2".
Operand, put in the output array.
Add 2 to the output array.
Output array: 5, 2.
Stack of operations: *.
We read "+".
Operation. The last character in the stack of operations (*) takes precedence over the current character (+). Therefore, we move the last character from the stack of operations to the output array.
Move * to exit stack. Add + to the stack of operations.
Output array: 5, 2, *.
Stack of operations: +.
We read "10".
Operand, put in the output array.
Add 2 to the output array.
Output array: 5, 2, *, 10.
Stack of operations: +.
Since all the characters have ended, we simply push everything from the stack of operations into the output array.
Output array: 5, 2, *, 10, +.
Now it is possible to solve the resulting string according to the algorithm of reverse Polish notation (from left to right):
As a result, we have a solution to the problem:
5 * 2 + 10 = 20
This example does not demonstrate the whole picture. Let's try a more complex expression:
(6 + 10-4) / (1 + 1 * 2) +1
We read "(".
Despite the fact that the surge arrester algorithm is considered to be without a scrap, we still consider the bracket for the operation. Since this is an opening bracket, we simply add it to the stack.
Add (to the stack of operations.
Output array: empty.
Stack of operations: (.
We read "6"
Add to the output array.
Output array: 6.
Stack of operations: (.
We read "+"
Add to the stack of operations.
Output array: 6.
Stack of operations: (, +.
We read "10"
Add to the output array.
Output array: 6, 10.
Stack of operations: (, +.
We read "-"
Since the current character (-) has equal priority over the last character in the stack (+), we still push the sign from the stack into the output array, and add the current one to the stack.
Output array: 6, 10, +.
Stack of operations: (, -.
We read "4"
Add to the output array.
Output array: 6, 10, +, 4.
Stack of operations: (, -.
We read ")"
Again the bracket, but now the closing one. Here you need to push all the characters from the stack to the array before the first opening bracket. We just need to get rid of both brackets.
Push "-" into the array of operations. We get rid of brackets.
Output array: 6.10, +, 4, -.
Stack of operations: empty.
We read "/"
Add to the stack.
Output array: 6.10, +, 4, -.
Stack of operations: /.
We read "("
Add to the stack.
Output array: 6.10, +, 4, -.
Stack of operations: /, (.
We read "1"
Add to array.
Output array: 6.10, +, 4, -, 1.
Stack of operations: /, (.
We read "+"
Add to the stack.
Output array: 6.10, +, 4, -, 1.
Stack of operations: /, (, +.
We read "1"
Add to array.
Output array: 6.10, +, 4, -, 1, 1.
Stack of operations: /, (, +.
We read "*"
The last character in the stack of operations (+) takes precedence over the current character (*). Therefore, we don’t touch the last character from the stack, but simply add the current one to the stack as usual.
Add to the stack.
Output array: 6.10, +, 4, -, 1, 1.
Stack of operations: /, (, +, *.
We read "2"
Add to array.
Output array: 6,10, +, 4, -, 1, 1, 2.
Stack of operations: /, (, +, *.
We read ")"
Again closing bracket, we do everything as last time.
Pushes * and + into an array of operations. We get rid of brackets.
Output array: 6,10, +, 4, -, 1, 1, 2, *, +.
Stack of operations: /.
We read "+"
The dividing sign has a higher priority. Push / into array. Add + to the stack.
Output array: 6,10, +, 4, -, 1, 1, 2, *, +, /.
Stack of operations: +.
We read "1"
Add to array.
Output array: 6,10, +, 4, -, 1, 1, 2, *, +, /, 1.
Stack of operations: +.
The expression is complete. Again, push everything from the stack of operations into the output array.
Output array: 6,10, +, 4, -, 1, 1, 2, *, +, /, 1, +.
Consider again.
Total: (6 + 10-4) / (1 + 1 * 2) + 1 = 5
Conclusion: if the current character is an operation, and the last character from the operation stack has priority below or equal, then the last character from the stack goes to the output array, and the current one is added to the stack. Otherwise, everything is added as usual. Simply put: operations are candidates for adding to an output array, but in order for them to get there, you need a sign with a lower or with the same priority at the input.
Thus, I can trust this stack building algorithm. It should be noted that I clearly did not use priority signs even higher, such as squaring or root computation. With this, I think, difficulties will not arise, since the algorithm will not change.
I will not touch on the topic affecting the pros and cons of the surge arrester algorithm, as well as its optimization. Here I tried to explain everything literally for those who, just like me, are looking for a solution to this issue.
It all started with the fact that I started creating a simple interpreter for my own project. To solve complex expressions, there were two algorithms to choose from: recursive descent and reverse Polish notation. The obvious simplicity and approach to solving the problem (and perhaps the name itself) allowed the latter to become a subject for study.
The case was helped by two articles. One of them is on Wikipedia , and the second was written by a wonderful user of Habr, GORKOFF , who literally explained everything on his fingers.
')
However, until the end I did not understand that important question: how to build the stack?
I will not beat around the bush, let's start in order. Imagine that we have a certain array with operations and operands in which the following expression is written: 5 * 2 + 10 . We translate this expression into the form that "eats" the algorithm of the reverse Polish notation. For this we need a stack of operations and an output array. Next, it is important to determine the priority of operations. This is necessary for the correct distribution of the order of mathematical operations, for example, to give preference to multiplication over addition.
High priority (1): here, following the laws of mathematics, we place multiplication and division.
Low priority (2): add and subtract here.
Once we have decided on priorities, we will proceed to the construction itself. Before starting, I have to explain something:
all numbers are operands. They are always written to the output array. The signs of addition, subtraction, and so on - are operations. But they can be both in the stack of operations, and in the output array. Where they go - depends on what is the last in the stack. Go in order, from left to right:
We read "5".
Operand, put in the output array.
Add 5 to the output array.
Output array: 5.
Stack of operations: empty.
We read "*".
Operation. There is nothing in the stack of operations, so we put it on the stack of operations.
Add * to the stack of operations.
Output array: 5.
Stack of operations: *.
We read "2".
Operand, put in the output array.
Add 2 to the output array.
Output array: 5, 2.
Stack of operations: *.
We read "+".
Operation. The last character in the stack of operations (*) takes precedence over the current character (+). Therefore, we move the last character from the stack of operations to the output array.
Move * to exit stack. Add + to the stack of operations.
Output array: 5, 2, *.
Stack of operations: +.
We read "10".
Operand, put in the output array.
Add 2 to the output array.
Output array: 5, 2, *, 10.
Stack of operations: +.
Since all the characters have ended, we simply push everything from the stack of operations into the output array.
Output array: 5, 2, *, 10, +.
Now it is possible to solve the resulting string according to the algorithm of reverse Polish notation (from left to right):
Decision
1) {5, 2, *, 10, +} {Empty}
2) {2, *, 10, +} {5}
3) {*, 10, +} {5, 2}
4) {10, +} {10}
5) {+} {10, 10}
6) {} {20}
2) {2, *, 10, +} {5}
3) {*, 10, +} {5, 2}
4) {10, +} {10}
5) {+} {10, 10}
6) {} {20}
As a result, we have a solution to the problem:
5 * 2 + 10 = 20
This example does not demonstrate the whole picture. Let's try a more complex expression:
(6 + 10-4) / (1 + 1 * 2) +1
We read "(".
Despite the fact that the surge arrester algorithm is considered to be without a scrap, we still consider the bracket for the operation. Since this is an opening bracket, we simply add it to the stack.
Add (to the stack of operations.
Output array: empty.
Stack of operations: (.
We read "6"
Add to the output array.
Output array: 6.
Stack of operations: (.
We read "+"
Add to the stack of operations.
Output array: 6.
Stack of operations: (, +.
We read "10"
Add to the output array.
Output array: 6, 10.
Stack of operations: (, +.
We read "-"
Since the current character (-) has equal priority over the last character in the stack (+), we still push the sign from the stack into the output array, and add the current one to the stack.
Output array: 6, 10, +.
Stack of operations: (, -.
We read "4"
Add to the output array.
Output array: 6, 10, +, 4.
Stack of operations: (, -.
We read ")"
Again the bracket, but now the closing one. Here you need to push all the characters from the stack to the array before the first opening bracket. We just need to get rid of both brackets.
Push "-" into the array of operations. We get rid of brackets.
Output array: 6.10, +, 4, -.
Stack of operations: empty.
We read "/"
Add to the stack.
Output array: 6.10, +, 4, -.
Stack of operations: /.
We read "("
Add to the stack.
Output array: 6.10, +, 4, -.
Stack of operations: /, (.
We read "1"
Add to array.
Output array: 6.10, +, 4, -, 1.
Stack of operations: /, (.
We read "+"
Add to the stack.
Output array: 6.10, +, 4, -, 1.
Stack of operations: /, (, +.
We read "1"
Add to array.
Output array: 6.10, +, 4, -, 1, 1.
Stack of operations: /, (, +.
We read "*"
The last character in the stack of operations (+) takes precedence over the current character (*). Therefore, we don’t touch the last character from the stack, but simply add the current one to the stack as usual.
Add to the stack.
Output array: 6.10, +, 4, -, 1, 1.
Stack of operations: /, (, +, *.
We read "2"
Add to array.
Output array: 6,10, +, 4, -, 1, 1, 2.
Stack of operations: /, (, +, *.
We read ")"
Again closing bracket, we do everything as last time.
Pushes * and + into an array of operations. We get rid of brackets.
Output array: 6,10, +, 4, -, 1, 1, 2, *, +.
Stack of operations: /.
We read "+"
The dividing sign has a higher priority. Push / into array. Add + to the stack.
Output array: 6,10, +, 4, -, 1, 1, 2, *, +, /.
Stack of operations: +.
We read "1"
Add to array.
Output array: 6,10, +, 4, -, 1, 1, 2, *, +, /, 1.
Stack of operations: +.
The expression is complete. Again, push everything from the stack of operations into the output array.
Output array: 6,10, +, 4, -, 1, 1, 2, *, +, /, 1, +.
Consider again.
Decision
1) {6,10, +, 4, -, 1, 1, 2, *, +, /, 1, +} {Empty}
2) {10, +, 4, -, 1, 1, 2, *, +, /, 1, +} {6}
3) {+, 4, -, 1, 1, 2, *, +, /, 1, +} {6.10}
4) {4, -, 1, 1, 2, *, +, /, 1, +} {16}
5) {-, 1, 1, 2, *, +, /, 1, +} {16.4}
6) {1, 1, 2, *, +, /, 1, +} {12}
7) {1, 2, *, +, /, 1, +} {12, 1}
8) {2, *, +, /, 1, +} {12, 1, 1}
9) {*, +, /, 1, +} {12, 1, 1, 2}
10) {+, /, 1, +} {12, 1, 2}
11) {/, 1, +} {12, 3}
12) {1, +} {4}
13) {+} {4, 1}
13) {} {5}
2) {10, +, 4, -, 1, 1, 2, *, +, /, 1, +} {6}
3) {+, 4, -, 1, 1, 2, *, +, /, 1, +} {6.10}
4) {4, -, 1, 1, 2, *, +, /, 1, +} {16}
5) {-, 1, 1, 2, *, +, /, 1, +} {16.4}
6) {1, 1, 2, *, +, /, 1, +} {12}
7) {1, 2, *, +, /, 1, +} {12, 1}
8) {2, *, +, /, 1, +} {12, 1, 1}
9) {*, +, /, 1, +} {12, 1, 1, 2}
10) {+, /, 1, +} {12, 1, 2}
11) {/, 1, +} {12, 3}
12) {1, +} {4}
13) {+} {4, 1}
13) {} {5}
Total: (6 + 10-4) / (1 + 1 * 2) + 1 = 5
Conclusion: if the current character is an operation, and the last character from the operation stack has priority below or equal, then the last character from the stack goes to the output array, and the current one is added to the stack. Otherwise, everything is added as usual. Simply put: operations are candidates for adding to an output array, but in order for them to get there, you need a sign with a lower or with the same priority at the input.
Thus, I can trust this stack building algorithm. It should be noted that I clearly did not use priority signs even higher, such as squaring or root computation. With this, I think, difficulties will not arise, since the algorithm will not change.
I will not touch on the topic affecting the pros and cons of the surge arrester algorithm, as well as its optimization. Here I tried to explain everything literally for those who, just like me, are looking for a solution to this issue.
Source: https://habr.com/ru/post/282379/
All Articles