Polish reverse record
Two plus two, multiply by two?
I don’t know about you, but I was tormented at school for a long time trying to figure out the priority of operations and brackets. Then, like every novice programmer, I suffered with the priority of operations and parentheses when I wrote my own calculator. But it turned out that all these torments were in vain. After all, there is an excellent mechanism known as reverse Polish recording. About what it is and how to work with it I want to tell you.
In mathematics, there is an ancient tradition to place an operator between operands (x + y), and not after operands (xy +). A form with an operator between operands is called an infix notation. The form with the operator after the operands is called postfix, or the reverse Polish record in honor of the Polish logic J. Lukasevich (1958), who studied the properties of this record.
Reverse Polish notation has several advantages over infix notation when expressing algebraic formulas. First, any formula can be expressed without parentheses. Secondly, it is convenient for calculating formulas in stack machines . Third, infix operators have priorities that are arbitrary and undesirable. For example, we know that ab + c means (ab) + c, and not a (b + c), since it was arbitrarily determined that multiplication takes precedence over addition. But does the shift to the left prior to operation AND take priority? Who knows? Reverse Polish entry eliminates such misunderstandings.
Formulation of the problem
The input of the program receives an expression consisting of single-character identifiers and signs of arithmetic operations. It is required to convert this expression to the reverse Polish notation or to report an error.
')
Algorithm for conversion to reverse Polish notation
There are several algorithms for converting infix formulas into reverse Polish entries. We consider the revised algorithm, the idea of which was proposed by E. Dijkstra (EW Dijkstra). Suppose that a formula consists of variables, two-operand operators +, -, *, /, ^, as well as left and right brackets. To mark the end of a formula, we will insert a character after its last character and before the first character of the following formula.
The figure schematically shows a railroad from New York to California with a branch line leading to Texas. Each formula symbol is represented by one car. The train is moving west (left). Before the arrow, each car should stop and find out if it should go straight to California, or if it will need to stop by on the way to Texas. Carriages containing variables are always sent to California and never go to Texas. Carriages that contain all the other symbols must, before passing the arrow, find out about the contents of the nearest car that went to Texas.
The table shows the dependence of the situation on which car went last to Texas and which car is located at the switch. The first carriage (marked with the symbol) is always sent to Texas.
The numbers correspond to the following situations:
1. The car on the arrow goes to Texas
2. The last car heading to Texas turns around and heads for California.
3. The car on the switch and the last car to go to Texas hijack and disappear
4. Stop. The symbols on the California branch are a formula in the reverse Polish notation, if read from left to right
5. Stop. An error has occurred. The original formula was incorrectly balanced.
After each action, a new comparison is made of the car located at the switch (it may be the same car as in the previous comparison, or maybe the next car), and the car that is currently the last to go to Texas. This process continues until step 4 is reached. Note that the line to Texas is used as a stack, where sending the car to Texas is placing the item on the stack, and turning the car sent to Texas toward California is pushing the element out of stack
The order of variables in infix and postfix notation is the same. However, the order of the operators is not always the same. In the reverse Polish record, operators appear in the order in which they will be executed.
An example of calculating the expression in the reverse Polish
Polish reverse is ideal for calculating formulas on a computer with a stack. The formula consists of n characters, each of which is either an operand or an operator. The algorithm for calculating the formula in the reverse Polish notation using the stack is simple. You just need to read the reverse Polish entry from left to right. If an operand is encountered, it must be marked on the stack. If an operator is encountered, you need to perform the operation specified by it.
As an example, consider the calculation of the following expression: (8 + 2 * 5) / (1 + 3 * 2-4). The corresponding formula in the reverse Polish notation looks like this: 825 * + 132 * + 4- /
The number at the top of the stack is the right operand (not the left). This is very important for division, subtraction and exponentiation operations, since the order of the operands in this case matters (as opposed to addition and multiplication). In other words, the division operation acts as follows: first, the numerator is placed on the stack, then the denominator, and then the operation gives the correct result. Note that it is very easy to convert the reverse Polish entry into machine code: you just need to move by the formula in the reverse Polish entry, writing down one command for each character. If a symbol is a constant or variable, you need to write a command to put this constant or variable on the stack, if the symbol is an operator, you need to enter a command to perform this operation.
PS You, as always, can download source codes on my site while it does not lay down under a habraeffekt.
PPS Now everyone can write their calculator. With blackjack and brackets.
I don’t know about you, but I was tormented at school for a long time trying to figure out the priority of operations and brackets. Then, like every novice programmer, I suffered with the priority of operations and parentheses when I wrote my own calculator. But it turned out that all these torments were in vain. After all, there is an excellent mechanism known as reverse Polish recording. About what it is and how to work with it I want to tell you.
In mathematics, there is an ancient tradition to place an operator between operands (x + y), and not after operands (xy +). A form with an operator between operands is called an infix notation. The form with the operator after the operands is called postfix, or the reverse Polish record in honor of the Polish logic J. Lukasevich (1958), who studied the properties of this record.
Reverse Polish notation has several advantages over infix notation when expressing algebraic formulas. First, any formula can be expressed without parentheses. Secondly, it is convenient for calculating formulas in stack machines . Third, infix operators have priorities that are arbitrary and undesirable. For example, we know that ab + c means (ab) + c, and not a (b + c), since it was arbitrarily determined that multiplication takes precedence over addition. But does the shift to the left prior to operation AND take priority? Who knows? Reverse Polish entry eliminates such misunderstandings.
Formulation of the problem
The input of the program receives an expression consisting of single-character identifiers and signs of arithmetic operations. It is required to convert this expression to the reverse Polish notation or to report an error.
')
Algorithm for conversion to reverse Polish notation
There are several algorithms for converting infix formulas into reverse Polish entries. We consider the revised algorithm, the idea of which was proposed by E. Dijkstra (EW Dijkstra). Suppose that a formula consists of variables, two-operand operators +, -, *, /, ^, as well as left and right brackets. To mark the end of a formula, we will insert a character after its last character and before the first character of the following formula.
The figure schematically shows a railroad from New York to California with a branch line leading to Texas. Each formula symbol is represented by one car. The train is moving west (left). Before the arrow, each car should stop and find out if it should go straight to California, or if it will need to stop by on the way to Texas. Carriages containing variables are always sent to California and never go to Texas. Carriages that contain all the other symbols must, before passing the arrow, find out about the contents of the nearest car that went to Texas.
The table shows the dependence of the situation on which car went last to Texas and which car is located at the switch. The first carriage (marked with the symbol) is always sent to Texas.
The numbers correspond to the following situations:
1. The car on the arrow goes to Texas
2. The last car heading to Texas turns around and heads for California.
3. The car on the switch and the last car to go to Texas hijack and disappear
4. Stop. The symbols on the California branch are a formula in the reverse Polish notation, if read from left to right
5. Stop. An error has occurred. The original formula was incorrectly balanced.
After each action, a new comparison is made of the car located at the switch (it may be the same car as in the previous comparison, or maybe the next car), and the car that is currently the last to go to Texas. This process continues until step 4 is reached. Note that the line to Texas is used as a stack, where sending the car to Texas is placing the item on the stack, and turning the car sent to Texas toward California is pushing the element out of stack
The order of variables in infix and postfix notation is the same. However, the order of the operators is not always the same. In the reverse Polish record, operators appear in the order in which they will be executed.
An example of calculating the expression in the reverse Polish
Polish reverse is ideal for calculating formulas on a computer with a stack. The formula consists of n characters, each of which is either an operand or an operator. The algorithm for calculating the formula in the reverse Polish notation using the stack is simple. You just need to read the reverse Polish entry from left to right. If an operand is encountered, it must be marked on the stack. If an operator is encountered, you need to perform the operation specified by it.
As an example, consider the calculation of the following expression: (8 + 2 * 5) / (1 + 3 * 2-4). The corresponding formula in the reverse Polish notation looks like this: 825 * + 132 * + 4- /
The number at the top of the stack is the right operand (not the left). This is very important for division, subtraction and exponentiation operations, since the order of the operands in this case matters (as opposed to addition and multiplication). In other words, the division operation acts as follows: first, the numerator is placed on the stack, then the denominator, and then the operation gives the correct result. Note that it is very easy to convert the reverse Polish entry into machine code: you just need to move by the formula in the reverse Polish entry, writing down one command for each character. If a symbol is a constant or variable, you need to write a command to put this constant or variable on the stack, if the symbol is an operator, you need to enter a command to perform this operation.
PS You, as always, can download source codes on my site while it does not lay down under a habraeffekt.
PPS Now everyone can write their calculator. With blackjack and brackets.
Source: https://habr.com/ru/post/100869/
All Articles