Eingehende Analyse der vier Rechenoperationen

Wie berechnet man den arithmetischen Ausdruck einer Zeichenfolge?

Wenn Sie zum Abgleichen regulären Ausdruck verwenden, ist das etwas undenkbar, und die allgemeine Idee besteht darin, Rekursion zu entwerfen, aber in Python Es wird dringend davon abgeraten, Rekursion zu verwenden,

, da diese nicht nur eine Begrenzung der Rekursionstiefe hat (normalerweise 1000 Stapelrahmen), sondern auch keine Schwanzrekursionsoptimierung unterstützt.

Der einfachste Weg besteht darin, den Ausdruck zuerst in einen Präfixausdruck umzuwandeln und dann das Ergebnis über den Präfixausdruck zu berechnen.

Präfixausdruck ( vor Operator ) wird auch polnischer Ausdruck genannt, und der entsprechende Postfixausdruck (hinter dem Operator) wird auch umgekehrter polnischer Ausdruck genannt, und in unserem Leben , und

die häufigsten Programmiersprachenverwenden Infix-Ausdrücke.

Die Regeln zum Konvertieren von Infix-Ausdrücken in Präfix-Ausdrücke:

　(1) Initialisieren Sie zwei Stapel: Operatorstapel S1 und Stapel S2, der Zwischenergebnisse speichert;

　( 2) Scannen der Infix-Ausdruck von rechts nach links

(3) Wenn Sie auf den Operanden stoßen, schieben Sie ihn in S2

(4) Wenn Sie auf den Operator stoßen, vergleichen Sie ihn mit S1 Die Priorität von Operator oben im Stapel :

　(4-1) Wenn S1 leer ist oder der Operator oben im Stapel eine rechte Klammer „)“ ist, schieben Sie diesen Operator direkt auf Stapel

　(4-2) Andernfalls, wenn die Priorität höher oder gleich dem Operator oben auf dem Stapel ist, schieben Sie den Operator in S1

　(4-3) Andernfalls drücken Sie Der oberste Operator des S1-Stapels wird entnommen und in S2 verschoben.

Gehen Sie erneut zu (4-1), um ihn mit dem neuen obersten Stapeloperator in S1 zu vergleichen.

(5) Wenn Sie auf Klammern stoßen:

　 (5-1) Wenn es sich um eine rechte Klammer ") handelt, drücken Sie S1 direkt

(5-2) Wenn es sich um eine linke Klammer "(" handelt, öffnen Sie den oberen Teil der S1 stapelt den Sequenzoperator und drückt S2, bis die rechte Klammer gefunden wird.

Zu diesem Zeitpunkt verwerfen Sie dieses Klammerpaar.

(6) Wiederholen Sie die Schritte (2) bis (5), bis Die äußerste linke Seite des Ausdrucks

(7) Pop die verbleibenden Operatoren in S1 nacheinander ein und schiebe sie in S2

(8) Pop weg die Elemente in S2 nacheinander und gebe sie aus, und Das Ergebnis ist das Infix. Das größte Merkmal der Verwendung von Präfixausdrücken zur Berechnung besteht darin, dass

Infixausdrücke in Präfixausdrücke umwandelt

Beispiel:

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

Es ist einfach, den konvertierten Präfixausdrucksstapel zu bedienen

(1) Eine neue Liste initialisieren

(2) Durchlaufen Sie die Präfixausdrucksliste von rechts nach links Nummer, speichern Sie sie in einer neuen Liste

(3) Wenn Sie auf einen Operator stoßen, rufen Sie die ersten beiden Nummern in der neuen Liste auf, fahren Sie mit dem Vorgang fort und speichern Sie dann das Ergebnis in der neuen Liste

(4) Bis die Präfixausdrucksliste in der neuen Liste durchlaufen wird, gibt es nur ein Element in der neuen Liste, nämlich das Endergebnis

Erhalten Sie das Gesamtergebnis:

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

Beispiel:

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)

Das vorherige Ergebnis des Präfixausdrucks:

Das überprüfte Ergebnis ist korrekt

Hinweis: Der Ausdruck muss durch Leerzeichen getrennt werden

es werden nur ganze Zahlen abgeglichen

.

Das obige ist der detaillierte Inhalt vonEingehende Analyse der vier Rechenoperationen. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!