# Ausdrucksparser für Mathematische Ausdrücke



## Todo (26. Mai 2010)

Hi @ all,

ich soll für die FH einen Mathe Parser schreiben, ich habe vier Testfälle, Exceptions für ungültige Ausdrücke wollte ich erst schreiben wenn die gültigen Funktionieren, die ersten drei Testfälle funktionieren auch, aber das letzte Funktioniert nicht.

Bei dem Ausdruck "1 + 2 * ( i + 2 * k - 1 ) / 2 + j" mit i = 3, k = 4 und j = 9 berechnet mein Parser 30, anstatt 20. 
Vielleich kann jemand einmal drüber gucken und mir den Fehler sagen.

Gucke nämlich schon seit 3 Tagen drüber und bin irgendwie zu blind um es zu sehen.

Danke schonmal.

Hier der Quelltext:
Der Parser

```
import java.util.ArrayList;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

/**
 * Klasse zum Parsen.
 *
 */
public class Parser {

    /** Arrayliste fuer die einzelnen Tokens. */
    private ArrayList<String> tokenListe = new ArrayList();

    /** Objekt der den vorherigen geparsten Ausdruck speichert */
    private Ausdruck vorheriger;

    /** Speichert das geparste Ergebnis */
    private Ausdruck ergebnis;

    /** Instantzvariable zum Speichern des Index */
    private int parserIndex = 0;

    /**
     * Methode zum Parsen eines Ausdrucks.
     *
     * @param infixdarstellung Infixdarstellung die geparst werden soll.
     *
     * @return der geparste Ausdruck.
     */
    public Ausdruck parse(String infixdarstellung) {
        /* Initaliesiert die Arrayliste der einzelnen Tokens. */
        initArrayListe(infixdarstellung);

        /* Variable zum Speichern des geparsten Ausdruck */
        Ausdruck geparsterAusdruck = null;

        /*
         * Durchläuft jedes Token solange der ParserIndex kleiner
         * der groeße der TokenListe ist.
         */
        while(parserIndex < tokenListe.size()) {
        
            geparsterAusdruck = parseAusdruck(parserIndex);
            vorheriger = geparsterAusdruck;
            parserIndex++;
            }
        
        return geparsterAusdruck;
    }

    /**
     * Parst einen Summand oder eine Folge von Summanden die mit '+'
     * oder '-' verbunden sind.
     *
     * @return geparster Ausdruck fuer Summanden.
     */
    private Ausdruck parseAusdruck(int index) {
        ergebnis = parseSummand(index);
        if (tokenListe.get(index).equalsIgnoreCase("+")) {
            parserIndex++;
            ergebnis = new OperatorAusdruck
                    (vorheriger, '+',
                    parseAusdruck(index + 1));
        }

        else if (tokenListe.get(index).equalsIgnoreCase("-")) {
            parserIndex++;
            ergebnis = new OperatorAusdruck
                    (vorheriger, '-',
                    parseAusdruck(index + 1));
        }
        return ergebnis;
    }

    /**
     * Parst einen Faktor oder eine Folge von Faktoren die mit '*'
     * oder '/' verbunden sind.
     *
     * @return geparster Ausdruck fuer Faktoren.
     */
    private Ausdruck parseSummand(int index) {
        ergebnis = parseFaktor(index);

        if (tokenListe.get(index).equalsIgnoreCase("*")) {
            parserIndex++;
            ergebnis =  new OperatorAusdruck
                    (vorheriger, '*',
                    parseAusdruck(index + 1));
        }

        else if (tokenListe.get(index).equalsIgnoreCase("/")) {
            parserIndex++;
           ergebnis =  new OperatorAusdruck
                    (vorheriger, '/',
                    parseAusdruck(index + 1));
        }

        
        return ergebnis;
    }


    /**
     * Parst eine Konstante, eine Variable oder Klammerausdruecke.
     *
     * @return geparster Ausdruck fuer Variablen oder Konstanten.
     */
    private Ausdruck parseFaktor(int index) {
        /* Regulaerer Ausdruck fuer Klammer auf. */
        Pattern klammerAuf = Pattern.compile("\\(");
        //Matcher fuer dem Regulaeren Ausdruck Klammer auf.
        Matcher matcherklammerAuf = klammerAuf.matcher(tokenListe.get(index));

        /* Das gleiche fuer die Klammer zu. */
        Pattern klammerZu = Pattern.compile("\\)");
        //Matcher fuer dem Regulaeren Ausdruck Klammer zu.
        Matcher matcherklammerZu = klammerZu.matcher(tokenListe.get(index));

        /* Regulaerer Ausdruck fuer Zahlen. */
        Pattern zahlen = Pattern.compile("[0-9]+");
        //Matcher fuer dem Regulaeren Ausdruck Zahlen.
        Matcher matcherzahlen = zahlen.matcher(tokenListe.get(index));
        
        /* Regulaerer Ausdruck fuer Zahlen. */
        Pattern variablen = Pattern.compile("[a-z]+");
        //Matcher fuer dem Regulaeren Ausdruck Zahlen.
        Matcher matchervariablen = variablen.matcher(tokenListe.get(index));
        
        if (matcherklammerAuf.find() == true) {
            parserIndex++;
            ergebnis = parseAusdruck(parserIndex);
        }

        if (matcherklammerZu.find() == true) {
            if (parserIndex < tokenListe.size()) {
                parserIndex++;
                ergebnis = parseAusdruck(parserIndex);
            }
        }

        if (matcherzahlen.find() == true) {
            ergebnis = new Konstante(Integer.parseInt(tokenListe.get(index)));
        }

        if (matchervariablen.find() == true) {
            ergebnis = new Variable(tokenListe.get(index));
        }

        return ergebnis;
    }

    /**
     * Initaliesiert die Liste aller Tokens.
     */
    private void initArrayListe(String infixdarstellung) {
        java.util.StringTokenizer st =
            new java.util.StringTokenizer(infixdarstellung, " ");

        while(st.hasMoreTokens()) {
            tokenListe.add(st.nextToken());
        }
    }
}
```

