Reverse Polish notation converting and calculating

calculate.py

# Author: Andrieiev Danil Maksimovich
# danssg08@gmail.com | https://github.com/DanilAndreev

def calculate(input_tokens: list) -> float:
    """
    calculate - function, designed to calculate math expression in Reverse polish notation (RPN).

    :argument input_tokens: List of tokens ordered in RPN.
    :raises SyntaxError:
    :returns: Calculated number
    """
    # Stack for calculations.
    stack: list = []
    # Loop while input tokens array is not empty.
    while len(input_tokens):
        # Getting next element and deleting it from the input_tokens. Always getting first element.
        item: str = input_tokens.pop(0)
        if item.isnumeric():
            # Numbers are pushed to stack.
            stack.append(float(item))
        else:
            try:
                # Getting two operands from stack.
                # Note: second operand on the top of stack!
                second = stack.pop()
                first = stack.pop()
                # Determining operation and applying it. After operation result is pushed to top of the stack.
                if item == "+":
                    stack.append(first + second)
                elif item == "-":
                    stack.append(first - second)
                elif item == "*":
                    stack.append(first * second)
                elif item == "/":
                    stack.append(first / second)
                elif item == "^":
                    stack.append(first ** second)
            except Exception:
                raise SyntaxError("Incorrect expression")

    # If stack contains not one element - error.
    if len(stack) != 1:
        raise SyntaxError("Incorrect expression")

    return stack[0]

convert.py

# Author: Andrieiev Danil Maksimovich
# danssg08@gmail.com | https://github.com/DanilAndreev

def convert(input_tokens: list) -> list:
    """
    convert - function, designed to convert an array of tokens in infix notation
    to Reverse polish notation (RPN)(postfix notation)

    :argument input_tokens: A list of input tokens. Numbers for operands and symbols for operators.
    :raises SyntaxError:
    :returns: List of tokens ordered in RPN.
    """
    PRIORITIES: dict = {
        "start": 0,
        "(": 1,
        ")": 1,
        # Next operators must stick to the rule:
        # The higher the priority, the higher the number.
        # If operators have same priority - their numbers must be equal.
        "+": 2,
        "-": 2,
        "*": 3,
        "/": 3,
        "^": 4,
    }

    # Here are described right-associated operators, such as power.
    RIGHT_ASSOCIATED_OPERATORS = ["^"]

    # Here will appear result expression in Reverse polish notation.
    result: list = []
    # Temporary stack.
    stack: list = ["start"]

    # Main loop
    while len(input_tokens):
        if input_tokens[0].isnumeric():
            # If token is numeric (is operand) - move it to result
            result.append(input_tokens.pop(0))
            continue

        stack_item: str = stack[len(stack) - 1]
        input_item: str = input_tokens[0]

        if stack_item == "(" and input_item == ")":
            # Delete first token from the input_tokens.
            input_tokens.pop(0)
            # Delete token on top of the stack.
            stack.pop()
        elif stack_item == "start" and input_item == ")":
            raise SyntaxError("Incorrect expression")
        elif stack_item == "(" and not len(input_tokens):
            raise SyntaxError("Incorrect expression")
        else:
            if input_item == "(":
                # Opening round brace must be pushed to stack.
                stack.append(input_tokens.pop(0))
            elif PRIORITIES.get(stack_item) == PRIORITIES.get(input_item) and input_item in RIGHT_ASSOCIATED_OPERATORS:
                # Move item from top of the stack to result list if operator is right-associated.
                stack.append(input_tokens.pop(0))
            elif PRIORITIES.get(stack_item) < PRIORITIES.get(input_item):
                # If token operator on top of the stack has lower priority then next token
                # from input stream - move it to the stack
                stack.append(input_tokens.pop(0))
            else:
                # Else move item from top of the stack to result list.
                result.append(stack.pop())

    # Removing "start" element from the stack.
    stack.pop(0)
    # Reversing stack to make operators order correct for extending result array.
    stack.reverse()
    # Extending result array with remaining operators.
    result.extend(stack)
    return result

main.py

# Author: Andrieiev Danil Maksimovich
# danssg08@gmail.com | https://github.com/DanilAndreev

from convert import convert
from calculate import calculate

# Input expression, each item separated with whitespace (it isn't example of lexer)
expression: str = "( 4 + 3 * 20 ) / ( 10 + 3 * 3 ^ 2 - 12 ) + 2 ^ 2 ^ 3"

# Generating tokens array. If token isn't numeric - interpret as operator.
tokens = expression.split(" ")

