package fplot;
import java.util.*;
/**
* Erzeugt die Knoten des Syntaxbaumes.
* @author Christian Semrau
*
* Christian.Semrau@student.uni-magdeburg.de
*
Homepage
*/
class NodeConstructor extends NodeBase {
static boolean verbose = false;
/** Keine Instanzen zulassen. */
private NodeConstructor() {}
/**
* Liefert den Postfix-Ausdruck "val2 val1 op".
* Wenn beide Operanden Zahlen sind, wird der Ausdruck
* (val2 op val1) direkt berechnet.
*/
private static String evaluate(Object val1, Object val2, Object op) {
String v1 = (String)val1, v2 = (String)val2, o = (String)op;
String term = v2+" "+v1+" "+o+" ";
if (verbose) System.out.println("berechne: "+term);
// keine Auswertung von reinen Zahlenausdruecken durchfuehren
if (false && FuncNode.isVal(v1) && FuncNode.isVal(v2) && isOp(o)){
double i1 = Double.valueOf(v1).doubleValue();
double i2 = Double.valueOf(v2).doubleValue();
switch(o.charAt(0)){
case '+': return (i2+i1)+" ";
case '-': return (i2-i1)+" ";
case '*': return (i2*i1)+" ";
case '/': if (i1!=0) return (i2/i1)+" ";
else return v2+" "+v1+" / ";
case '%': if (i1!=0) return (i2%i1)+" ";
else return v2+" "+v1+" % ";
case '\\':if (i1!=0) return (int)(i2/i1)+" ";
else return v2+" "+v1+" \\ ";
case '^': return term; // nicht berechnen
case '_': return (-i1)+" ";
default: return term; // sollte nicht auftreten
}
}else
if (o.equals("_"))
return v1+" _ ";
else
return term;
}
/**
* Wertet die oberste Operation des opStack aus.
* Wird von der Methode parseInfix aufgerufen.
*/
private static void evaluateFunc(Stack valStack, Stack opStack) {
String op = (String)opStack.pop();
String v;
// Verteilt die Arbeit an die einzelnen Spezialfunktionen.
if (isOp(op)){
String val1 = (String)valStack.pop();
String val2 = (String)valStack.pop();
v = filterRPN(evaluate(val1, val2, op));
valStack.push(v);
}else
if (FuncNode.isFunc0(op)){
v = filterRPN(evaluateFunc0(op));
valStack.push(v);
}else
if (FuncNode.isFunc1(op)){
String val1 = (String)valStack.pop();
v = filterRPN(evaluateFunc1(val1, op));
valStack.push(v);
}else
if (FuncNode.isFunc2(op)){
String val1 = (String)valStack.pop();
String val2 = (String)valStack.pop();
v = filterRPN(evaluateFunc2(val1, val2, op));
valStack.push(v);
}else
if (FuncNode.isFunc3(op)){
String val1 = (String)valStack.pop();
String val2 = (String)valStack.pop();
String val3 = (String)valStack.pop();
v = filterRPN(evaluateFunc3(val1, val2, val3, op));
valStack.push(v);
}else
throw new IllegalArgumentException(op);
}
/**
* Liefert den Postfix-Ausdruck fuer die Berechnung der parameterlosen
* Funktion op().
*/
private static String evaluateFunc0(String op) {
String term = op+" ";
if (verbose) System.out.println("berechne: "+term);
return term;
}
/**
* Liefert den Postfix-Ausdruck fuer die Berechnung der unaeren
* Funktion op(val).
*/
private static String evaluateFunc1(String val, String op) {
String term = val+" "+op+" ";
if (verbose) System.out.println("berechne: "+term);
return term;
}
/**
* Liefert den Postfix-Ausdruck fuer die Berechnung der binaeren
* Funktion op(val2,val1).
*/
private static String evaluateFunc2(String val, String val2, String op) {
String term = val2+" "+val+" "+op+" ";
if (verbose) System.out.println("berechne: "+term);
return term;
}
/**
* Liefert den Postfix-Ausdruck fuer die Berechnung der dreiparametrigen
* Funktion op(val3,val2,val1).
*/
private static String evaluateFunc3(String val1, String val2, String val3, String op) {
String term = val3+" "+val2+" "+val1+" "+op+" ";
if (verbose) System.out.println("berechne: "+term);
return term;
}
/**
*
* @param args java.lang.String[]
*/
public static void main(String args[]) {
String e =
// "e*x^2-(x-2)+x*-sin(e+x)+2*(-x)^3+pi*3^-2*pow(x,-3^-2)"
// "pow(x*x+3,23*p)"
// "x/(x\\x)/(x%x)"
// "-x^3+2*(-x)^3+2*-x^3*-4"
// "x\\(3*2)%x"
"1+sum3(p,x,2)"
;
System.out.println(e);
String e2;
try{
e2 = parseInfix(e);
}catch(EmptyStackException exc){
System.out.println(exc);
exc.printStackTrace();
return;
}catch(IllegalArgumentException exc){
System.out.println(exc);
exc.printStackTrace();
return;
}
System.out.println(e2);
FuncNode node = parseRPN(e2);
// System.out.println(node.internal());
node.setKlammerung(KLAMMERUNG_ALLES);
System.out.println("n1A:"+node);
node.setKlammerung(KLAMMERUNG_MITTEL);
System.out.println("n1M:"+node);
node.setKlammerung(KLAMMERUNG_WENIG);
System.out.println("n1W:"+node);
e = NodeConstructorHelp.parseInfixKlammerung2(node.toString());
e2 = parseInfix(e);
node = parseRPN(e2);
node.setKlammerung(KLAMMERUNG_ALLES);
System.out.println("n2A:"+node);
node.setKlammerung(KLAMMERUNG_MITTEL);
System.out.println("n2M:"+node);
node.setKlammerung(KLAMMERUNG_WENIG);
System.out.println("n2W:"+node);
}
/** Konstruiert einen neuen Knoten mit der Konstanten op */
private static FuncNode newConst(int op) {
return new FuncNode(op, NOFUNC, 0);
}
/** Konstruiert einen neuen Knoten mit der Zahl z */
private static FuncNode newZahl(double z) {
return new FuncNode(ZAHL, NOFUNC, z);
}
/** Konstruiert einen neuen Knoten mit der Zahl z */
private static FuncNode newZahl(String z) {
return newZahl(Double.valueOf(z).doubleValue());
}
/**
* Wandelt in Infixnotation gegebene arithmetische Ausdruecke von
* double-Zahlen mit den vier Grundrechenarten und bestimmten Funktionen
* mit einem und zwei Parametern im Postfixnotation um.
* @throws IllegalArgumentException
* @throws EmptyStackException
*/
public static String parseInfix(String eingabe) {
eingabe = NodeConstructorHelp.parseInfixKlammerung2(eingabe);
Stack valStack = new Stack(); // Operanden = Werte
Stack opStack = new Stack(); // Operatoren
String[] ti = new String[]{"", eingabe}; // Token, Eingabe
boolean lastWasOp = true; // war das letzte Token ein Operator?
while (ti[1].length()>0){
ti = getToken(ti[1]); // naechstes Token holen
if (verbose) System.out.println("Token: "+ti[0]+" Rest:"+ti[1]);
String t = ti[0]; // aktuelles Token
if (t.equals("(")){
if (verbose) System.out.println("Oeffnende Klammer --> op.push");
opStack.push(t);
lastWasOp = true;
}else
if (t.equals(")")){
if (verbose) System.out.println("Schliessende Klammer");
while(!opStack.peek().equals("(")){
evaluateFunc(valStack, opStack);
if (verbose) System.out.println("pushe Ergebnis "+valStack.peek());
}
opStack.pop(); // Klammer entfernen
if (!opStack.empty() && FuncNode.isFunction((String)opStack.peek())){
evaluateFunc(valStack, opStack);
if (verbose) System.out.println("pushe Ergebnis "+valStack.peek());
}
lastWasOp = false;
}else
if (isOp(t)){
if (verbose) System.out.println("Operator");
if (lastWasOp && (t.equals("-") || t.equals("+") )){
if (t.equals("-")){
if (verbose) System.out.println("unaeres Minus --> val.push(0), op.push(_)");
valStack.push("0");
opStack.push("_");
}else
if (verbose) System.out.println("unaeres Plus --> ignorieren");
lastWasOp = true;
}else
if (opStack.empty()){
if (verbose) System.out.println("leerer Stack --> op.push");
opStack.push(t);
lastWasOp = true;
}else
if (opStack.peek().equals("(")){
if (verbose) System.out.println("Klammer auf Stack --> op.push");
opStack.push(t);
lastWasOp = true;
}else
if (comparePriority(t, (String)opStack.peek())<=0){
if (verbose) System.out.println("Prioritaet: "+t+" <= "+opStack.peek());
evaluateFunc(valStack, opStack);
if (verbose) System.out.println("pushe Ergebnis "+valStack.peek());
ti[1] = t + ti[1]; // Operator wieder einsetzen
// lastWasOp unveraendert
}else{
if (verbose) System.out.println("Prioritaet: "+t+" > "+opStack.peek()+" --> op.push");
opStack.push(t);
lastWasOp = true;
}
}else
if (FuncNode.isConst(t)){
if (verbose) System.out.println("Konstante --> val.push");
valStack.push(t+" ");
lastWasOp = false;
}else
if (FuncNode.isFunction(t)){
if (verbose) System.out.println("Funktion --> op.push");
opStack.push(t);
lastWasOp = false;
}else
if (t.equals(",")){
if (verbose) System.out.println("Komma");
lastWasOp = true;
}else{
if (verbose) System.out.println("Value --> val.push");
valStack.push(t+" ");
lastWasOp = false;
}
if (verbose) System.out.println("Vals: "+valStack+", Ops: "+opStack+", lastWasOp: "+lastWasOp);
}
if (verbose) System.out.println("Eingabe fertig.");
while(!opStack.empty()){
evaluateFunc(valStack, opStack);
if (verbose) System.out.println("pushe Ergebnis "+valStack.peek());
if (verbose) System.out.println("Vals: "+valStack+", Ops: "+opStack);
}
if (valStack.size()!=1)
throw new IllegalArgumentException("valStack nicht leer.");
if (verbose) System.out.println("Berechnung fertig.");
return (String)valStack.pop();
}
/** Wandelt einen RPN-Ausdruck in einen Syntaxbaum um */
public static FuncNode parseRPN(String rpn) {
rpn = filterRPN(rpn);
if (!rpn.endsWith(" ")) rpn+=" ";
Stack stack = new Stack();
while (rpn.length()>0){
int p = rpn.indexOf(" ");
char c = rpn.charAt(0);
String s = rpn.substring(0, p);
if (s.equals("+") || s.equals("-") ||
s.equals("*") || s.equals("/") ||
s.equals("\\") || s.equals("%") ||
s.equals("^") ){
// binaerer Operator
FuncNode v2 = (FuncNode)stack.pop();
FuncNode v1 = (FuncNode)stack.pop();
int op = nameOp(c);
FuncNode n = new FuncNode(op,NOFUNC,0,v1,v2);
stack.push(n);
rpn = rpn.substring(2);
if (verbose) System.out.println("Op: "+n.internal());
}else
if (s.equals("_")){
// unaerer Operator
FuncNode v1 = (FuncNode)stack.pop();
FuncNode n = new FuncNode(NEG,NOFUNC,0,v1,null);
stack.push(n);
rpn = rpn.substring(2);
if (verbose) System.out.println("Neg:"+n.internal());
}else
if (isConst(s)){
FuncNode n=newConst(nameConst(s));
stack.push(n);
rpn = rpn.substring(p+1);
if (verbose) System.out.println("Con:"+n.internal());
}else
if (isVal(s)){
FuncNode n=newZahl(s);
stack.push(n);
rpn = rpn.substring(p+1);
if (verbose) System.out.println("Val:"+n.internal());
}else{
// Funktion
int func = nameFunc(s);
if (func==NOFUNC)
throw new IllegalArgumentException(s);
int op =
(func>=3000) ? FUNC3 :
(func>=2000) ? FUNC2 :
(func>=1000) ? FUNC1 :
FUNC0;
FuncNode v1 = null, v2 = null, v3 = null;
if (func>=3000) // >=3 Parameter, den dritten holen
v3 = (FuncNode)stack.pop();
if (func>=2000) // >=2 Parameter, den zweiten holen
v2 = (FuncNode)stack.pop();
if (func>=1000) // >=1 Parameter, den ersten holen
v1 = (FuncNode)stack.pop();
FuncNode n;
if (op==FUNC3)
n = new FuncNode(op,func,0,new FuncNode[]
{v1,v2,v3});
else
n = new FuncNode(op,func,0,v1,v2);
stack.push(n);
rpn = rpn.substring(p+1);
if (verbose) System.out.println("Fnc:"+n.internal());
}
while (rpn.startsWith(" ")) rpn = rpn.substring(1);
if (verbose) System.out.println("Stack: "+stack+", Rest: "+rpn);
} // while(rpn.length()>0)
FuncNode n = (FuncNode)stack.pop();
return n;
}
}