Rangierbahnhof
Wie Compiler und Interpreter Formeln auswerten
Ein Computer kann auch komplexeste Formeln in Nullkommanichts ausrechnen. Dazu überführt er die einzelnen Operationen in eine spezielle Struktur. Ein Streifzug durch Infix- und Postfix-Notation sowie Operatoren, Stacks, Queues und den Shunting-Yard-Algorithmus.
Der in c’t 16/2019 vorgestellte Arbitrary Precision Calculator (APC) ist einen Rechner für den Browser, der mit beliebig großen Ganzzahlen umgehen kann, und das nicht nur im Dezimalsystem, sondern auch im Binär-, Oktal- und Hexadezimalsystem [1]. Er beherrscht die Grundrechenarten, bitweise Operationen, geklammerte Terme und ein paar Funktionen wie größter gemeinsamer Teiler (ggT), kleinstes gemeinsames Vielfaches (kgV) und Quadratwurzelziehen. Darüber hinaus kann er Variablen verarbeiten, sodass man wiederkehrende oder bereits berechnete Werte nicht erneut eintippen muss, sondern über Namen wie x oder theta wiederverwenden kann (Demo unter 607011.github.io/bincalc).
Was wir in dem Artikel nicht erklärten, können Sie im Folgenden lesen: wie der Arbitrary Precision Calculator die eingetippten Formeln so unter Berücksichtigung der Operatorenrangfolge (lies: Punkt vor Strich, höchste Priorität für Klammern) in ihre Bestandteile zerlegt, dass er sie bequem durchrechnen kann. Dazu bedient er sich des sogenannten Shunting-Yard-Algorithmus. Shunting Yard ist das englische Wort für Rangierbahnhof, und tatsächlich erinnert das Verfahren daran, wie Zugteile von einem Gleis zum anderen verschoben werden.