(Python) Principles and implementation of calculator using stack

Preface

How do we implement calculations in our daily calculator? How can you determine the priority of operators by yourself and handle the matching of brackets?

A well-known answer is to use a stack. OK, so why use a stack? Why can the stack be implemented?

(Previous|Medium|Post) suffix expression?

What we are most familiar with is our infix expression, that is, shape1 + 3 * 2Such an equation means that the operator is located between operands.

From a similar concept, it is not difficult to get the prefix expression+ 1 * 3 2(operator is before operand), the suffix expression is1 3 2 * +

Prefix expressionAlso known as Polish notation (Polish notation, or Polish notation).Suffix expressionIt is called Reverse Polish notation (RPN, or reverse Polish notation).

What we input to the calculator is our infix expression. Because the infix expression can only be calculated one by one in order, the judgment of the priority of the operator cannot be realized. Therefore, a common operation is to convert the infix expression to a suffix expression (which can determine the priority of the operation), and then let our calculator perform the calculation.

The implementation of the process of infix to suffix is ​​very simple, that is,Operator priority stack：

1. Initialize an empty stack, used to store operators (+、-、*、/etc.), and initialize an empty output queue (used to store the results of the suffix expression).

2. Scan the infix expression from left to right, process each character one by one:

   • in the case ofOperands(such as numbers), directly join the output queue.

   • in the case ofLeft bracket（(), directly pressed into the stack.

   • in the case ofClose bracket（)), then the top-stack operator is popped up and added to the output queue in turn until the left bracket is encountered (the left bracket is out of the stack but not the output queue).

   • in the case ofOperators（+、-、*、/etc.), then:

     • If the stack is empty, directly push it into the stack.

     • If the stack is not empty, compare the priority of the current operator with the top-stack operator:

       • If the current operator's priority isAboveThe top-stack operator is directly pushed into the stack.
       • If the current operator's priority isLess than or equal toThe top-stack operator, pop up the top-stack operator in turn and add the output queue until the stack is empty or the priority of the top-stack operator is lower than the current operator, and then push the current operator into the stack.

3. After the scan is finished, If there are still operators in the stack, pop up and join the output queue in turn.

4. The content in the output queue is the suffix expression。

   The priority of operators is determined without brackets.* / > + -

   Follow the same levelFrom left to rightOrder of

Take the easiest1 + 3 * 2 - 5Give an example

The reason for using a suffix expression is that it only requires a scan from left to right, and the time complexity of each operation is only required\(O(1)\), for length\(n\)The calculation complexity of the expression and the suffix expression is\(O(n)\), and to say, this expression is not ambiguity for computers, has clear priorities, and is easy to implement.

Calculator implementation logic

Overall implementation logic

Then the implementation logic of the calculator can be written as follows:

Infix expression to suffix expression

If we have the expression as follows:

expression = "1-2*((60-30+(-40/5)*(9-2*5/3+7/3*99/4*2998+10*568/14))-(-4*3)/(16-3*2))"

Infix expressions to suffix expressions are solved by our favorite regular expressions.

1. ​\d+\.\d+​: Match the fractional part.
2. ​\d+​: Match the integer part.
3. ​[+\-*/()]​: Match operators and brackets.

What, what to do if there are negative numbers, how to follow it-distinguish? Mark it out and deal with it separately, for example,u-Indicates a negative sign.

How to mark it? There are only two situations where the minus sign appears:

1. The beginning of the expression
2. Following the previous operator

In this way, the analytical problem will be solved easily.

import re
 def infix_expression2suffix_expression(infix_expression):
     precedence = {'+': 1, '-': 1, '*': 2, '/': 2, '(': 0, 'u-': 3}
     op_stack = []
     suffix_expression = []
     # Match decimals, integers and operators
     tokens = (r'\d+\.\d+|\d+|[+\-*/()]', infix_expression)
     print(tokens)
  
     for i, token in enumerate(tokens):
         if (r'\d+\.\d+|\d+', token): # If it is a number
             suffix_expression.append(token)
         elif token == '(': # If it is the left bracket
             op_stack.append(token)
         elif token == ')': # If it is a close bracket
             while op_stack and op_stack[-1] != '(':
                 suffix_expression.append(op_stack.pop())
             op_stack.pop() # pop up the left bracket
         else: # If it is an operator
             # Handle negative signs (negative numbers), beginning of expression, after the previous operator
             if token == '-' and (i == 0 or tokens[i - 1] in "+-*/("):
                 token = 'u-' # Mark as negative sign
             while op_stack and (token, 0) <= (op_stack[-1], 0):
                 suffix_expression.append(op_stack.pop())
             op_stack.append(token)
     # Add the remaining operators on the pop-up operator stack to the suffix expression
     while op_stack:
         suffix_expression.append(op_stack.pop())
     print("Suffix expression:", " ".join(suffix_expression))
     return " ".join(suffix_expression)

 if __name__ == '__main__':
     infix_expression = expression
     suffix_expression = infix_expression2suffix_expression(infix_expression)
     print("Suffix expression:", suffix_expression)