Die Klasse Ausdruck

```
/**
 * Oberklasse Ausdruck, die alles Ausdruecke repraesentiert.
 *
 */
public abstract class Ausdruck {
    /**
     * Abstrakte Methode, die den Wert dieses Ausdrucks
     * basierend auf der Variablenbelegung liefert.
     *
     * @return Wert der zuruekgegeben wird.
     */
    public abstract int gibWert(Variablenbelegung variablenbelegung);


}
```

Die Klasse OperatorAusdrucl

```
/**
 * Klasse zur Darstellung eines Operationsausdrucks.
 *
 */
public class OperatorAusdruck extends Ausdruck {
    /** Erzeugt einen neuen Ausdruck. */
    private Ausdruck linkerAusdruck;

    /** Erzeugt einen neuen Ausdruck. */
    private Ausdruck rechterAusdruck;

    /** Erzeugt ein neues char zeichen. */
    private char operator;

    /**
     * Erzeugt ein Objekt dieser Klasse fÃ¼r die angegebenen Daten.
     *
     * @param linkerAusdruck Wert des ersten Ausdrucks.
     * @param operator Wert des char Zeichen.
     * @param rechterAusdruck Wert des zweiten Ausdrucks.
     */
    public OperatorAusdruck(Ausdruck linkerAusdruck, char operator,
            Ausdruck rechterAusdruck) {
        this.linkerAusdruck = linkerAusdruck;
        this.rechterAusdruck = rechterAusdruck;
        this.operator = operator;
    }

    @Override
    /**
    * Prueft, ob zwei Operatorausdruecke gleich sind.
    *
    * @param obj ein beliebiges Objekt
    * @return <code>true</code> genau dann, wenn das uebergebene Objekt
    *         denselben Wert repraesentiert wie dieses Objekt.
    */
    public boolean equals(Object obj) {
        boolean istGleich = false;
        if (obj instanceof OperatorAusdruck) {
            OperatorAusdruck operatorAusdruck = (OperatorAusdruck) obj;

            istGleich = 
                    operatorAusdruck.linkerAusdruck.equals(this.linkerAusdruck)
                    && operatorAusdruck.rechterAusdruck.equals(this.rechterAusdruck)
                    && operatorAusdruck.operator == this.operator;
        }
        return istGleich;
    }

    @Override
    /**
     * Methode, die den Wert des Operatorausdrucks zurueck gibt.
     *
     */
    public int gibWert(Variablenbelegung variablenbelegung) {
        int ergebnis = 0;

        switch(operator) {
            case '+':
                ergebnis = linkerAusdruck.gibWert(variablenbelegung) +
                        rechterAusdruck.gibWert(variablenbelegung);
                break;

            case '-':
                ergebnis = linkerAusdruck.gibWert(variablenbelegung) -
                        rechterAusdruck.gibWert(variablenbelegung);
                break;

            case '*':
                ergebnis = linkerAusdruck.gibWert(variablenbelegung) *
                        rechterAusdruck.gibWert(variablenbelegung);
                break;

            case '/':
                ergebnis = linkerAusdruck.gibWert(variablenbelegung) /
                        rechterAusdruck.gibWert(variablenbelegung);
                break;
            }
        return ergebnis;
        }

    }
```

Die Klasse Konstante

```
/**
 * Klasse zur Darstellung einer Konstante.
 *
 */
public class Konstante extends Ausdruck {

    /** Erzeugt eine neue Konstante. */
    private final int wert;

    /**
     * Erzeugt ein Objekt dieser Klasse.
     *
     * @param wert Wert der Konstanten.
     */
    public Konstante(int wert) {
        this.wert = wert;
    }

    @Override
    /**
    * Prueft, ob zwei Objekte gleich sind.
    *
    * @param obj ein beliebiges Objekt
    * @return <code>true</code> genau dann, wenn das uebergebene Objekt
    *         denselben Wert repraesentiert wie dieses Objekt
    */
    public boolean equals(Object obj) {
        boolean istGleich = false;

        if (obj instanceof Konstante) {
            Konstante konstante = (Konstante) obj;
            if (konstante.wert == this.wert) {
                    istGleich = true;
            }
        }
        return istGleich;
    }



    @Override
    /**
     * Methode, die den Wert der Konstante zurueck gibt.
     */
    public int gibWert(Variablenbelegung variablenbelegung) {
        return this.wert;
    }
}
```

Die Klasse Variable

```
/**
 * Klasse zur Darstellung einer Variable.
 *
 */
public class Variable extends Ausdruck {

    /** Variablennamen als String. */
    private String name;

    /**
     * Erzeugt ein Objekt dieser Klasse fÃ¼r die angegebenen Daten.
     *
     * @param name Name der Variable.
     */
    public Variable(String name) {
        this.name = name;
    }



    @Override
    /**
    * Prueft, ob dieses Objekt gleich dem uebergebenen Objekt ist.
    *
    * @param obj ein beliebiges Objekt.
    * @return <code>true</code> genau dann, wenn das uebergebene Objekt
    *         denselben Wert repraesentiert wie dieses Objekt.
    */
    public boolean equals(Object obj) {
        boolean istGleich = false;

        if (obj instanceof Variable) {
            Variable variable = (Variable) obj;
            if (variable.name.equalsIgnoreCase(this.name)) {
                    istGleich = true;
            }
        }
        return istGleich;
    }

    @Override
    /**
     * Methode, die den Wert der Variable zurÃ¼ck gibt.
     */
    public int gibWert(Variablenbelegung variablenbelegung) {
        return variablenbelegung.gibWert(this.name);
    }
}
```

Die Klasse Variablenbelegung

```
import java.util.HashMap;

/**
 * Klasse zum Belegen einzelner Variablen.
 *
 */
public class Variablenbelegung {

    private HashMap<String, Integer> map;
    /**
     * Erzeugt ein Objekt dieser Klasse.
     */
    public Variablenbelegung() {
        map = new HashMap();
    }

    /**
     * Methode belge zum belegen der Variablen.
     *
     * @param name Name der Variable.
     * @param wert Wert der Variable.
     */
    public void belege(String name, int wert) {
        map.put(name, wert);
    }

    /**
     * Methode, die den Wert der Variable zurueck gibt.
     *
     * @param name Name der Variable.
     *
     * @return Wert der Variable.
     */
    public int gibWert(String name) {
        return map.get(name);
    }
}
```

Und der Parser Test

