Shunting-Yard-Algorithmus (Funktionsplotter)

Simii123 · 12. Januar 2015

Hallo Ihr lieben,

ich bin momentan in der Endphase meiner Studienarbeit. Die Aufgabe besteht darin, einen Funktionsplotter in Android zu realisieren. Mithilfe vom Shunting-Yard-Alogrithmus möchte ich die eingegebene Funktion in die Umgekehrte Polnische Notatoin überführen und dann mit verschiedenen x-Werten auswerten. Dazu möchte ich das Ergebnis des Shunting-Yards (also bei 5+3 bspw. 53+) in einem Textview ausgeben. Der Code sieht folgendermaßen aus:

Java

import java.util.*;  
public class ShuntingYard {   
  
private enum Operator   {         
ADD(1), SUBTRACT(2), MULTIPLY(3), DIVIDE(4);         
final int precedence;         
Operator(int p) { precedence = p; }     
}      
private Map&lt;String, Operator&gt; ops = new HashMap&lt;String, Operator&gt;() {{         
put("+", Operator.ADD);         
put("-", Operator.SUBTRACT);         
put("*", Operator.MULTIPLY);         
put("/", Operator.DIVIDE);     }}; 
    
 private boolean isHigerPrec(String op, String sub)     {         
return (ops.containsKey(sub) && ops.get(sub).precedence &gt;= ops.get(op).precedence);     }      


public TextView RPN(View view)     {


String Function = getIntent().getStringExtra("funktion");
StringBuilder output = new StringBuilder();         
Deque&lt;String&gt; stack  = new LinkedList&lt;&gt;();          


for (String token : Function.split("\\s")) {            
 // operator            
if (ops.containsKey(token)) {                 
while ( ! stack.isEmpty() && isHigerPrec(token, stack.peek()))                    
output.append(stack.pop()).append(' ');                 
stack.push(token);             
 // left parenthesis             
}else if (token.equals("(")) {                 
stack.push(token);             
 // right parenthesis             
} else if (token.equals(")")) {                
 while ( ! stack.peek().equals("("))                     
output.append(stack.pop()).append(' ');                 
stack.pop();              
// digit            
 } else {                 
output.append(token).append(' ');            
 }         
}         
 while ( ! stack.isEmpty())             
output.append(stack.pop()).append(' ');         
 output.toString()
Output.setText(output)
return Output
 }  
}

Alles anzeigen

Leider erhalte ich als Ergebnis nur genau das eingegebene, nichts verändertes. Weiß jemand, woran das liegen könnte?

Psychosadistic · 12. Januar 2015

Bestimmt wird noch wer anders helfen, nur gebe ich dir schon einmal das hier als Hilfe - http://rosettacode.org/wiki/Pa…nting-yard_algorithm#Java
Vielleicht hilft dir das ja bei der Fehlersuche weiter.

Ich werde mich demnächst damit auseinandersetzen und dir dann dementsprechend versuchen zu helfen, sollte sich denn niemand gemeldet haben.

Simii123 · 12. Januar 2015

Der Code ist von der Seite habe ihn nur ein wenig umgeändert, den "Hauptteil" ins TextView gesteckt, dort die Variablenübergabe aus der vorigen Activity eingesetzt und am Ende den Output wieder in ein TextView gesteckt...Wäre super wenn du meinen Fehler findest

Psychosadistic · 12. Januar 2015

Du kannst deine eigenen Eintragungen in das Textfeld oben vornehmen, auf den Button klicken und eine Ausgabe erhalten - Fehler werden nicht abgefangen.

ShuntingYard.java (dein eigenes Package nicht vergessen ganz oben zu belassen!)

Java

import android.support.v7.app.ActionBarActivity;
import android.os.Bundle;
import android.view.View;
import android.widget.EditText;
import android.widget.TextView;
import android.widget.Toast;


import java.util.*;


public class ShuntingYard extends ActionBarActivity {


    private enum Operator
    {
        ADD(2), SUBTRACT(2), MULTIPLY(3), DIVIDE(3), UP(4);
        final int precedence;
        Operator(int p) {
            precedence = p;
        }
    }


    private Map&lt;String, Operator&gt; ops = new HashMap&lt;String, Operator&gt;() {{
        put("+", Operator.ADD);
        put("-", Operator.SUBTRACT);
        put("*", Operator.MULTIPLY);
        put("/", Operator.DIVIDE);
        put("^", Operator.UP);
    }};


    private boolean isHigherPrec(String op, String sub)     {
        return (ops.containsKey(sub) && ops.get(sub).precedence &gt;= ops.get(op).precedence && ops.get(sub).precedence != 4);
    }


    public String RPN(String toNewNot)     {


        StringBuilder output = new StringBuilder();
        Deque&lt;String&gt; stack  = new LinkedList&lt;&gt;();


        for (String token : toNewNot.split("\\s")) {
            // operator


            if (ops.containsKey(token)) {


                while (!stack.isEmpty() && isHigherPrec(token, stack.peek()))
                    output.append(stack.pop()).append(' ');
                stack.push(token);
                // left parenthesis
            }


            else if (token.equals("(")) {
                stack.push(token);
                // right parenthesis
            }


            else if (token.equals(")")) {


                while (!stack.peek().equals("("))
                    output.append(stack.pop()).append(' ');
                stack.pop();
                // digit
            }
            else {
                output.append(token).append(' ');
            }
        }
        while (!stack.isEmpty())
            output.append(stack.pop()).append(' ');
        return output.toString();
    }


    @Override
    protected void onCreate(Bundle savedInstanceState) {
        super.onCreate(savedInstanceState);
        setContentView(R.layout.activity_main);
    }


    public void onClick(View view) {
        EditText editText = (EditText) findViewById(R.id.editText);


        if (editText.getText().toString().equals("")) {
            Toast.makeText(getApplicationContext(),"In das Textfeld muss etwas eingegeben werden!",Toast.LENGTH_SHORT).show();
        }
        else {
            ((TextView) findViewById(R.id.textView)).setText("RPN: "+RPN(editText.getText().toString()));
        }
    }
}

Alles anzeigen

activity_main.xml

HTML

&lt;RelativeLayout xmlns:android="http://schemas.android.com/apk/res/android"
    xmlns:tools="http://schemas.android.com/tools" android:layout_width="match_parent"
    android:layout_height="match_parent" android:paddingLeft="@dimen/activity_horizontal_margin"
    android:paddingRight="@dimen/activity_horizontal_margin"
    android:paddingTop="@dimen/activity_vertical_margin"
    android:paddingBottom="@dimen/activity_vertical_margin" tools:context=".MainActivity"&gt;


    &lt;EditText
        android:layout_width="fill_parent"
        android:layout_height="wrap_content"
        android:id="@+id/editText"
        android:layout_alignParentTop="true"
        android:layout_centerHorizontal="true" /&gt;


    &lt;TextView
        android:layout_width="fill_parent"
        android:layout_height="wrap_content"
        android:textAppearance="?android:attr/textAppearanceLarge"
        android:id="@+id/textView"
        android:layout_alignParentBottom="true"
        android:layout_centerHorizontal="true" /&gt;


    &lt;Button
        android:layout_width="wrap_content"
        android:layout_height="wrap_content"
        android:text="Klick mich!"
        android:id="@+id/clickButton"
        android:layout_centerVertical="true"
        android:layout_centerHorizontal="true"
        android:onClick="onClick"/&gt;
&lt;/RelativeLayout&gt;

Alles anzeigen

Simii123 · 12. Januar 2015

Vielen Dank schonmal für die Antwort! Habe das EditText entfernt, weil die Funktion, mit der der Algorithmus durchgeführt wird, aus einer anderen Activity kommt und deswegen ja schon bestimmt ist...die methode onClick() sieht jetzt so aus:

Code

public void onClick(View view) {
        String Function = getIntent().getStringExtra("funktion"); 
 textView.setText("RPN: " + RPN(Function));    }

Der String Function wird aus der anderen Activity geholt, dann soll der Algorithmus durchgeführt werden. An diesem selbst habe ich nichts verändert, nur leider kommt bei Eingabe von bspw. 6+4 auch als Ausgabe 6+4 und es müsste doch eigentlich 64+ als Ergebnis kommen..

Psychosadistic · 12. Januar 2015

Da müssen Leerzeichen zwischen den jeweiligen Zeichen sein.

6+4
nicht richtig

6 + 4
richtig

Simii123 · 12. Januar 2015

Achso okay, ja super, dann funktioniert es DANKE!

Simii123 · 12. Januar 2015

Trotzdem noch eine kurze Frage...woran im code erkenne ich, dass da Leerzeichen sein müssen? Wäre da ja nie selbst draufgekommen

Psychosadistic · 12. Januar 2015

Oh Gott ...
Habe das voll verpennt - hier:

Java

for (String token : toNewNot.split("\\s"))

Du splittest nach jedem Leerzeichen, ich habe das verwechselt, dachte \\s wäre einfach ein leerer String, haha.
Dementsprechend erhält er Folgendes bei "6+4":
Er erhält als "token" eben "6+4".

Solltest du solche Schreibweisen bevorzugen, müsstest du das obige \\s durch ein "" austauschen; ich jedoch würde es so stehen lassen.
Bei "6 + 4" durchläuft er die for-Schleife 3x, da er "6", "+" und "4" als "token" bekommt und diese dementsprechend abhandeln kann.

Marco Feltmann · 13. Januar 2015

Wäre es nicht einfacher, via StringBuilder den jeweilige Operatoren zu suchen, herauszuschneiden und hinten an zu fügen?
Oder habe ich nur die Möglichkeit einer komplexeren Gleichung übersehen?

Psychosadistic · 13. Januar 2015

Zitat von Marco Feltmann

Wäre es nicht einfacher, via StringBuilder den jeweilige Operatoren zu suchen, herauszuschneiden und hinten an zu fügen?
Oder habe ich nur die Möglichkeit einer komplexeren Gleichung übersehen?

Code

infix:   3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3
postfix: 3 4 2 * 1 5 - 2 3 ^ ^ / +

Einfaches Anfügen ist da leider nicht so 'einfach'. Oder habe ich deine Idee nur halb-richtig interpretiert?

Marco Feltmann · 13. Januar 2015

Nö, Deine Interpretation passt scho.

Shunting-Yard-Algorithmus (Funktionsplotter)

Jetzt mitmachen!

Teilen