Operatorbaum aufstellen

[Seppo]

Wie kann ich z.B so einen Ausdruck -((A+B)*C)+A in einen Operatorbaum bringen? (Das -,+,* sollen boolsche Ausdrücke sein.)
Danach kann man ja den Baum PostOrder auslesen und mit Hilfe eines Stacks auswerten, aber bis jetzt ist es mir noch nicht gelungen dies richtig in einen solchen Baum einzulesen (in Java).

[HajottV]

Original geschrieben von Seppo
Wie kann ich z.B so einen Ausdruck -((A+B)*C)+A in einen Operatorbaum bringen? (Das -,+,* sollen boolsche Ausdrücke sein.)


Such mal bei Google nach "parsing kontextfreie grammatiken".

Gruß

Jörg

[Trap]

In Java würd ich www.sablecc.org benutzen. Das ist zwar etwas oversized für so eine einfache Sprache wie boolsche Ausdrücke, aber Parser selber schreiben ist ziemlich eklig.

[Xmas]

Lustig, einen Parser für etwas ähnliches habe ich im letzten Semester für ein Projekt in Anwendungsprogrammierung geschrieben. Dabei waren x, Float-Konstanten, +, -, *, /, ^, ( und ) erlaubt.

import java.text.ParseException;

public class FormulaParser
{
// parse
//
// Parst einen mathematischen Term und gibt einen Operationsbaum zurück
// Der Ablauf ist rekursiv, jeweils die Operation die zuletzt ausgeführt
// werden muss wird am nächsten zur Baumwurzel angehängt, der Formelstring
// wird gesplittet und die beiden Teile geparst als Operanden der
// jeweiligen Operation verwendet.

public static IMathExpression parse(String str)
throws ParseException
{
str = str.trim();
if(str.length() == 0)
throw new ParseException("Ausdruck fehlt!", 0);
if(str.equals("x")) // ist die Formel nur x?
return new XExpression();

// Rechenzeichen finden, nur außerhalb von Klammern
int lastMulDiv = -1, lastAddSub = -1, lastPow = -1;
for(int i = str.length() - 1; i >= 0; --i) {
switch(str.charAt(i)) {
case '+':
case '-':
lastAddSub = Math.max(i, lastAddSub);
break;
case '*':
case '/':
lastMulDiv = Math.max(i, lastMulDiv);
break;
case '^':
lastPow = Math.max(i, lastPow);
break;
case ')':
i = findOpeningBracket(str, i);
if(i == -1)
throw new ParseException("Öffnende Klammer fehlt: " + str, 0);
break;
case '(':
throw new ParseException("Schließende Klammer fehlt: " + str, 0);
}
}

if(lastAddSub > 0) { // Kommt + oder - in der Formel vor?
if(str.charAt(lastAddSub) == '-')
return new SubExpression(parse(str.substring(0, lastAddSub)),
parse(str.substring(lastAddSub + 1)));
else
return new AddExpression(parse(str.substring(0, lastAddSub)),
parse(str.substring(lastAddSub + 1)));
} else if(lastMulDiv >= 0) { // Kommt * oder / in der Formel vor?
if(str.charAt(lastMulDiv) == '*')
return new MulExpression(parse(str.substring(0, lastMulDiv)),
parse(str.substring(lastMulDiv + 1)));
else
return new DivExpression(parse(str.substring(0, lastMulDiv)),
parse(str.substring(lastMulDiv + 1)));
} else if(lastPow >= 0) { // Kommt ^ in der Formel vor?
return new PowExpression(parse(str.substring(0, lastPow)),
parse(str.substring(lastPow + 1)));
} else if(lastAddSub == 0) { // Vorzeichen?
if(str.charAt(lastAddSub) == '-') // führendes -? Negation!
return new NegExpression(parse(str.substring(1)));
else // führendes + kann ignoriert werden
return parse(str.substring(1));
} else if((str.charAt(0) == '(') && // Nur Klammerausdruck?
(str.charAt(str.length() - 1) == ')')) {
return parse(str.substring(1, str.length() - 1));
}
try {
return new ConstExpression(Double.parseDouble(str));
} catch(NumberFormatException e) {
throw new ParseException("Fehler beim Parsen von Konstante: " + str, 0);
}
}

protected static int findOpeningBracket(String str, int pos)
throws IndexOutOfBoundsException
{
for(int i = pos - 1; i >= 0 ; --i) {
if(str.charAt(i) == '(')
return i;
if(str.charAt(i) == ')') {
i = findOpeningBracket(str, i);
if(i == -1)
return -1;
}
}
return -1;
}
}

[Seppo]

Ich habs jetzt so gemacht:

public class Parser {

public boolean parse(String s) {
return ausdruck(s, 0);
}

public boolean ausdruck(String s, int i) {
boolean stop = false;
boolean ergebnis;
ergebnis = term(s, i);
do {
if (s.charAt(i) == '+') {
i++;
ergebnis = ergebnis | term(s, i);
} else {
stop = true;
}
} while (!stop);
return ergebnis;
}

public boolean term(String s, int i) {
boolean stop = false;
boolean ergebnis;
ergebnis = faktor(s, i);
do {
if (s.charAt(i) == '*') {
i++;
ergebnis = ergebnis & faktor(s, i);
} else {
stop = true;
}
} while (!stop);
return ergebnis;

}

public boolean faktor(String s, int i) {
boolean ergebnis;
if (s.charAt(i) == '1') {
i++;
return ergebnis = true;
} else {
if (s.charAt(i) == '0') {
i++;
return ergebnis = false;
} else {
if (s.charAt(i) == '(') {
i++;
ergebnis = ausdruck(s, i);
if (s.charAt(i) != ')') {
throw new RuntimeException("");
} else {
i++;
}
return ergebnis;
} else {
throw new RuntimeException("");
}
}

}

}

public static void main(String[] args) {
Parser p = new Parser();
System.out.println(p.parse("0|1"));
}
}
Doch leider klappt das nicht so ganz. 1|0 liefert wahr, aber 0|1 falsch. :(

[Seppo]

Das soll natürlcich + heißen, klappt aber auch so nicht.

[ethrandil]

Also, so ein Zufall aber auch, ich hatte einen ähnlichen Beispielcode von XMas auch schon, und das hier draus gemacht. Vielleicht ergehts dir damit besser?


//this code is ported by Xmas' C#-function. No Warranty ;)
public static Command parse(String formel) throws Exception
{
int klammerebene = 0;
int splitpos = -1;
int splitlevel = 0;

boolean klammer = false;

for (int i = 0 ; i < formel.length() ; i++)
{
switch (formel.charAt(i))
{
case '(':
klammer = true;
klammerebene++;
break;

case ')':
klammer = true;
if (klammerebene == 0)
throw new Exception ("nicht genug Klammern geöffnet");

klammerebene--;
break;

case '+':
case '-':
if (splitlevel > 4 || klammerebene != 0){
break;
}

splitpos = i;
splitlevel = 4;
break;

case '*':
case '/':
if (splitlevel > 3 || klammerebene != 0){
break;
}

splitpos = i;
splitlevel = 3;
break;

case '^':
if (splitlevel > 2 || klammerebene != 0){
break;
}

splitpos = i;
splitlevel = 2;
break;
}
}

if (klammerebene != 0)
throw new Exception("Klammern nicht geschlossen!!!");

if (splitlevel > 0)
{
Command left = parse (formel.substring(0, splitpos));
Command right = parse (formel.substring(splitpos+1));
//System.out.println("left:"+formel.substring(0, splitpos)+"right:"+formel.substring(splitpos+1));

switch (formel.charAt(splitpos))
{
case '+':
return new Additioner(left, right);

case '-':
return new Substractioner(left, right);

case '*':
return new Multiplier(left, right);

case '/':
return new Divider(left, right);

case '^':
return new Hoch(left, right);
default:
throw new Exception();
}
}

if (klammer)
return parse (formel.substring(1, formel.length()-1));

if (formel.equals("x"))
return new XValue();

if(formel.length()>0)
return new Value(java.lang.Double.parseDouble(formel));

return new Value(0);
}

[Xmas]

Original geschrieben von Seppo
public class Parser {
public boolean ausdruck(String s, int i) {
boolean stop = false;
boolean ergebnis;
ergebnis = term(s, i);

Doch leider klappt das nicht so ganz. 1|0 liefert wahr, aber 0|1 falsch. :(
Kein Wunder. Du bekommst hier gar nicht die Breite des Terms zurück, erhöhst i also nicht. Beim darauffolgenden vergleich bist du immer noch beim ersten Zeichen, was einen Stop bewirkt.

[Seppo]

Jetzt klappts, musste nur ein paar Variablen umändern :)