Reverse Polish entry

    Two plus two, multiply by two?

    I don’t know about you, but at school I suffered for a long time trying to figure out the priority of operations and brackets. Then, like every novice programmer, I was tormented with the priority of operations and parentheses when I wrote my own calculator. But it turned out that all this torment was in vain. After all, there is a wonderful mechanism known as reverse Polish notation. I want to tell you what it is and how to work with it.

    In mathematics, there is an ancient tradition of placing an operator between operands (x + y), and not after operands (xy +). A form with an operator between operands is called infix notation. A form with an operator after the operands is called a postfix or reverse Polish notation in honor of the Polish logician J. Lukasevic (1958), who studied the properties of this notation.
    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 machines with stacks . Third, infix operators have priorities that are arbitrary and undesirable. For example, we know that ab + c means (ab) + c, not a (b + c), since it was arbitrarily determined that multiplication takes precedence over addition. But does left shift take precedence over operation AND? Who knows? Reverse Polish notation 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 reverse Polish notation or report an error.

    Algorithm for translating to reverse Polish notation
    There are several algorithms for converting infix formulas to reverse Polish notation. We will consider the revised algorithm, the idea of ​​which was proposed by E. Dijkstra (EW Dijkstra). Suppose that the formula consists of variables, two-operand operators +, -, *, /, ^, as well as left and right brackets. To mark the end of the formula, we will insert a character after its last character and before the first character of the next formula.


    The figure schematically shows a railroad from New York to California with a branch to Texas. Each symbol of the formula is represented by one carriage. The train moves west (to the left). In front of the arrow, each car should stop and find out if it should go straight to California, or if it would need to call Texas on the way. Wagons containing variables are always sent to California and never travel to Texas. Wagons containing all other symbols must know the contents of the nearest wagon that went to Texas before passing the arrow.
    The table shows the dependence of the situation on which carriage went to Texas last and which car is at the arrow. The first wagon (marked with a ⊥) always leaves for Texas. The numbers correspond to the following situations:




    1. The wagon on the arrow leaves for Texas
    2. The last wagon heading to Texas turns around and heads for California
    3. The wagon on the arrow and the last wagon leaving for Texas are stolen and disappear
    4. Stop. Symbols located on the California branch represent the formula in the reverse Polish notation, if you 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 wagon located at the arrow (it may be the same wagon as in the previous comparison, or may be the next wagon), and the wagon, which at the moment was the last to leave for Texas. This process continues until step 4 is reached. Note that the line to Texas is used as a stack, where sending a wagon to Texas is putting an item on the stack, and turning a car sent to Texas towards California is pushing the element out stack.
    The order of variables in the infix and postfix entries is the same. However, the order of the operators is not always the same. In reverse Polish notation, statements appear in the order in which they will be executed.

    Example of evaluating an expression in reverse Polish notation
    Reverse Polish notation 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 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 found, it must be pushed onto the stack. If an operator is encountered, you must 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 the operations of division, subtraction and exponentiation, since the order of operands in this case is important (in contrast to the operations of 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 notation into machine code: you just need to move by the formula in the reverse Polish notation, writing down one command for each character. If the symbol is a constant or variable, you need to enter the command to put this constant or variable on the stack, if the symbol is an operator, you need to enter the command to perform this operation.

    PS You, as always, can download the source codes on my site until it falls under the habraeffect.
    PPS Now everyone can write their own calculator. With blackjack and brackets.

    Also popular now: