In-depth analysis of the four arithmetic operations

How to calculate the arithmetic expression of a string?

If you use regular expression to match, it is a bit unthinkable, and the general idea is to recursion, but in Python it is It is highly not recommended to use recursion,

because it not only has a limit on the recursion depth (usually 1000 stack frames), but also does not support tail recursion optimization.

The simplest way is to first convert the expression into a prefix expression, and then calculate the result through the prefix expression.

The prefix expression (in front of operator ) is also called Polish expression, and the corresponding suffix expression (in the back of operator) is also called reverse Polish expression, and in our lives , and

Commonly used in most programming languages are infix expressions.

Rules for converting infix expressions into prefix expressions:

　(1) Initialize two stacks: operator stack S1 and stack S2 that stores intermediate results;

　( 2) Scan the infix expression

from right to left. (3) When the operand is encountered, push it into S2

. (4) When the operator is encountered, compare it with S1. The priority of the operator on the top of the stack:

　(4-1) If S1 is empty, or the operator on the top of the stack is a right bracket ")", push this operator directly onto the stack

　(4-2) Otherwise, if the priority is higher or equal to the operator on the top of the stack, push the operator into S1

　(4-3) Otherwise, push S1 onto the stack The top operator is popped and pushed into S2,

Go to (4-1) again to compare with the new top operator in S1

(5) When encountering parentheses ：

　(5-1) If it is a right bracket ")", push S1

directly. (5-2) If it is a left bracket "(", pop up the top of S1 stack one by one operator, and push S2 until the right bracket is encountered,

At this time, discard this pair of brackets

(6) Repeat steps (2) to (5) until The leftmost

of the expression　(7) Pop the remaining operators in S1 one by one and push them into S2

　(8) Pop the elements in S2 one by one and output them, the result is the infix The prefix expression corresponding to the expression.

The biggest feature of using prefix expressions is that it removes the parentheses

Convert the infix expression into a prefix expression

def mid_to_prev(expressions: str):
    priority = {  # 运算符的优先级
        "/": 1,
        "//": 1,
        "*": 1,
        "%": 1,
        "+": 0,
        "-": 0,
        "**": 2 }
    expression_list = expressions.split() # 
    number_stack = [] # 数字栈
    symbol_stack = [] # 运算符栈
    for x in expression_list[::-1]:
        if x.isdigit():             
            number_stack.insert(0, x)  # 如果是整数直接存进去
        else:
            if x == '(':         # 如果是 ( 弹出运算符栈中的运算符直到遇到 ( 
                pop_symbol = symbol_stack[0]
                while pop_symbol != ')':
                    pop_symbol = symbol_stack.pop(0)
                    number_stack.insert(0, pop_symbol)
                    pop_symbol = symbol_stack[0]
                else:
                    symbol_stack.pop(0)
            elif len(symbol_stack) == 0 or symbol_stack[0] == ')' or x == ')' or priority[x] >= priority[symbol_stack[0]]:
                symbol_stack.insert(0, x)  # 当符号栈为空 或者 遇到 ) 或者栈顶的符号是 ) 或者优先级大于等于符号栈顶的运算符优先级 直接存进去

            elif priority[x] < priority[symbol_stack[0]]:  # 优先级小于符号栈顶元素的时候
                while symbol_stack[0] != &#39;)&#39; and priority[x] < priority[symbol_stack[0]]:
                    number_stack.insert(0, symbol_stack.pop(0))
                else:
                    symbol_stack.insert(0, x)
    else:
        while len(symbol_stack) != 0:
            number_stack.insert(0, symbol_stack.pop(0))
    return number_stack

##. #Example:

It is simple to operate the converted prefix expression stack

(1)Initialize a new list

(2) Traverse the prefix expression list from right to left. When encountering a number, store it in a new list

(3) When encountering an operator, pop up the first two numbers in the new list and perform operations. Then save the result to the new list

(4) Until the prefix expression list is traversed in the new list, there is only one element in the new list, which is the final result

def calc(number1,number2,calc): # 两个数运算
    if calc == '/':
        return number1 / number2
    elif calc == '*':
        return number1 * number2
    elif calc == '//':
        return number1 // number2
    elif calc == '**':
        return number1 ** number2
    elif calc == '%':
        return number1 % number2
    elif calc == '+':
        return number1 + number2
    elif calc == '-':
        return number1 - number2

obtained Total result:

def operation(stack_list:list):
    number = []
    for x in stack_list[::-1]:
        if x.isdigit():
            number.insert(0, x)
        else:
            first = number.pop(0)
            second = number.pop(0)
            tmp = calc(int(first),int(second), x)
            number.insert(0,tmp)
    return number.pop(0)

Example:

Previous prefix expression result:

The verified result is correct.

Note: The expression must be separated by spaces

Only integers are matched

The above is the detailed content of In-depth analysis of the four arithmetic operations. For more information, please follow other related articles on the PHP Chinese website!