Programmieraufgabe 108

Ich renne durchs Schulhaus und versuche die letzten Win 7-Leichen auf Win 10 zu aktualisieren und ersetze bzw. repariere nebenher noch den ein oder anderen Beamer oder stecke Kabel wie zurück. „Agile Schule“ hatte ich mir da irgendwie auch anders vorgestellt. Daher komme ich im Moment auch nicht weiter mit meiner Blogserie zum Thema „Agile Schule“.

Aber ich hatte eine kleine Idee für eine anspruchsvollere Programmieraufgabe für die elfte Klasse zum Thema Binärbaum, die ich unbedingt weitergeben wollte:

Aufgabe

Schreibe eine Programm, das einen einfachen mathematischen Term der Form „3+4*5“ einliest, in einen Binärbaum schreibt und durch einen inorder-Durchlauf auswertet.

Jetzt ist die Aufgabe zwar auf den ersten Blick vielleicht ganz überschaubar, aber es gibt den ein oder anderen Fallstrick, daher habe ich noch folgende Vereinfachungen angeboten:

  1. Es gibt nur Ziffern und nur die Operatoren *,+,-,/ . Das erlöst einen von dem Problem des Tokenizers. Also das Zerlegen eines Terms in logische Einheiten wie „<Zahl><Operator><Zahl><Operator><Zahl>“.
  2. Es gibt erstmal kein Punkt vor Strich.
  3. Im ersten Schritt müsste der Term eingelesen und ein Baum aufgebaut werden. Dabei könnte ich natürlich einfach von Vorne nach Hinten durchgehen. Dann hätte ich aber das Problem, dass ich eher einen entarteten Baum bekomme.
    Daher wäre wenigstens eine Art von Halbierungsverfahren sinnvoll: Ich suche die Mitte des Terms und wenn es ein Rechenzeichen ist, dann gehe ich rekursiv in die Teiläste.
  4. Habe ich den Baum aufgebaut, dann muss der Term ausgewertet werden. Hierzu wird wiederum ein Term aus dem Baum gewonnen und ausgewertet. Da das in JavaScript über die Funktion eval() recht leicht ist, habe ich meinen Schülern folgendes Codefragment gegeben:
    import javax.script.*;
    import java.io.StringWriter;
    static void evalMath() {
        ScriptEngine engine = new ScriptEngineManager().getEngineByName("javascript");
        ScriptContext context = engine.getContext();
        StringWriter writer = new StringWriter();
        context.setWriter(writer);
        try {
            engine.eval("print(3+2)");
        } catch (ScriptException ex) {}
        String output = writer.toString();
        System.out.println("Script output: " + output);
    }
    

Das Trennen in Einlesen und Wertberechnung, vor allem, wenn man letzteres nicht mit meinem Trick macht, wäre eine schöne Aufgabe für die Projektphase am Ende des 11. Klasse, die sich zwei Schüler auch teilen können. Man könnte im übrigen auch noch einen „zufälligen Rechenterm-Generator implementieren.  Ebenso könnte noch versucht werden Punkt-Vor-Strich und Klammer unterzubringen und natürlich „normale“ Zahlen und nicht nur Ziffern zu zu lassen. Aber dann wird es gleich anspruchsvoller. Zumindest beim Aufbau des Terms  – vielleicht wäre das Parsen beim Eintippen eine Alternative, vorausgesetzt man ignoriert Fehleingaben.

Kennt jemand im Übrigen eine „echte“ Lösung? Wie machen es zum Beispiel die Taschenrechner?

Schreib einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind mit * markiert.

Durch die weitere Nutzung der Seite (Scrollen, Navigieren) stimmen Sie der Verwendung von Cookies zu. Weitere Informationen

Die Cookie-Einstellungen auf dieser Website sind auf "Cookies zulassen" eingestellt, um das beste Surferlebnis zu ermöglichen. Wenn du diese Website ohne Änderung der Cookie-Einstellungen verwendest oder auf "Akzeptieren" klickst, erklärst du sich damit einverstanden.

Schließen