Das ist auch schon mein letzter Blog-Eintrag zu unserem kleinen Projekt. Wir haben uns auch überlegt, wie wir die Funktionen auf dem Brick kriegen. Da kamen uns direkt einige Ideen, wie einen Discord-Bot zu programmieren, aber wir brauchten erstmal schnell etwas um unseren Roboter zu testen. Zwar könnten wir einfach vordefinierte Funktionen nehmen, die waren uns aber wieder zu einfach, also programmierte ich einen Parser. Ein Parser konvertiert eine Abfolge von Zeichen und fügt sie in eine für den Computer verständlichen Struktur, bei uns dem Binärbaum. Analog zum Vergleich am Anfang des Blogs ist der Parser sowas wie das Rezept, das sagt wie die Zutaten kombiniert werden müssen.
Shunting-yard-Algorithmus
Der Shunting-yard-Algorithmus ist in der Lage ein Term in der Infixnotation (für uns gängige Notation, z.B. 2 + 4) in die umgekehrte polnische Notation / in einen BET zu überführen. Die umgekehrte polnische Notation (RPN) sieht etwas anders aus, und zwar kommen hier erst Operanden (also Zahlen und Variablen) und erst dann die Operatoren. Ein Beispiel wäre „2 4 +“ (was dem obigen Beispiel entspricht). Wichtig dabei ist dabei ein Trennzeichen zwischen Zahlen. Eine weitere Besonderheit ist, dass diese Schreibweise keine Klammern benötigt:
| Infix | Postfix / RPN |
|---|---|
| (3+4)×5 | 3 4 + 5 * |
| sin(2x) | 2 x * sin |
Außerdem kann ein Computer ziemlich gut sogar mit so welchen Ausdrücken arbeiten. Man geht dafür Token für Token durch und legt die Operanden auf einen Stapel. Kommt ein Operator, nimmt sich dieser seine benötigte Anzahl an Operanden vom Stapel, verrechnet sie und legt das Ergebnis auf den Stapel. Am Ende sollte eine einzige Zahl auf dem Stapel liegen. Das konnten wir leider nicht in unserem Projekt uns zu Nutze machen, da die Ableitung wahrscheinlich wieder sehr komplex / unmöglich ist.
Zurück zum Thema: Also wir haben den Tokenizer + Shunting-yard-Algorithmus implementiert und irgendwie hat er nur so halb funktioniert, bzw. ich war nicht zufrieden wie er mit negativen Zahlen umgegangen ist (gar nicht). Da blieben mir letztendlich nur zwei Optionen: Den Algorithmus so umschreiben, dass er negative negative Zahlen akzeptiert oder einen neuen Parser schreiben. Fragt mich nicht, warum ich mich dazu entschieden hab einen komplett neuen Parser zu schreiben. Auch nicht warum ich mich für einen Recursive Descent Parser entschieden hab. Im Endeffekt hat er zwar funktioniert, ist aber kompletter Overkill. Bis heute habe ich den Algorithmus nur zur Hälfte verstanden, aber wer sich für Grammatik und LL(1) top-down parsing interessiert, mir hat dieses 30 minütige Video sehr geholfen.
App
Da der Algorithmus von gerade nicht schon kompliziert genug ist, haben wir uns letztlich dazu entschieden, eine App zur Übertragung der Funktionen zu programmieren. Dafür benutze ich das Dart-Framework Flutter von Google, was sehr leicht zu erlernen ist und auch ein sehr viel Spaß macht. :]
Verbindung
Am Anfang wollte ich eine Bluetooth-Verbindung zwischen App und Brick herstellen, dabei gab es aber sämtliche Kompabilitätsprobleme: Der Brick unterstützt nur Bluetooth 2.1 während die Software die wir darauf installiert haben keine wirkliche Implementierung dafür bereitstellt, sondern nur das aktuelle Bluetooth Low Energy. Also entschied ich mich für eine Wifi-Verbindung über TCP, dem Standardprotokoll für Transport. Um jetzt loszulegen müssen Handy und Brick im gleichen Netzwerk sein, dann drückt man einfach auch „Connect to Brick“, wählt die IP-Adresse und Bricks und schon ist man verbunden.
Man kann sich letztendlich nur mit Geräten verbinden, bei dem auch ein Server auf dem richtigen Port läuft.
Eingeben der Funktion
Am Anfang musste man noch Funktionen mit so eintippen wie man es hier auch tun würde, doch dann habe eine großartige Library namens „math_keyboard“ gefunden, die eine interaktive Möglichkeit bietet Funktionen mit einer speziellen Tastatur zu bilden.
Hier könnt ihr es auch direkt selbst ausprobieren.
Das tolle an der Library ist auch das ich mir die Funktion direkt als Reverse Polish Notation ausgeben kann. Und die kann man genauso einfach in ein Baum überleiten wie sie auszurechnen, in dem man statt dem Ergebnis ein Node mit dem Operanden auf den Stapel legt. Das macht traurigerweise die tollen Parser die ich geschrieben habe redundant.
Fazit
Erstmal herzlichen Glückwunsch, du hast bis zu dem Ende des Blogs geschafft. Daher hoffe ich das du zumindest irgendwas mitnehmen konntest und den kleinen Einblick in den Robotikkurs 2021/2022 interessant fandst.
Dieser Kurs bleibt auf jeden Fall ein einmaliges Schulerlebnis für mich: Ein Jahr, 10 Schüler und ein selbstständiges Projekt. Der Moment, so lange an etwas zu arbeiten und dann zu sehen, wie der kleine Roboter für dich arbeitet macht einen einfach verdammt glücklich. Die Möglichkeit sich seine Zeit selbst einzuteilen ist so unfassbar cool und hat mir definitiv geholfen selbstständiger zu arbeiten. Ein weiterer Faktor war die Kommunikation: Am Anfang denkt man schon ach das klappt schon, bis einem dann auffällt das man sich einige Male in die Quere kommt, weil dein Partner denkt ein Legoprodukt muss modular sein, koste es was wolle. Am Ende ist zum Glück nochmal alles gutgegangen.
Auch wenn das Zeichnen am Ende nicht genau unseren Vorstellungen entsprachen hatte ich sehr viel Spaß, alleine in die verschiedenen Teile der Softwareentwicklung/Informatik (Technik/Motoren, App-Entwicklung, TCP/IP, Binärbäume, Parser) reinzuschnuppern und diese auch Verbinden um ein Produkt zu entwickeln ist etwas was ich noch nie vorher gemacht hab. So ein Lego-Roboter hat man ja nicht einfach zu Hause rumliegen.