Aus Das deutschsprachige Scratch-Wiki
Dieses Tutorial lehrt wie man einen Ausdruck auswertet.
Den benutzerdefinierten Block erstellen
Diese Implementierung enthält nur instabile Unterstützung für Funktionen und gar keine unäre Negation. Deswegen muss man -5 * 10 zu (0-5) * 10 ändern.
Variablen
Man braucht folgende Variablen:
(i)(letzter token)(token)(zeichen)(ergebnis)
Man braucht auf folgende Listen:
(warteschlange::list)(stapel::list)(tokens::list)
Und mache eine Liste "Operatoren" mit genau diesen Zeichen in genau dieser Reinfolge:
- -
- +
- /
- *
- √
Dies ist wichtig, wegen Punkt vor Strich.
Kompletter Benutzerdefinierter Block
Definiere Werte (Ausdruck :: custom-arg) aus
setze [i v] auf (1) // Tokenisierung des Ausdrucks
lösche alles aus [tokens v]
wiederhole (Länge von (Ausdruck :: custom-arg)) mal
setze [zeichen v] auf (Zeichen (i) von (Ausdruck :: custom-arg))
setze [letzter token v] auf (Element (Länge von [tokens v]) von [tokens v])
falls <(123456.7890) enthält (zeichen) ?> , dann
falls <<((letzter token) / (1)) = (last token)> oder <(last token) = [.]>> , dann
ersetze Element (Länge von [tokens v]) von [tokens v] durch (verbinde (letzter token) und (zeichen))
sonst
füge (zeichen) zu [tokens v] hinzu
end
sonst
falls <[()+-/*√] enthält (zeichen) ?> , dann
füge (zeichen) zu [tokens v] hinzu
end
end
ändere [i v] um [1]
end
lösche alles aus [stapel v] // Sortierung der Operationen (Punkt vor Strich, Klammer usw.) und wechselung von Infix zu Postfix
lösche alles aus [warteschlange v]
setze [i v] auf (1)
wiederhole (Länge von [tokens v]) mal
setze [token v] auf (Element (i) von [tokens v])
falls <((token) / (1)) = (token)> , dann
füge (token) zu [warteschlange v] hinzu
end
falls <[operatoren v] enthält (token) ?> , dann
wiederhole bis <<<(Element (1) von [stapel v]) = [(]> oder <(Länge von [stapel v]) = [0]>> oder <(Nummer von (Element (1) von [stapel v]) in [operatoren v]) < (Nummer von (token) in [operatoren v])>>
füge (Element (1) von [stapel v]) zu [warteschlange v] hinzu
lösche (1) aus [stapel v]
end
füge (token) bei (1) in [stapel v] ein
end
falls <(token) = [(]> , dann
füge (token) bei (1) in [stapel v] ein
end
falls <(token) = [)]> , dann
wiederhole bis <<(Element (1) von [stapel v]) = [(]> oder <(Länge von [stapel v]) = [0]>>
füge (Element (1) von [stapel v]) zu [warteschlange v] hinzu
lösche (1) aus [stapel v]
end
falls <(Element (1) von [stapel v]) = [(]> , dann
lösche (1) aus [stapel v]
end
end
ändere [i v] um (1)
end
wiederhole bis <(Länge von [stapel v]) = (0)>
füge (Element (1) von [stapel v]) zu [warteschlange v] hinzu
lösche (1) aus [stapel v]
end
wiederhole bis <(Länge von [warte schlange v]) = [0]>
setze [token v] auf (Element (1) von [warteschlange v])
lösche [1] aus [warteschlange v]
falls <[operatoren v] enthält (token) ?> , dann
falls <(token) = [+]> , dann
füge ((Element [2] von [stapel v]) + (Element [1] von [stapel v])) bei [1] in [stapel v] ein
end
falls <(token) = [-]> , dann
füge ((Element [2] von [stapel v]) - (Element [1] von [stapel v])) bei [1] in [stapel v] ein
end
falls <(token) = [/]> , dann
füge ((Element [2] von [stapel v]) / (Element [1] von [stapel v])) bei [1] in [stapel v] ein
end
falls <(token) = [*]> , dann
füge ((Element [2] von [stapel v]) * (Element [1] von [stapel v])) bei [1] in [stapel v] ein
end
falls <(token) = [√]> , dann // Unärer Operator
füge ([Wurzel v] von (Element [1] von [stapel v])) bei [1] in [stapel v] ein
füge () bei [2] in [stapel v] ein //Füge ein Dummy ein, damit die andere Nummer nicht gelöscht wird, der Token darf nur ein Charakter lang sein. Dieser Weg Funktionen und Unäre Negation einzubauen ist instabil, es wird vorgeschlagen, einen besseren parser zu benutzen.
end
lösche [2] aus [stapel v]
lösche [2] aus [stapel v]
sonst
füge (token) bei (1) in [stapel v] ein
end
end // Löse die Schlange auf
setze [ergebnis v] auf (Element [1] von [stapel v]) // Das Ergebnis ist in der Variable "ergebnis"
Erklärung
Das Problem der Auswertung eines Ausdrucks kann in 3 Schritte unterteilt werden:
- Tokenisierung des Ausdrucks (Umwandlung der Eingabe in eine Liste von Symbolen und Zahlen)
- Umwandlung der Token in das Postfix-Format (wobei der Operator hinter den 2 Operanden steht)
- Auswertung des Postfix-Ausdrucks mit einer Stapelmaschine (Berechnung der Antwort)
Tokenisierung des Ausdrucks
Der Ausdruck muss zunächst in eine Liste umgewandelt werden. Jede Zahl muss alle ihre Ziffern in demselben Listenelement haben.
Dieses Skript tokenisiert einen Ausdruck.
setze [i v] auf (1)
lösche alles aus [tokens v]
wiederhole (Länge von (Ausdruck :: custom-arg)) mal
setze [zeichen v] auf (Zeichen (i) von (Ausdruck :: custom-arg))
setze [letzter token v] auf (Element (Länge von [tokens v]) von [tokens v])
falls <(123456.7890) enthält (zeichen) ?> , dann
falls <<((letzter token) / (1)) = (last token)> oder <(last token) = [.]>> , dann
ersetze Element (Länge von [tokens v]) von [tokens v] durch (verbinde (letzter token) und (letter))
sonst
füge (zeichen) zu [tokens v] hinzu
end
sonst
falls <[()+-/*] enthält (zeichen) ?> , dann
füge (zeichen) zu [tokens v] hinzu
end
end
ändere [i v] um [1]
end
Umwandlung der Token in das Postfix-Format
Zunächst wird der Shunting yard Algorithmus verwendet, um die Token von Infix (A op B) in Postfix (A B op) umzuwandeln. Dies geschieht, weil die Berechnung eines Postfix-Ausdrucks viel weniger Code erfordert als die eines Infix-Ausdrucks.
Dieses Skript lässt den Shunting yard Algorithmus auf der Tokenliste laufen:
 Information: |
lösche alles aus [stapel v]
lösche alles aus [warteschlange v]
setze [i v] auf (1)
wiederhole (Länge von [tokens v]) mal
setze [token v] auf (Element (i) von [tokens v])
falls <((token) / (1)) = (token)> , dann
füge (token) zu [warteschlange v] hinzu
end
falls <[operatoren v] enthält (token) ?> , dann
wiederhole bis <<<(Element (1) von [stapel v]) = [(]> oder <(Länge von [stapel v]) = [0]>> oder <(Nummer von (Element (1) von [stapel v]) in [operatoren v]) < (Nummer von (token) in [operatoren v])>>
füge (Element (1) von [stapel v]) zu [warteschlange v] hinzu
lösche (1) aus [stapel v]
end
füge (token) bei (1) in [stapel v] ein
end
falls <(token) = [(]> , dann
füge (token) bei (1) in [stapel v] ein
end
falls <(token) = [)]> , dann
wiederhole bis <<(Element (1) von [stapel v]) = [(]> oder <(Länge von [stapel v]) = [0]>>
füge (Element (1) von [stapel v]) zu [warteschlange v] hinzu
lösche (1) aus [stapel v]
end
falls <(Element (1) von [stapel v]) = [(]> , dann
lösche (1) aus [stapel v]
end
end
ändere [i v] um (1)
end
wiederhole bis <(Länge von [stapel v]) = (0)>
füge (Element (1) von [stapel v]) zu [warteschlange v] hinzu
lösche (1) aus [stapel v]
end
Berechnen des Ergebnisses mit einer Stapelmaschine
Dieses Skript berechnet das Ergebnis des Postfix-Ausdrucks:
wiederhole bis <(Länge von [warte schlange v]) = [0]>
setze [token v] auf (Element (1) von [warteschlange v])
lösche [1] aus [warteschlange v]
falls <[operatoren v] enthält (token) ?> , dann
falls <(token) = [+]> , dann
füge ((Element [2] von [stapel v]) + (Element [1] von [stapel v])) bei [1] in [stapel v] ein
end
falls <(token) = [-]> , dann
füge ((Element [2] von [stapel v]) - (Element [1] von [stapel v])) bei [1] in [stapel v] ein
end
falls <(token) = [/]> , dann
füge ((Element [2] von [stapel v]) / (Element [1] von [stapel v])) bei [1] in [stapel v] ein
end
falls <(token) = [*]> , dann
füge ((Element [2] von [stapel v]) * (Element [1] von [stapel v])) bei [1] in [stapel v] ein
end
falls <(token) = [*]> , dann
füge (([Wurzel v] von (Element [1] von [stapel v])) ) bei [1] in [stapel v] ein
end
lösche [2] aus [stapel v]
lösche [2] aus [stapel v]
sonst
füge (token) bei (1) in [stapel v] ein
end
end // Löse die Schlange auf
setze [ergebnis v] auf (Element [1] von [stapel v])
Wie man den Block benutzt
Wenn die grüne Flagge angeklickt werte [5 + 5] aus :: custom sage (ergebnis)
Wenn es funktioniert hat, sollte die Figur die Nummer 10 anzeigen.
Demo
Code zum Einbinden ins Forum:
[wiki=de:Mathematische Ausdrücke auswerten]Mathematische Ausdrücke auswerten[/wiki]
[wiki=de:Mathematische Ausdrücke auswerten]Mathematische Ausdrücke auswerten[/wiki]
