Analyse approfondie des quatre opérations arithmétiques

Comment calculer l'expression arithmétique de la chaîne ?

Si vous utilisez une expression régulière pour faire correspondre, c'est un peu impensable, et l'idée générale est de concevoir une récursion, mais en Python il est fortement déconseillé d'utiliser la récursion,

car elle a non seulement une limite sur la profondeur de récursion (généralement 1000 images de pile), mais ne prend pas non plus en charge l'optimisation de la récursion de queue.

Le moyen le plus simple est de convertir d'abord l'expression en une expression de préfixe, puis de calculer le résultat via l'expression de préfixe.

l'expression préfixe ( devant l'opérateur ) est également appelée expression polonaise, et l'expression postfixe correspondante (derrière l'opérateur) est également appelée expression polonaise inversée, et dans nos vies, et Les

les langages de programmation les plus courants utilisent des expressions infixes.

Les règles de conversion des expressions infixes en expressions préfixes :

　(1) Initialisez deux piles : la pile d'opérateurs S1 et la pile S2 qui stocke les résultats intermédiaires

　( 2) Scan ; l'expression infixe de droite à gauche

(3) Lorsque vous rencontrez l'opérande, poussez-le dans S2

(4) Lorsque vous rencontrez l'opérateur, comparez-le avec S1 La priorité du opérateur en haut de la pile  :

　(4-1) Si S1 est vide, ou si l'opérateur en haut de la pile est un crochet droit ")", poussez cet opérateur directement sur le stack

　(4-2) Sinon, si la priorité est supérieure ou égale à l'opérateur en haut de la pile, poussez l'opérateur dans S1

　(4-3) Sinon, poussez La S1 pile L'opérateur supérieur est sauté et poussé dans S2,

Allez à nouveau à (4-1) pour comparer avec le nouvel opérateur supérieur de pile dans S1

(5) Lorsque vous rencontrez des parenthèses ：

　 (5-1) S'il s'agit d'un support droit ")", poussez directement S1

(5-2) S'il s'agit d'un support gauche "(", faites sauter le haut du S1 empile dans l'opérateur de séquence et poussez S2 jusqu'à ce que le support droit soit rencontré,

À ce moment, jetez cette paire de supports

(6) Répétez les étapes (2) à (5) jusqu'à ce que Le côté le plus à gauche de l'expression

(7) Afficher les opérateurs restants dans S1 dans l'ordre et les pousser dans S2

(8) Extraire les éléments dans S2 dans l'ordre et les afficher, et le résultat est l'infixe. La plus grande caractéristique de l'utilisation d'expressions de préfixe pour le calcul est que

convertit les expressions d'infixe en expressions de préfixe

Exemple :

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

<. 🎜>

Il est simple d'utiliser la pile d'expressions de préfixes converties

(1) Initialiser une nouvelle liste

(2) Parcourez la liste d'expressions de préfixes de droite à gauche. numéro, enregistrez-le dans une nouvelle liste

(3) Lorsque vous rencontrez un opérateur, affichez les deux premiers numéros de la nouvelle liste et continuez l'opération, puis enregistrez le résultat dans la nouvelle liste

<. 🎜> (4) Jusqu'à ce que la liste d'expressions de préfixes soit parcourue dans la nouvelle liste, il n'y aura qu'un seul élément dans la nouvelle liste, qui est le résultat final

Obtenir le résultat total :

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

Exemple :

Le résultat de l'expression de préfixe précédente :

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)

Le résultat vérifié est correct

Remarque : L'expression doit être séparée par des espaces

seuls les entiers correspondent

.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!