converted: list = convert(tokens)
print(" ".join(converted))

calculated: float = calculate(converted)
print(calculated)

Reverse Polish Notation (RPN).md

Reverse Polish Notation (RPN)

There is an ancient tradition in mathematics to place an operator between the operands (x + y) rather than after the operands xy+. Form with an operator between operands is called infix notation. The form with an operator after the operands is called postfix, or Reverse Polish notation. It has a number of advantages over infix notation when expressing algebraic formulas:

1. Any formula can be expressed without parentheses.
2. It is convenient for calculating formulas on stacked machines.
3. Infix operators have precedence that is arbitrary and undesirable.

For example, we know that ab+c means (ab)+c, not a(b+c), since it was arbitrarily determined that multiplication has priority over addition. But does the left shift take precedence over the AND operation? Who knows? Reverse Polish notation allows you to eliminate such misunderstandings.

Converting infix notation to RPN

We will consider an algorithm, the idea of which was proposed by E.W. Dijkstra. Let the formula consist of variables, two-operand operators + - * / ^, as well as left and right parentheses. For convenience, it is suggested to insert markers start and end before the beginning of the formula and at the end, respectively.

        (result expression in RPN)                       
                                                    (here we choose way)    [ (,4,+,3,*,20,),/,(,10,+,3,*,3,^,2,-,12,) ]
                  result <─────────────────────────────────── ? <───────────────── queue 
                      ^                                       │              (input expression)
                      │                                       │
                      │                                       │
                      │ (here operators are temporary stored) │
                      └─────────────── stack <────────────────┘
                                     [ start ]

The diagram shows the paths of movement of an element from the queue to the resulting list. Elements move from left to right. In a place indicated by the sign ?, a decision is made on the path of further movement of the element from the beginning of the queue. The elements can move directly to the resulting list or hit the stack along the way.

Operands (variables) always move directly to the resulting list.

The table shows the dependence of the situation on which operator is next in line and which operator is on the top of the stack.

The start element is always pushed onto the stack.

	end	+	-	*	/	^	(	)
