Funktionsplotter

[qwert10]

Hi,
ich möchte gerne selbst einen Funktionsplotter schreiben. Dabei möchte ich nicht auf eine vorgegebene Lösung zurückgreifen, sondern den Plotter selbst schreiben. Die GUI habe ich schon so gut wie fertig.

Für den Anfang soll der Plotter nur ganzrationale Funktionen und sin cos tan können. Später evtl. gebrochen Rationale Funktionen.

Die Idee ist folgende: der User gibt eine Funktion ein und stellt die Grenzen des zu zeichnenden Bereiches ein (xmin, xman, ymin, ymax).
Nach einigen Eingabeprüfungen wird der eingegebene Funktionsstring dann an eine Methode weitergeleitet die ihn "zerlegt" und so ca. 50 Punkte errechnet die im Intervall ymin bis ymax liegen berechnet.Dann werden mithilfe einem Dreisatz die Werte auf die echte Pixelzahl skaliert. Anschließend wird mit drawPolyline() gezeichnet.

Mein Problem betrifft jetzt die Hauptfunktion, die den Eingabestring so zerlegt, das ich die X-Werte einsetzen kann.Wie wandele ich den Eingabestring am besten so um, das die X-Werte eingesetzt werden können? Das Problem: es müssen natürlich alle mathematischen Rechenregeln beachtet werden. inkl. Klammern.
Also den Inhalt der Methode:

 public void funktionBerechnen(String funktion) {}

Meine bisherigen Ideen (nach Recherche):
1. Im Eingabestring zB. ^ durch Math.pow() ersetzen und irgendwie die Reihenfolge so vertauschen, dass die Potenz berechnet werden kann.^ steht ja hinter dem Term und Math.pow() muss davor. Danach mit so etwas wie eval() ausrechenen (ich habe gelesen das soll mittels einer Java Script Engine in Java gehen)
Vorteil: evtl. einfach umzusetzen
Nachteil: Vertauschen der Reihenfolge? (Wobei ich nichtmal weiß ob das überhaupt möglich ist), falsche
Ausdrücke/ Anfällig für Fehler denke ich mal

2. Einen Parser für die normale (Infix) Notation schreiben. zB. mittels einer Baumstruktur. Da ich so etwas noch nicht geschrieben habe, weiß ich nicht wie kompliziert das ist.
Vorteile:keine Umwandlungen nötig (wie 3. und 4.)
Nachteile: aufwendig zu schreiben nehme ich an

3. Umwandeln des Terms in umgekehrte Polnische Notation und anschließendes Berechnen. Nach einer Suche bei Wikipedia bin ich auf den: Shunting Yard Algorithmus gestoßen, der genau dafür da ist.
Vorteile: das anschließende Parsen des Strings der in UPN vorliegt ist relativ einfach.
Nachteile: sicherlich noch aufwendiger als 2.

4. Umwandeln des Termes in normale Polnische Notation. Hintergrund: die normalen Java Operatoren verwenden diese Notation soweit ich gelesen habe.
Vorteil: Ein Vertauschen der Reihenfolge wie bei 3. und 1. nötig entfällt.
Nachteile: Ich habe noch keinen Algorithmus gefunden zum direkten Umwandeln in normale Polnische Notation.

Nun die Frage : Was würdet ihr machen ? Ich tendiere zu 2. Was ist am aufwendigsten? Gibt es noch andere einfachere Möglichkeiten?

Viele Grüße
qwert10

 

[AndiE]

Ich würde es gar nicht so machen. Wenn dein Fokus auf dem Funktionsplotter liegt, solltest du dir die Eingabe so leicht wie möglich machen. Ich würde das System "Hornerschema" nutzen.

Das Gundprinzip ist, dass