```
import junit.framework.TestCase;

/**
 * Testklasse fuer Methoden der Klasse Parser.
 *
 */
public class ParserTest extends TestCase {
        /** Erzeugt ein Parser.  */
        private Parser parser;

        /** Erzeugt ein Variablenbelegungsobjekt. */
        private Variablenbelegung variablenbelegung;

        /**
         * Erzeugt ein Objekt dieser Klasse
         * mit dem angegebenen Namen.
         *
         * @param name  Name dieses Tests
         */
        public ParserTest(String name) {
              super(name);
        }

        /**
         * Testdaten aufbauen.
         */
        protected void setUp() {
            parser = new Parser();
            variablenbelegung = new Variablenbelegung();

            /* Erzeugt eine neue Variablenbelegung fuer i = 3. */
            variablenbelegung.belege("i", 3);

            /* Erzeugt eine neue Variablenbelegung fuer i = 3. */
            variablenbelegung.belege("k", 4);

            /* Erzeugt eine neue Variablenbelegung fuer i = 3. */
            variablenbelegung.belege("j", 9);
        }

        /**
         * Testet die Methode Parse in der KLasse Parser.
         */
        public void testParse() {
            /** Parst den Ausdruck "10". */
            assertEquals(10 , parser.parse("10").gibWert(variablenbelegung) );

            /** Parst den Ausdruck "7 + i" mit i = 3. */
            assertEquals(10 , parser.parse("7 + i").gibWert(variablenbelegung));

            /** Parst den Ausdruck "( i + 18 ) / 2".
             * i = 3.
             */
            assertEquals(10 , parser.parse("( i + 18 ) / 2")
                    .gibWert(variablenbelegung));

            /* Parst den Ausdruck "1 + 2 * ( i + 2 * k - 1 ) / 2 + j".
             * mit i = 3, k = 4 und j = 9.
             */
            assertEquals(20, parser.parse("1 + 2 * ( i + 2 * k - 1 ) / 2 + j")
                    .gibWert(variablenbelegung));
        }

        /**
         * Startet den Test.
         *
         * @param args  wird nicht verwendet
         */
        public static void main(String[] args) {
        junit.textui.TestRunner.run(ParserTest.class);
        }
}
```

Danke nochmal.....


----------



## AlexSpritze (26. Mai 2010)

Wie wäre es mit einigen Logger-Ausgaben, um zu sehen, was da alles gemacht wird? Sowas wie

```
logger.debug("Found Ausdruck: "+ausdruck);
```


----------



## SlaterB (26. Mai 2010)

viel interessanter als der Fehler ist ja, wie du bei der Suche vorgehst,
ein elementarer Schritt wäre z.B. die Baumstruktur der Ausdrücke auszugeben

dabei ist mir aufgefallen dass anscheinend Punktrechnung vor Strichrechnung nicht berücksichtigt wird, richtig?
bzw. selbst Klammern helfen nicht
1 + 2 * ( i + 2 * k - 1 ) / 2 + j
wird wie
((((((1 + 2) * i) + 2) * k) - 1 )  / 2) + j
ausgewertet, mit Rundungsfehler bei int durch int (43 / 2 = 21) kommt man damit auf 30

auch die gibWert-Berechnung ließe sich mit Debugger oder System.out.println genauestens verfolgen,
scheint aber korrekt, von der Rundung abgesehen, nur der Baum wird eben falsch zusammengestellt,

-----

bedenklich ist auch, dass einfache Klammern außen zu einer Exception führen:
Ausdruck a = parser.parse("( i + 2 )");

und der Parser ist leerzeichenempfindlich, i+2 statt i + 2 mag er nicht

-------

zum Abschauen hier noch eine andere Version
http://www.java-forum.org/allgemeines/12306-parser-fuer-mathematische-formeln.html


----------



## -horn- (26. Mai 2010)

moien,

arrrg, wenn mir mein kumpel nicht sowas programmiert hätte würde ich dir nun meinen code geben, aber ohne erlaubnis mache ich das nicht. will keinen zoff .
aber ich werd ihn mal hieraus aufmerksam machen. vielleicht kann er dir helfen.
mir hat er sowas mal für meine diplomarbeit gebaut, damit meine simulation auch auf externe formeln zurückgreifen konnte.

ich versprechenix, aber ich werd ihm vom thread mal berichten.

grüße, Andreas


----------



## Landei (26. Mai 2010)

Schon mal überlegt, einen "richtigen" Parser-Generator zu verwenden (ANTLR, JavaCC, SableCC, Coco/R). Wenn das Ding noch "wachsen" soll, wirst du mit deinem handgefriemelten Code nicht glücklich, falls du nicht schon _einige_ Erfahrungen mit sowas hast.


----------



## Marco13 (26. Mai 2010)

Landei hat gesagt.:


> Wenn das Ding noch "wachsen" soll, wirst du mit deinem handgefriemelten Code nicht glücklich, falls du nicht schon _einige_ Erfahrungen mit sowas hast.



Dem Einstieggsatz nach...



Todo hat gesagt.:


> ich soll für die FH einen Mathe Parser schreiben,



soll es vermutlich nicht mehr wachsen (der allseits bekannte STL-Zyklus: Schreiben-Testieren-Löschen) - vielmehr geht es wohl um das Sammeln der angesprochenen Erfahrungen...


----------



## Todo (26. Mai 2010)

Ich weiß das ich die Klammern nicht wirklich berücksichtige, wenn eine Klammer auf kommt erhöre ich einfach das Token und guck mir das nächste an, weiß aber nicht was ich da besonders beachten soll, ausser halt bei den Exceptions, das auch auf jede Klammer auf eine Klammer zu folgt.

EDIT: Und ja ich beachte nicht Punkt vor Strichrechnung, ich geh einfach Token für Token rekursiv die Methode ab, mir wurd gesagt das es wohl so möglich ist....

PS: Danke für den Link, bin ich schonmal drauf gestoßen werde ich mir mal intensiv durchlesen....


----------



## SlaterB (26. Mai 2010)

niemand hat behauptet, es wäre einfach, 
richtige Klammersetzung ist komplex, ob man das hier alles erklären kann?

als ich das selber mal gebaut hatte, hatte ich glaube ich Extra-Knoten für die Klammern, dort dann neu mit links, rechts anfangen usw.,
noch schwieriger ist aber sicherlich Punkt vor Strich

naja, viel einfacher als es selber zu bauen wäre wie gesagt das Abschauen, versuche es damit,
wenn das auch nicht klappt dann hmm..


----------



## Java-Freak (26. Mai 2010)

aus den FAQs...
http://www.java-forum.org/allgemeines/12306-parser-fuer-mathematische-formeln.html
kann aber keine variblen, musste selber einbaun


----------



## Todo (26. Mai 2010)

Ja das mit den char vergleichen anstatt mit den StringTokenizer ist auf jeden Fall schonmal 10 mal besser, wieder mal was einfaches gelernt ....
Der Algo arbeitet leider mit Prioritäten, so wollte ich das auch erst machen sollten wir aber leider nicht  ... mal sehen was ich da noch so raus machen kann danke schonmal an alle


----------



## Antoras (26. Mai 2010)

Du programmierst nicht für deinen Lehrer, sondern für dich! Niemand kann dir vorschreiben wie ein Programm am Ende auszusehen hat solange es das macht für was es ursprünglich konzipiert wurde.

Ich kann mir außerdem nicht vorstellen, dass dein Lehrer dich ausdrücklich darauf hingewiesen hat, dass alle zusätzlichen Features strengstens untersagt sind und mit nicht Anerkennung der Arbeit angesehen werden...


----------



## Todo (27. Mai 2010)

Naja abschauen ist ja auch nicht so das ware, und leider macht es es ja auch komplett anders als ich wie ich finde....
muss nochmal schauen wirklich ne Lösung habe ich leider noch nicht...


----------



## Landei (27. Mai 2010)

Für das Punktrechnung-vor-Strichrechnung- und Klammer-Problem würde ich vorschlagen, den Inhalt nach dem Parsen mit dem Shunting-Yard-Algorithmus entweder in einen Syntax-Baum oder in einen Stack in Postfix-Notation zu überführen, dann sieht das Ganze schon freundlicher aus.


----------



## Todo (28. Mai 2010)

Programm läuft,
mal ne kurze Frage zu den &Exceptions, kann man sich ein regulären Ausdruck basteln der auf richtige Klammersetzung und richte Operatorensetzung  (+-*/) achtet ?


----------



## SlaterB (28. Mai 2010)

nein, das machen Parser wie deiner dann hoffentlich auch nebenbei


----------



## Landei (28. Mai 2010)

Normalerweise trennt man das Zerstückeln in sinnvolle Einheiten ("Tokens") und die Auswertung der Tokensuppe (meistens mit einem Syntaxbaum oder "AST"). Die beiden Programmteile nennt man "Lexer" und "Parser". Diese Einteilung beruht auf der genauso bitteren wie gesicherten Erfahrung, das alles andere in einem Kuddelmuddel endet. Vergiss also ganz schnell die Idee, das alles auf einmal mit regulären Ausdrücken zu erschlagen - es wird nicht funktionieren. Wie man das Klammer- und Operator-Rang-Problem lösen kann, hatte ich schon geschrieben, aber ignoriere das ruhig, wenn du einen besseren Weg weißt.


----------

