bht-berlin.deDas nachfolgende Java-Programm AusdruckParser berechnet den Wert eines arithmetischen Ausdrucks, gegeben als Iterable<String> (ein Obertyp von List<String>). Die syntaktische Korrektheit wird vorausgesetzt und nicht geprüft. Jedes String enthält entweder ein syntaktisch korrekte Bruchzahl (als double), oder einen Operator +, -, /, *, (, oder ). Bei der Auswertung wird Präzedenz (Priorität, Ausführungsreihenfolge) berücksichtigt: „Punkt vor Strich“, die aber durch Klammerung verändert werden kann.
Der Algorithmus wird mit Hilfe von zwei (parallel geführten) Stapeln (stack) durchgeführt: der eine für Operanden, der zweite für Operatoren. Dadurch wird der Ausdruck nur linear gelesen. Wenn ein Operand (eine Zahl) gelesen wird, kommt er auf den Operanden-Stapel. Wenn ein Operator gelesen wird, werden zuerst die Stapel geleert, d.h. alle gestapelten Operatoren mit höherer Priorität werden berechnet. Anschließend wird der Operator auf den Stapel gelegt. Klammern werden als Operatoren behandelt, wobei nebeneinander liegende Klammerpaare (deren Inhalt schon berechnet worden ist) werden aus dem Operatorstapel entfernt. Zum Schluss (nachdem der Ausdruck vollständig gelesen wurde) werden noch die Stapel geleert, d.h. die restlichen Operatoren mit ihren gestapelten Operanden berechnet.
Die main-Methode der Klasse testet die Methode mit den in List<String> umgewandelten Kommandozeilenparametern. Sie kann also z.B. mit
> java AusdruckParser 1 + 2 * ( 3 – 4 )
aufgerufen werden. Das Ergebnis erscheint auf der Konsole:
Der Wert der Formel [1, +, 2, *, (, 3, –, 4, )] ist: 7.0
Die Klasse AusdruckTest enthält einen grammatik- und zufallgesteuerten Testdatengenerator für AusdruckParser. Ihre Methode testdatengenerator generiert als Ergebnis ein String[] aufgrund der Grammatik für Ausdrücke einen syntaktisch korrekten Ausdruck. Seine Länge, Struktur und die enthaltenen double-Werte (im Bereich von 000.000 bis 999.999) werden vom Zufallsgenerator bestimmt.
Interessant dabei ist die objektorienterte Abbildung der Grammatik für Ausdrücke:
Ausdruck : Term | Ausdruck + Term | Ausdruck - Term Term : Faktor | Term * Faktor | Term / Faktor Faktor : Zahl | ( Ausdruck )
Hierzu dient die Klasse Regel, von der (entsprechend der obigen Grammatik) 8 Objekte (für jede Alternative eins) erzeugt werden. Diese werden in der Reihung Regel[] grammatik gespeichert. Ein Regel-Objekt besteht aus einem Symbol (die linke Seite der Regel) und aus einem Symbol[] (ihre rechte Seite). Ein Symbol ist ein enum-Wert Ausdruck, Term, Faktor, Zahl, Plus, Minus, Mal, Durch, KlammerAuf oder KlammerZu. Es stellt ein nichtterminales Symbol (Ausdruck, Term, Faktor) oder ein terminales Symbol (Zahl, Plus, Minus, Mal, Durch, KlammerAuf oder KlammerZu) der Grammatik dar. Die Methode istTerminal() der enum-Klasse Symbol ist für die Unterscheidung geeignet.
In der Methode wortGenerieren() wird das Wort als ein ArrayList<Symbol>-Objekt gesammelt. Dabei wird der Algorithmus „Ableitung in einer Grammatik“ verwendet: Ausgehend aus dem Startsymbol (hier: Ausdruck) werden nichtterminale Symbole (Ausdruck, Term oder Faktor) auf eine ihrer rechten Seiten ausgetauscht, solange es noch nichtterminale Symbole gibt. Um die Länge der erzeugten Ausdrücke zu begrenzen, wird die Wahrscheinlichkeit für die Verwendung der letzten Regel (in der eine Zahl erzeugt wird) um den Faktor 3 erhöht. Die Zahlen werden zufallsbasiert im Bereich 000.000 bis 999.999 in der toString()-Methode von Symbol erzeugt.
Wenn die Klasse mit
java AusdruckTest
interpretiert wird, ist das Ergebnis zufallsabhängig z.B.
Der Wert der Formel 141.110 / 916.358 + 919.013 * 192.501 - ( 552.253 / 1.57938 ) ist: 176561.41107775364
/** AusdruckParser.java Algorithmus zum Berechnen den Wert eines arithmetischen Ausdrucks mit Klammern und Operatorpräzedenz @author Prof. Dr. Andreas Solymosi, (c) 2000-2011: APSIS GmbH @date: 22. April 2008 @version: 25. März 2011 */
import java.util.Arrays; import java.util.List; import java.util.Stack;
public class AusdruckParser { private static Stack<Double> operanden = new Stack<Double>(); private static Stack<Integer> operatoren = new Stack<Integer>();
/** Methode zum Berechnen den Wert eines arithmetischen Ausdrucks mit Klammern und Operatorpräzedenz @param ausdruck aus Bruchzahlen und Operatoren +, -, /, *, (, ) @return Wert des Ausdrucks */ public static double auswertung(Iterable<String> ausdruck) { // Verallgemeinerung von String[] ausdruck final String oper = "(+-*/)"; // Operatoren final String prior = "311220"; // Präzedenz der Operatoren final int klammerAuf = oper.indexOf('('), klammerZu = oper.indexOf(')');
operanden.push(0.); operatoren.push(klammerAuf); // Boden markieren for (String element : ausdruck) { char zeichen = element.charAt(0); if (Character.isDigit(zeichen)) operanden.push(Double.parseDouble(element)); else for (int op = 0; op < oper.length(); op++) // Operator suchen if (zeichen == oper.charAt(op)) { // Operator gefunden while (prior.charAt(op) <= prior.charAt(operatoren.peek()) && operatoren.peek() != klammerAuf) // Stapel leeren rechnen(operatoren.pop()); if (op != klammerZu) operatoren.push(op); if (op == klammerZu && operatoren.peek() == klammerAuf) operatoren.pop(); } }
while (!operatoren.isEmpty()) rechnen(operatoren.pop()); return operanden.pop(); }
private static void rechnen(int operator) { switch (operator) { case 1: operanden.push(operanden.pop() + operanden.pop()); break; // '+' case 2: operanden.push(-(operanden.pop() - operanden.pop())); break; // '-' case 3: operanden.push(operanden.pop() * operanden.pop()); break; // '*' case 4: operanden.push(1/(operanden.pop() / operanden.pop())); break; // '/' } }
/** * Testtreiber * @param kzp enthält zu testenden Ausdruck elementweise (Bruchzahlen und Operatoren getrennt) */
public static void main(String[] kzp) { final String benutzung = "Benutzung: java AusdruckParser Formel\n" + "Die Formel besteht aus Bruchzahlen und Operatoren +, -, /, *, (, ) getrennt durch Leerzeichen.", ergebnis = "Der Wert der Formel ", verbindung = " ist: "; final List<String> eingabe = Arrays.asList(kzp); System.out.println((kzp.length < 1) ? benutzung : ergebnis + eingabe.toString() + verbindung + auswertung(eingabe)); } }
/** AusdruckTest.java Klasse für Zufallsgenerierung eines arithmetischen Ausdrucks mit Klammern und Operatorpräzedenz @author Prof. Dr. Andreas Solymosi, (c) 2000-2011: APSIS GmbH @date: 24. April 2008 @version: 25. März 2011 */
import static java.util.Arrays.asList; import java.util.Arrays; import java.util.List;
public class AusdruckTest { /** * Testtreiber * @param kzp enthält den zu testenden Ausdruck elementweise (Bruchzahlen und Operatoren getrennt), oder leer */ public static void main(String[] kzp) { /* Benutzung: java AusdruckParser Ausdruck oder java AusdruckParser Ausdruck besteht aus Bruchzahlen und Operatoren +, -, /, *, (, ) getrennt durch Leerzeichen. Ohne Ausdruck wird ein Ganzzahlausdruck nach Zufall generiert */ final String[] testdaten = kzp.length < 1 ? testdatengenerator() : kzp; String ausdruck = ""; for (String s : testdaten) ausdruck += s + " "; final List<String> eingabe = Arrays.asList(testdaten); System.out.println("Der Wert der Formel " + ausdruck + "ist: " + AusdruckParser.auswertung(eingabe)); }
/* Testdatengenerator für die Grammatik der Ausdrücke:
Ausdruck : Term | Ausdruck + Term | Ausdruck - Term
Term : Faktor | Term * Faktor | Term / Faktor
Faktor : Zahl | ( Ausdruck )
*/
private static enum Symbol { Ausdruck, Term, Faktor, Zahl, Plus, Minus, Mal, Durch, KlammerAuf, KlammerZu; public boolean istTerminal() { return this.ordinal() >= Zahl.ordinal(); } private java.util.Random zufall = new java.util.Random(java.util.Calendar.getInstance().getTimeInMillis());
public String toString() { final int MAX = 1000, ZIFFER = 7; // zu generierende Zahlen 000.000 bis 999.999 switch (this) { case Zahl: return ("" + Math.abs(zufall.nextInt(MAX) + zufall.nextDouble())).substring(1,7); case Plus: return "+"; case Minus: return "-"; case Mal: return "*"; case Durch: return "/"; case KlammerAuf: return "("; case KlammerZu: return ")"; default: return ""; } } }
private static class Regel { Symbol links; Symbol[] rechts; Regel(Symbol links, Symbol[] rechts) { this.links = links; this.rechts = rechts; } }
private static String[] testdatengenerator() { final Symbol Ausdruck = Symbol.Ausdruck, // Abkürzung Term = Symbol.Term, Faktor = Symbol.Faktor, Zahl = Symbol.Zahl, Plus = Symbol.Plus, Minus = Symbol.Minus, Mal = Symbol.Mal, Durch = Symbol.Durch, KlammerAuf = Symbol.KlammerAuf, KlammerZu = Symbol.KlammerZu;
/* Grammatik: Ausdruck : Term | Ausdruck + Term | Ausdruck - Term Term : Faktor | Term * Faktor | Term / Faktor Faktor : Zahl | ( Ausdruck ) */ Regel[] grammatik = { new Regel( Ausdruck, new Symbol[] {Term} ), new Regel( Ausdruck, new Symbol[] {Ausdruck, Plus, Term} ), new Regel( Ausdruck, new Symbol[] {Ausdruck, Minus, Term} ), new Regel( Term, new Symbol[] {Faktor} ), new Regel( Term, new Symbol[] {Term, Mal, Faktor} ), new Regel( Term, new Symbol[] {Term, Durch, Faktor} ), new Regel( Faktor, new Symbol[] {KlammerAuf, Ausdruck, KlammerZu} ), new Regel( Faktor, new Symbol[] {Zahl} ) }; return wortGenerieren(grammatik); }
/** * generiert Wort nach gegebener Grammatik * @param grammatik Reihung aus Regeln * @return generiertes Wort */ private static String[] wortGenerieren(Regel[] grammatik) { // ein Ausdruck wird nach der obigen Grammatik generiert java.util.ArrayList<Symbol> wort = new java.util.ArrayList<Symbol>();
while (wort.size() <= 1) { // befriedigendes Ergebnis nur wenn wort.size() > 1 wort.clear(); wort.add(grammatik[0].links); // Startsymbol
boolean nichtterminal = true; // es gibt noch nichtterminale Symbole java.util.Random zufall = new java.util.Random(java.util.Calendar.getInstance().getTimeInMillis());
while (nichtterminal) { // solange es noch nichtterminale Symbole gibt for (int i = 0; i < wort.size(); i++) { nichtterminal = false; // aufhören wenn es keine nichtterminale Symbole mehr gibt if (!wort.get(i).istTerminal()) { // nichtterminaes Symbol gefunden int index = 0; // Index in grammatik do { index = zufall.nextInt(grammatik.length); // beliebige Regel auswählen if (zufall.nextInt(3) % 3 == 0) // jedes dritte Mal trifft zu index = grammatik.length - 1; // Wahrscheinlichkeit der letzten Regel (Zahl wird generiert) erhöhen } while (grammatik[index].links == wort.get(i)); // Regel für dieses nichtterminale Symbol finden
// austauschen das nichtterminale Symbol auf die rechte Seite seiner Regel: java.util.ArrayList<Symbol> neu = new java.util.ArrayList<Symbol>(); // zum konkatenieren if (i > 0) neu.addAll(wort.subList(0, i)); // links vom Nichtterminal neu.addAll(asList(grammatik[index].rechts)); // ersetzen if (i < wort.size()-1) neu.addAll(wort.subList(i+1, wort.size())); // rechts vom Nichtterminal wort = neu; // neues Wort nichtterminal = true; // weitermachen break; // der for-Schleife } } } }
String[] ergebnis = new String[wort.size()]; for (int i = 0; i < wort.size(); i++) ergebnis[i] = "" + wort.get(i); return ergebnis; } // wortGenerieren } // AusdruckTest
Version: 30. März 2011
© Prof. Solymosi, 2011, Beuth-Hochschule für Technik Berlin, FB VI (Informatik und Medien)
solymosibht-berlin.de