start	4	1	1	1	1	1	1	5
+	2	2	2	1	1	1	1	2
-	2	2	2	1	1	1	1	2
*	2	2	2	2	2	1	1	2
.	2	2	2	2	2	1	1	2
^	2	2	2	2	2	1	1	2
(	5	1	1	1	1	1	1	3

Vertically - the operator at the top of the stack.
Horizontally - the next operator in the queue.

The numbers correspond to the following situations:

1. The next operator from the queue is pushed onto the stack.
2. The operator at the top of the stack is sent to the end of the resulting list.
3. The next operator from the queue and the operator at the top of the stack are removed and disappeared.
4. The resulting list contains the expression in reverse Polish notation. End of conversion.
5. Fatal error. The input expression is formulated incorrectly.

After each action, the next comparison is made between the operator from the queue and the operator at the top of the stack. Process continues until situation 4 is reached.

The order of variables in infix and postfix notation 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.

Conversion steps explained

0. Initially stack contains start item. Input infix expression in queue.

        (result expression in RPN)                       
                  [ ]                               (here we choose way)    [ (,4,+,3,*,20,),/,(,10,+,3,*,3,^,2,-,12,) ]
                  result <─────────────────────────────────── ? <───────────────── queue 
                      ^                                       │              (input expression)
                      │                                       │
                      │                                       │
                      │ (here operators are temporary stored) │
                      └─────────────── stack <────────────────┘
                                     [ start ]

1. Moving ( to the stack.

        (result expression in RPN)                       
                  [ ]                               (here we choose way)    [ 4,+,3,*,20,),/,(,10,+,3,*,3,^,2,-,12,) ]
                  result <─────────────────────────────────── ? <───────────────── queue 
                      ^                                       │              (input expression)
                      │                                       │
                      │                                       │
                      │ (here operators are temporary stored) │
                      └─────────────── stack <────────────────┘
                                     [ start,( ]

2. Moving 4 to the result list.

        (result expression in RPN)                       
                  [ 4 ]                             (here we choose way)    [ +,3,*,20,),/,(,10,+,3,*,3,^,2,-,12,) ]
                  result <─────────────────────────────────── ? <───────────────── queue 
                      ^                                       │              (input expression)
                      │                                       │
                      │                                       │
                      │ (here operators are temporary stored) │
                      └─────────────── stack <────────────────┘
                                     [ start,( ]

3. Moving + to the stack.

        (result expression in RPN)                       
                  [ 4 ]                             (here we choose way)    [ 3,*,20,),/,(,10,+,3,*,3,^,2,-,12,) ]
                  result <─────────────────────────────────── ? <───────────────── queue 
                      ^                                       │              (input expression)
                      │                                       │
                      │                                       │
                      │ (here operators are temporary stored) │
                      └─────────────── stack <────────────────┘
                                     [ start,(,+ ]

4. Moving 3 to the result list.

        (result expression in RPN)                       
                  [ 4,3 ]                           (here we choose way)    [ *,20,),/,(,10,+,3,*,3,^,2,-,12,) ]
                  result <─────────────────────────────────── ? <───────────────── queue 
                      ^                                       │              (input expression)
                      │                                       │
                      │                                       │
                      │ (here operators are temporary stored) │
                      └─────────────── stack <────────────────┘
                                     [ start,(,+ ]

5. Moving * to the stack.

        (result expression in RPN)                       
                  [ 4,3 ]                           (here we choose way)    [ 20,),/,(,10,+,3,*,3,^,2,-,12,) ]
                  result <─────────────────────────────────── ? <───────────────── queue 
                      ^                                       │              (input expression)
                      │                                       │
                      │                                       │
                      │ (here operators are temporary stored) │
                      └─────────────── stack <────────────────┘
                                     [ start,(,+,* ]

6. Moving 20 to the result list.

        (result expression in RPN)                       
                  [ 4,3,20 ]                        (here we choose way)    [ ),/,(,10,+,3,*,3,^,2,-,12,) ]
                  result <─────────────────────────────────── ? <───────────────── queue 
                      ^                                       │              (input expression)
                      │                                       │
                      │                                       │
                      │ (here operators are temporary stored) │
                      └─────────────── stack <────────────────┘
                                     [ start,(,+,* ]

7. Moving * from the stack to the result list.

        (result expression in RPN)                       
                  [ 4,3,20,* ]                      (here we choose way)    [ ),/,(,10,+,3,*,3,^,2,-,12,) ]
                  result <─────────────────────────────────── ? <───────────────── queue 
                      ^                                       │              (input expression)
                      │                                       │
                      │                                       │
                      │ (here operators are temporary stored) │
                      └─────────────── stack <────────────────┘
                                     [ start,(,+ ]

8. Moving + from the stack to the result list.

        (result expression in RPN)                       
                  [ 4,3,20,*,+ ]                    (here we choose way)    [ ),/,(,10,+,3,*,3,^,2,-,12,) ]
                  result <─────────────────────────────────── ? <───────────────── queue 
                      ^                                       │              (input expression)
                      │                                       │
                      │                                       │
                      │ (here operators are temporary stored) │
                      └─────────────── stack <────────────────┘
                                     [ start,( ]

9. Removing ( from the stack and removing ) from the input queue.

        (result expression in RPN)                       
                  [ 4,3,20,*,+ ]                    (here we choose way)    [ /,(,10,+,3,*,3,^,2,-,12,) ]
                  result <─────────────────────────────────── ? <───────────────── queue 
                      ^                                       │              (input expression)
                      │                                       │
                      │                                       │
                      │ (here operators are temporary stored) │
                      └─────────────── stack <────────────────┘
                                     [ start ]

10. Moving / to the stack.

        (result expression in RPN)                       
                  [ 4,3,20,*,+ ]                    (here we choose way)    [ (,10,+,3,*,3,^,2,-,12,) ]
                  result <─────────────────────────────────── ? <───────────────── queue 
                      ^                                       │              (input expression)
                      │                                       │
                      │                                       │
                      │ (here operators are temporary stored) │
                      └─────────────── stack <────────────────┘
                                     [ start,/ ]

11. Moving ( to the stack.

        (result expression in RPN)                       
                  [ 4,3,20,*,+ ]                    (here we choose way)    [ 10,+,3,*,3,^,2,-,12,) ]
                  result <─────────────────────────────────── ? <───────────────── queue 
                      ^                                       │              (input expression)
                      │                                       │
                      │                                       │
                      │ (here operators are temporary stored) │
                      └─────────────── stack <────────────────┘
                                     [ start,/,( ]

12. Moving 10 to the result list.

        (result expression in RPN)                       
                  [ 4,3,20,*,+,10 ]                 (here we choose way)    [ +,3,*,3,^,2,-,12,) ]
                  result <─────────────────────────────────── ? <───────────────── queue 
                      ^                                       │              (input expression)
                      │                                       │
                      │                                       │
                      │ (here operators are temporary stored) │
                      └─────────────── stack <────────────────┘
                                     [ start,/,( ]

13. Moving + to the stack.

        (result expression in RPN)                       
                  [ 4,3,20,*,+,10 ]                 (here we choose way)    [ 3,*,3,^,2,-,12,) ]
                  result <─────────────────────────────────── ? <───────────────── queue 
                      ^                                       │              (input expression)
                      │                                       │
                      │                                       │
                      │ (here operators are temporary stored) │
                      └─────────────── stack <────────────────┘
                                     [ start,/,(,+ ]

14. Moving 3 to the result list.

        (result expression in RPN)                       
                  [ 4,3,20,*,+,10,3 ]               (here we choose way)    [ *,3,^,2,-,12,) ]
                  result <─────────────────────────────────── ? <───────────────── queue 
                      ^                                       │              (input expression)
                      │                                       │
                      │                                       │
                      │ (here operators are temporary stored) │
                      └─────────────── stack <────────────────┘
                                     [ start,/,(,+ ]

15. Moving * to the stack.

        (result expression in RPN)                       
                  [ 4,3,20,*,+,10,3 ]               (here we choose way)    [ 3,^,2,-,12,) ]
                  result <─────────────────────────────────── ? <───────────────── queue 
                      ^                                       │              (input expression)
                      │                                       │
                      │                                       │
                      │ (here operators are temporary stored) │
                      └─────────────── stack <────────────────┘
                                     [ start,/,(,+,* ]

16. Moving 3 to the result list.

        (result expression in RPN)                       
                  [ 4,3,20,*,+,10,3,3 ]             (here we choose way)    [ ^,2,-,12,) ]
                  result <─────────────────────────────────── ? <───────────────── queue 
                      ^                                       │              (input expression)
                      │                                       │
                      │                                       │
                      │ (here operators are temporary stored) │
                      └─────────────── stack <────────────────┘
                                     [ start,/,(,+,* ]

17. Moving ^ to the stack.

        (result expression in RPN)                       
                  [ 4,3,20,*,+,10,3,3 ]             (here we choose way)    [ 2,-,12,) ]
                  result <─────────────────────────────────── ? <───────────────── queue 
                      ^                                       │              (input expression)
                      │                                       │
                      │                                       │
                      │ (here operators are temporary stored) │
                      └─────────────── stack <────────────────┘
                                     [ start,/,(,+,*,^ ]

18. Moving 2 to the result list.

        (result expression in RPN)                       
                  [ 4,3,20,*,+,10,3,3,2 ]           (here we choose way)    [ -,12,) ]
                  result <─────────────────────────────────── ? <───────────────── queue 
                      ^                                       │              (input expression)
                      │                                       │
                      │                                       │
                      │ (here operators are temporary stored) │
                      └─────────────── stack <────────────────┘
                                     [ start,/,(,+,*,^ ]

19. Moving ^ from the stack to the result list.

        (result expression in RPN)                       
                  [ 4,3,20,*,+,10,3,3,2,^ ]         (here we choose way)    [ -,12,) ]
                  result <─────────────────────────────────── ? <───────────────── queue 
                      ^                                       │              (input expression)
                      │                                       │
                      │                                       │
                      │ (here operators are temporary stored) │
                      └─────────────── stack <────────────────┘
                                     [ start,/,(,+,* ]

20. Moving * from the stack to the result list.

        (result expression in RPN)                       
                  [ 4,3,20,*,+,10,3,3,2,^,* ]       (here we choose way)    [ -,12,) ]
                  result <─────────────────────────────────── ? <───────────────── queue 
                      ^                                       │              (input expression)
                      │                                       │
                      │                                       │
                      │ (here operators are temporary stored) │
                      └─────────────── stack <────────────────┘
                                     [ start,/,(,+ ]

21. Moving + from the stack to the result list.

        (result expression in RPN)                       
                  [ 4,3,20,*,+,10,3,3,2,^,*,+ ]     (here we choose way)    [ -,12,) ]
                  result <─────────────────────────────────── ? <───────────────── queue 
                      ^                                       │              (input expression)
                      │                                       │
                      │                                       │
                      │ (here operators are temporary stored) │
                      └─────────────── stack <────────────────┘
                                     [ start,/,( ]

22. Moving - to the stack.

        (result expression in RPN)                       
                  [ 4,3,20,*,+,10,3,3,2,^,*,+ ]     (here we choose way)    [ 12,) ]
                  result <─────────────────────────────────── ? <───────────────── queue 
                      ^                                       │              (input expression)
                      │                                       │
                      │                                       │
                      │ (here operators are temporary stored) │
                      └─────────────── stack <────────────────┘
                                     [ start,/,(,- ]

23. Moving 12 to the result list.

        (result expression in RPN)                       
                  [ 4,3,20,*,+,10,3,3,2,^,*,+,12 ]  (here we choose way)    [ ) ]
                  result <─────────────────────────────────── ? <───────────────── queue 
                      ^                                       │              (input expression)
                      │                                       │
                      │                                       │
                      │ (here operators are temporary stored) │
                      └─────────────── stack <────────────────┘
                                     [ start,/,(,- ]

24. Moving - from the stack to the result list.

        (result expression in RPN)                       
                [ 4,3,20,*,+,10,3,3,2,^,*,+,12,- ]  (here we choose way)    [ ) ]
                  result <─────────────────────────────────── ? <───────────────── queue 
                      ^                                       │              (input expression)
                      │                                       │
                      │                                       │
                      │ (here operators are temporary stored) │
                      └─────────────── stack <────────────────┘
                                     [ start,/,( ]

25. Removing ( from the stack and removing ) from the input queue.

        (result expression in RPN)                       
                [ 4,3,20,*,+,10,3,3,2,^,*,+,12,- ]  (here we choose way)    [ ]
                  result <─────────────────────────────────── ? <───────────────── queue 
                      ^                                       │              (input expression)
                      │                                       │
                      │                                       │
                      │ (here operators are temporary stored) │
                      └─────────────── stack <────────────────┘
                                     [ start,/ ]

26. Moving / from the stack to the result list.

        (result expression in RPN)                       
              [ 4,3,20,*,+,10,3,3,2,^,*,+,12,-,/ ]  (here we choose way)    [ ]
                  result <─────────────────────────────────── ? <───────────────── queue 
                      ^                                       │              (input expression)
                      │                                       │
                      │                                       │
                      │ (here operators are temporary stored) │
                      └─────────────── stack <────────────────┘
                                     [ start ]

Input infix expression: ( 4 + 3 * 20 ) / ( 10 + 3 * 3 ^ 2 - 12 ).
Result RNP expression: 4 3 20 * + 10 3 3 2 ^ * + 12 - /.

Several words about right-associated operators

Many programming languages have right-associative operators. Let us analyze using the example of the power operator.

2 ^ 2 ^ 3 = 2 ^ (2 ^ 3) = 256 (not 64!)

So, operations executes from right to the left.

Calculating RPN expression

Algorithm

The algorithm for calculating an expression in Reverse Polish notation using a stack is quite simple:

• If an operand is encountered, it must be put on the top of the stack.
• If an operator is encountered - you need to perform the specified operation.

To perform the operation, the last two operands are popped from the stack. Note, the number located at the top of the stack is the right-hand operand (not the left-hand one)! This is very important for such operations like division, subtraction and others, where the order of the operands is important.

Therefore, it is necessary to traverse all elements of the input expression.

If, after calculating the expression, more or less than one element remains on the stack - the input expression is not written correctly.

Execution example

Step	Remaining chain	Stack
1	4, 3, 20, *, +, 10, 3, 3, 2, ^, *, +, 12, -, /
2	3, 20, *, +, 10, 3, 3, 2, ^, *, +, 12, -, /	4.0
3	20, *, +, 10, 3, 3, 2, ^, *, +, 12, -, /	4.0, 3.0
4	*, +, 10, 3, 3, 2, ^, *, +, 12, -, /	4.0, 3.0, 20.0
5	+, 10, 3, 3, 2, ^, *, +, 12, -, /	4.0, 60.0
6	10, 3, 3, 2, ^, *, +, 12, -, /	64.0
7	3, 3, 2, ^, *, +, 12, -, /	64.0, 10.0
8	3, 2, ^, *, +, 12, -, /	64.0, 10.0, 3.0
9	2, ^, *, +, 12, -, /	64.0, 10.0, 3.0, 3.0
10	^, *, +, 12, -, /	64.0, 10.0, 3.0, 3.0, 2.0
11	*, +, 12, -, /	64.0, 10.0, 3.0, 9.0
12	+, 12, -, /	64.0, 10.0, 27.0
13	12, -, /	64.0, 37.0
14	-, /	64.0, 37.0, 12.0
15	/	64.0, 25.0
16		2.56

Result: 2.56

Credits

Author: Danil Andreev
Thanks for inspiration: agorkov (https://habr.com/ru/post/100869/)