(((((((...(a*x)x+b)*x+c)*x* ...+z=a*x^n+b*b^n-1+...+z

ist, wobei man
z=z*x^x^0

setzen kann.

Umsetzen würde ich das in einem Dialog, wo durch Eingabe der Koeffizienten die Fomel aufgebaut wird.

Dann ersparst du dir die ganze Parserarbeit, und kannst deine Funktionen leicht plotten. Dass diese dem User in Normalform vorliegen müssen, ist ein Kompromiss, den du als offensichtlicher Anfänger eingehen solltest.

Gruß

Andre'

 

[DrZoidberg]

Die einfachste Möglichkeit wäre, wenn man die Gleichung direkt in UPN Form in dein Programm eingibt.

 

[qwert10]

Hi,
erstmal danke für die Antworten. Ich habe mir jetzt das Hornerschema
angeschaut. Ich denke das ist die einfachste Möglichkeit eine ganzrationale Funktion zu plotten. Doch der Kompromiss die Koeffizienten im einem Dialog abfragen zu müssen, ist für den Benutzer recht umständlich und was mache ich mit sin/cos/tan ? Da ich jedoch relativ viel Zeit für die Aufgabe habe, möchte ich gerne eine bessere Lösung schreiben die später auch um gebrochen Rationale Funktionen erweitert werden kann und auch mit sin/cos/tan/ln umgehen kann.

Die einfachste Möglichkeit wäre, wenn man die Gleichung direkt in UPN Form in dein Programm eingibt.

Das ist natürlich klar. Aber der Benutzer soll die Funktion schon in Normalform eingeben können.

Ich möchte also einen Parser schreiben. Kann mir jemand dazu ein paar Tipps geben oder zumindest das Prinzip kurz erklären? Ist es aufwendiger einen Parser für die normale Notation zu schreiben oder erst in UPN umzuwandeln und dann einen (viel einfacheren) Parser zu schreiben?

Viele Grüße
qwert10

 

[DrZoidberg]

Also ich finde es einfacher erst nach UPN umzuwandeln.
Hier mal ein Beispiel

public static List<Object> tokenize(String str) {
        ArrayList<Object> list = new ArrayList<>();
        Matcher m = Pattern.compile("[.\\d]+|[A-Za-z]+|\\S+?").matcher(str);
        while(m.find()) {
            String token = m.group();
            try {
                list.add(Double.valueOf(token));
            } catch(NumberFormatException e) {
                list.add(token);
            }
        }
        for(int i = 0; i < list.size(); i++) {
            Object o = list.get(i), p = i==0?null:list.get(i-1);
            if(o.equals("+") || o.equals("-")) {
                if(p == null || !(p.equals(")") || p.equals("x") || (p instanceof Double))) {
                    list.set(i, "unary" + o);
                }
            }
        }
        return list;
    }
    
    private static int getPriority(String operator) {
        switch(operator) {
            case "+": case "-": return 1;
            case "*": case "/": return 2;
            case "^": return 3;
            case "sin": case "cos": case "tan": case "unary-": case "unary+": return 4;
            case "(": return 0;
        }
        throw new IllegalArgumentException(operator);
    }
    
    public static List<Object> toUPN(List<Object> input) {
        ArrayList<Object> output = new ArrayList<>();
        LinkedList<Object> stack = new LinkedList<>();
        for(Object token: input) {
            if(token instanceof Double || token.equals("x")) output.add(token);
            else if(token.equals("(")) stack.push(token);
            else if(token.equals(")")) {
                while(!stack.peek().equals("(")) output.add(stack.pop());
                stack.pop();
            }
            else {
                while(!stack.isEmpty() && getPriority((String)stack.peek()) >= getPriority((String)token)) {
                    output.add(stack.pop());
                }
                stack.push(token);
            }
        }
        while(!stack.isEmpty()) output.add(stack.pop());
        return output;
    }
    
    public static double eval(List<Object> upn, double x) {
        LinkedList<Double> stack = new LinkedList<>();
        for(Object token: upn) {
            if(token instanceof Double) stack.push((Double)token);
            else if(token.equals("x")) stack.push(x);
            else {
                switch((String)token) {
                    case "+": stack.push(stack.pop() + stack.pop()); break;
                    case "-": stack.push(-stack.pop() + stack.pop()); break;
                    case "*": stack.push(stack.pop() * stack.pop()); break;
                    case "/": stack.push(1.0/stack.pop() * stack.pop()); break;
                    case "^": double exp = stack.pop(), n = stack.pop();
                              stack.push(Math.pow(n, exp)); break;
                    case "unary+": break;
                    case "unary-": stack.push(-stack.pop()); break;
                    case "sin": stack.push(Math.sin(stack.pop())); break;
                    case "cos": stack.push(Math.cos(stack.pop())); break;
                    case "tan": stack.push(Math.tan(stack.pop())); break;
                }
            }
        }
        if(stack.size() != 1) throw new RuntimeException();
        return stack.pop();
    }
    
    public static void main(String[] args) throws Exception {
        String str = "-3*x^2+sin(x)";
        List<Object> tokens = tokenize(str);
        System.out.println(tokens);
        List<Object> upn = toUPN(tokens);
        System.out.println(upn);
        double result = eval(upn, 2);
        System.out.println(result);
    }

 

[qwert10]

Vielen Dank für den Hinweis. Ich werde es jetzt versuchen mit UPN umzusetzen.

Danke
qwert10