Calculate the result of the suffix expression

How to calculate the result of a suffix expression? Scan from left to right, push the number into the stack when encountering a number, and then run it when encountering an operator, which is simple and trouble-free.

If there is a negative number, you just need to take out the negative sign and then push it back to the stack.

import re
def evaluate_suffix_expression(suffix_expression):
    stack = []
    tokens = suffix_expression.split()
    print(tokens)
    for token in tokens:
        if (r'\d+\.\d+|\d+', token):
            (float(token))
        elif token == 'u-':
            (-())
        else:
            operand2 = ()
            operand1 = ()
            if token == "+":
                (operand1 + operand2)
            elif token == "-":
                (operand1 - operand2)
            elif token == "*":
                (operand1 * operand2)
            elif token == "/":
                (operand1 / operand2)
            else:
                raise ValueError("Invalid operator: " + token)
            print(f'{operand1} {token} {operand2} = {stack[-1]}')
    if len(stack) != 1:
        raise ValueError("Invalid expression: " + suffix_expression)
    return stack[0]
if __name__ == "__main__":
    print(evaluate_suffix_expression(infix_expression2suffix_expression(expression)))

Overall implementation of computing

Next, encapsulate the above implementation process together and you can implement the calculator without any burden.

def evaluate(expression):
    return evaluate_suffix_expression(infix_expression2suffix_expression(expression))
if __name__ == '__main__':
    expression = input("Enter an infix expression: ")
    print(evaluate(expression))

Further simplification

What we did before is to convert the infix expression to the suffix expression, and then use the suffix expression to calculate the result. In this process, two stacks of numbers and operator stacks are required.

So, can we operate while reading? sure. The suffix expression directly displays the order of operations, so the process of obtaining the suffix expression is actually the process of operations.

import re

 def evaluate_expression(expression):
     def four_rules_eval(sum_stack, op_stack):
         op = op_stack.pop()
         if op == 'u-':
             operand = sum_stack.pop()
             sum_stack.append(-operand)
             print(f'u-{operand} = {sum_stack[-1]}')
         else:
             operand2 = sum_stack.pop()
             operand1 = sum_stack.pop()
             if op == "+":
                 sum_stack.append(operand1 + operand2)
             elif op == "-":
                 sum_stack.append(operand1 - operand2)
             elif op == "*":
                 sum_stack.append(operand1 * operand2)
             elif op == "/":
                 sum_stack.append(operand1 / operand2)
             else:
                 raise ValueError("Invalid operator: " + op)
             print(f'{operand1} {op} {operand2} = {sum_stack[-1]}')
  
     precedence = {'+': 1, '-': 1, '*': 2, '/': 2, '(': 0, 'u-': 3}
     op_stack = []
     sum_stack = []
     tokens = (r'\d+\.\d+|\d+|[+\-*/()]', expression)
     print(tokens)
  
     for i, token in enumerate(tokens):
         if (r'\d+\.\d+|\d+', token): # If it is a number
             sum_stack.append(float(token))
         elif token == '(': # If it is the left bracket
             op_stack.append(token)
         elif token == ')': # If it is a close bracket
             while op_stack and op_stack[-1] != '(':
                 four_rules_eval(sum_stack, op_stack)
             op_stack.pop() # pop up the left bracket
         else: # If it is an operator
             # Handle negative signs (negative numbers), beginning of expression, after the previous operator
             if token == '-' and (i == 0 or tokens[i - 1] in "+-*/("):
                 op_stack.append('u-')
             else:
                 while op_stack and (token, 0) <= (op_stack[-1], 0):
                     four_rules_eval(sum_stack, op_stack)
                 op_stack.append(token)
     while op_stack:
         four_rules_eval(sum_stack, op_stack)
     return sum_stack[-1]

 if __name__ == '__main__':

     expression = "1-2*((60-30+(-40/5)*(9-2*5/3+7/3*99/4*2998+10*568/14))-(-4*3)/(16-3*2))"
     result = evaluate_expression(expression)
     print(result) # out: 2776672.6952380957

References

Prefix expressions, infix expressions, and suffix expressions:/zzliu/p/