Selber das Rechnen programmieren?

[lisali]

Hallo,

ich bin gerade dabei Java zu lernen und möchte gerne folgende Aufgabe lösen:

Arithmetic Expression Evaluation

An important application of stacks is in parsing. For example, a compiler must parse arithmetic expressions written using infix notation. For example the following infix expression evaluates to 212:

( 2 + ( ( 3 + 4 ) * ( 5 * 6 ) ) )

We break the problem of parsing infix expressions into two stages. First, we convert from infix to a different representation called postfix. Then we parse the postfix expression, which is a somewhat easier problem than directly parsing infix.

Evaluating a postfix expression. A postfix expression is:

2 3 4 + 5 6 * * +

First, we describe how to parse and evaluate a postfix expression. We read the tokens in one at a time. If it is an integer, push it on the stack; if it is a binary operator, pop the top two elements from the stack, apply the operator to the two elements, and push the result back on the stack. Program Postfix.java reads in and evaluates postfix expressions using this algorithm.
Converting from infix to postfix. Now, we describe how to convert from infix to postfix. We read in the tokens one at a time. If it is an operator, we push it on the stack; if it is an integer, we print it out; if it is a right parentheses, we pop the topmost element from the stack and print it out; if it is a left parentheses, we ignore it. Program Infix.java reads in an infix expression, and uses a stack to output an equivalent postfix expression using the algorithm described above.

Könnte mir vielleicht jemand behilflich sein und mir sagen wie genau ich überhaupt anfangen müsste oder könnte?
Es heißt ja, dass aller Anfang schwer ist und ich tue mir hierbei gerade total schwer und wäre echt dankbar für etwas Hilfe.

Dankeschön im Voraus!

 

[Carron]

Hallo,

beginnen würde ich einfach mich dem Befolgen der gegebenen Anweisungen (jedoch würde ich der Logik einer Verarbeitung folgend erst die infix zu postfix Konvertierung machen und danach die postfix Berechnung ausführen.

import java.util.Stack;

/**
 * Convert from infix to postfix.<br>
 * We read in the tokens one at a time. If it is an operator, we push it on the
 * stack; if it is an integer, we print it out; if it is a right parentheses, we
 * pop the topmost element from the stack and print it out; if it is a left
 * parentheses, we ignore it. Program Infix.java reads in an infix expression,
 * and uses a stack to output an equivalent postfix expression using the
 * algorithm described above.</br>
 */
public class Infix {

    private final Stack<Character> operators = new Stack<Character>();
    private final StringBuffer postfix = new StringBuffer();

    public Infix(final String expression) {
        // read in the tokens one at a time
        for (String singleToken : expression.split("[ ]")) {
            handleToken(singleToken);
        }
    }
    
    public String getPostfix() {
        return this.postfix.toString();
    }

    private void handleToken(final String token) {
        if (token.length() == 1) {
            switch (token.charAt(0)) {
                case '(':
                    /*
                     * if it is a left parentheses, we ignore it
                     */
                    return;
                case '+':
                    // If it is an operator, we push it on the stack
                    this.operators.add('+');
                    return;
                case '-':
                    // If it is an operator, we push it on the stack
                    this.operators.add('-');
                    return;
                case '*':
                    // If it is an operator, we push it on the stack
                    this.operators.add('*');
                    return;
                case '/':
                    // If it is an operator, we push it on the stack
                    this.operators.add('/');
                    return;
                case ')':
                    /*
                     * if it is a right parentheses, we pop the topmost element
                     * from the stack and print it out
                     */
                    this.postfix.append(this.operators.pop() + " ");
                    return;
            }
        }
        /*
         * if it is an integer, we print it out
         */
        this.postfix.append(token + " ");
    }
}

import java.util.Stack;

/**
 * Parse and evaluate a postfix expression.<br>
 * We read the tokens in one at a time. If it is an integer, push it on the
 * stack; if it is a binary operator, pop the top two elements from the stack,
 * apply the operator to the two elements, and push the result back on the
 * stack. Program Postfix.java reads in and evaluates postfix expressions using
 * this algorithm.</br>
 */
public class Postfix {

    private final Stack<Integer> integers = new Stack<Integer>();

    public Postfix(final Infix expression) {
        // read the tokens in one at a time
        for (String singleToken : expression.getPostfix().split("[ ]")) {
            handleToken(singleToken);
        }
    }
    
    public int getResult() {
        return this.integers.get(0).intValue();
    }

    private void handleToken(final String token) {
        if (token.length() == 1) {
            switch (token.charAt(0)) {
                /*
                 * if it is a binary operator, pop the top two elements from the
                 * stack,
                 * apply the operator to the two elements, and push the result
                 * back on the
                 * stack
                 */
                case '+':
                    applyOperator('+');
                    return;
                case '-':
                    applyOperator('-');
                    return;
                case '*':
                    applyOperator('*');
                    return;
                case '/':
                    applyOperator('/');
                    return;
            }
        }
        /*
         * If it is an integer, push it on the stack
         */
        this.integers.add(Integer.valueOf(token));
    }

    /**
     * pop the top two elements from the stack,
     * apply the operator to the two elements, and push the result back on the
     * stack
     * 
     * @param operator operator to apply
     */
    private void applyOperator(final char operator) {
        Integer result = null;
        switch (operator) {
            case '+' : result = Integer.valueOf(this.integers.pop() + this.integers.pop());break;
            case '-' : result = Integer.valueOf(this.integers.pop() - this.integers.pop());break;
            case '*' : result = Integer.valueOf(this.integers.pop() * this.integers.pop());break;
            case '/' : result = Integer.valueOf(this.integers.pop() / this.integers.pop());break;
            default : // something bad happened...
        }
        this.integers.add(result);
    }
}

 

[FrankBooth]

Hallo,

also was Carron gemacht hat ist ziemlich einfach. Er hat seinen Browser geöffnet, google aufgerufen und dann für seine erst Klasse 'infix zu postfix Java' eingegeben.
Den Code den er gefunden hat, hat er hier reinkopiert und dir gesagt so geht es. Das hat er dann für die 2. Klasse wiederholt.
Solltest du jedoch an einer eigenen Lösung interessiert sein bzw. eine eigenen Lösung umsetzen wollen, würde ich folgendes machen:

Ich würde das Programm selber schreiben!
Das war nach meiner Interpretation auch deine Frage, aber nicht Carrons Antwort.

Wie geht man dabei vor? (Ich glaube, das war deine Frage)

1. String (mathematische Formel) übergeben oder einlesen.
2. Jeden char des Strings analysieren, wenn es:
- '(' ist ignorieren wir es
- ist es ein Rechenoperator , dann speichern wir ihn in einem Stack
- ist es eine Zahl, wird sie ausgegeben
- ist es ')' geben wir den ersten Operator von unserem Stack aus

das macht aus ( 2 + ( ( 3 + 4 ) * ( 5 * 6 ) ) ) ----> 2 3 4 + 5 6 * * +

Das kann man ausgeben oder in einen String schreiben.
Schreibst du es in einen String ist das die Vorbereitung für die Berechnung.
Wie berechnet man das?

Du gehst deinen String durch,
- wenn du eine Zahl findest schreibst du sie wieder in einen Ergebnisstack
- wenn du einen Operator findest holst du die beiden obersten Zahlen vom Stack, verrechnest sie mit dem Operator und packst das Ergebnis wieder auf den Stack.

am Ende steht das Ergebnis in deinem Stack

Beispiel Postfix: 234+56**+

Stack : 2,3,4 dann kommt das '+'
--> Stack : 2,7,5,6 dann kommt das '*'
--> Stack : 2,7,30 dann kommt das '*'
--> Stack : 2,210 dann kommt das '+'
--> Stack 212

ENDE

Wichtig ist, dass du wirklich Stacks benutzt, also LIFO Last In, Fist Out

Das war der mathematische Teil!

Was musst du noch zu Java wissen oder reicht das hier erst?

Grüße!

 

[Carron]

Hey Frank,

mir zu unterstellen, ich würde hier nur Copy & Paste machen ist durchaus unangebracht. Dann hätte ich genauso gut den Link dazu posten können...
Ich habe den Code heute morgen bevor ich auf Arbeit gefahren bin von Grund auf selbst geschrieben und als Kommentare einfach nur die gegebene Aufgabenstellung eingefügt um das Ganze nachvollziehbar zu gestalten.

Wieder zur Sache:
Das zeichenweise Auslesen (im Gegensatz zum von mir verwendeten .split("[ ]")) wird bei Zahlen mit mehreren Ziffern Probleme bereiten.
Der von dir vorgeschlagene Weg funktioniert (auf den ersten Blick) leider nur für Zahlen von 0 bis 9. Darüber hinaus hast du wohl mit deiner Antwort tatsächlich eher die Bedürfnisse von lisali getroffen. (Da ich aber auch erst vor Kurzem mit Java angefangen habe und noch immer lerne, habe ich einfach den von mir persönlich präferierten Weg gewählt: Beispielcode)


@lisali
Ich habe versucht den Code so simpel wie möglich zu halten. Für Nachfragen stehe ich natürlich gern zur Verfügung. Da ich dir Englischkenntnisse unterstelle, habe ich auf die Einzelübersetzungen verzichtet, aber Frank hat das ja nachgeliefert. Das macht es natürlich übersichtlicher.

Grundsätzlich hilft es aus der Aufgabenstellung jeden zu behandelnden Fall herauszutrennen und für jeden Fall die paar Codezeilen zu dessen Umsetzung zu schreiben. Im zweiten Schritt kann man dann das Bedingungsgerüst drumherum bauen um beim Eintreten der einzelnen Fälle die jeweiligen Code-Schnipsel bzw. Methoden auszuführen/aufzurufen.


Viele Grüße
Carron

 

[FrankBooth]

Hallo,

gut, selber geschrieben.
Einwand richtig, mit Zahlen 0 - 9!

Trotzdem null Erläuterung zu deinem Code. Die Aufgabenstellung wiedergegeben (erst umwandeln dann berechnen) und Code hingeklatscht.
Ich finde das unangebracht! Hier ging es nicht um Code, sondern um selberschreiben und Tipps für die Umsetzung.

 

[Akeshihiro]

Das Auswerten der einzelnen Zeichen ist ja nun nicht wirklich das Problem. Im Moment können im Beispiel von Frank zwar nur Zahlen von 0 bis 9 ausgewertet werden, aber wenn man eine Zahl hat, könnte man einfach das nächste Zeichen auswerten und wenn es auch eine Zahl ist, dann wird diese eben der vorherigen hinzugefügt und das so lange, bis man auf ein Nicht-Zahl-Zeichen stößt. Ist das der Fall, kann man die zusammengesetzte Zahl parsen und gut is, also daran soll es ja nun wirklich nicht scheitern.

 

[lisali]

Also, erstmal vielen Dank für all die Mühe. Ich weiß das wirklich zu schätzen!

Erstmal... wieso macht das dann das daraus?

"das macht aus ( 2 + ( ( 3 + 4 ) * ( 5 * 6 ) ) ) ----> 2 3 4 + 5 6 * * +"

Da ist doch auch noch ein Plus als Operator nach der ersten 2?

Und wieso schreibe ich eigentlich in den Stack hinein?

Und wenn ich den Code benutze bzw. die 2 Klassen, wie genau kann ich es testen bzw. starten? Muss ich dazu eine Extraklasse schreiben/haben?

Vielen Dank nochmals!

 

[Carron]

Der Ausdruck ( 2 + ( ( 3 + 4 ) * ( 5 * 6 ) ) ) wird in seine einzelnen Bestandteile zerlegt und da nach dem ( 2 + (...)) der Rest in Klammern steht, wird diese Teiloperation als letztes ausgeführt und das dazugehörige "+" steht ganz am Ende.

Das hat Frank recht gut zusammengefasst wie ich finde:

Beispiel Postfix: 234+56**+

Stack : 2,3,4 dann kommt das '+'
--> Stack : 2,7,5,6 dann kommt das '*'
--> Stack : 2,7,30 dann kommt das '*'
--> Stack : 2,210 dann kommt das '+'
--> Stack 212

ENDE

Die Verwendung des Stacks war erstens in der Aufgabenstellung so verlangt und zweitens benötigt man für jede Teiloperation (a + b) bzw. (c * d) immer den absoluten Werte beider miteinander zu verbindender Variablen.
Oder anders: der Stack sorgt dafür, dass man den Klammern gemäß von Innen nach Außen vorgeht.

Wenn du die zwei Klassen nutzen möchtest, kannst du entweder in eine von beiden eine main()-Methode einfügen oder eine separate Testklasse schreiben (auf jeden Fall sauberer, falls du noch eine Aufgabe bekommen solltest, bei der du die Umrechnerei nochmal brauchst).

Hiermit sollte es gehen:

/**
 * Testklasse fuer die Anwendung von Infix-zu-Postfix-Formatierung und
 * anschliessender Auswertung des erzeugten Postfix-Strings.<br>
 * Zur Vereinfachung verzichten wir in diesem Beispiel mal auf eine grafische
 * Oberflaeche und lesen nur eine Konstante ein und geben die Ergebnisse in
 * der Konsole aus.</br>
 */
public class ExpressionTester {

    /**
     * Aus dieser Konstante wird der zu bearbeitende Ausdruck entnommen.
     */
    private static final String INFIX_EXPRESSION = "( 2 + ( ( 3 + 4 ) * ( 5 * 6 ) ) )";

    /**
     * Eigentliche auszufuehrende Methode
     * 
     * @param args
     *        Zusatzargumente haben wir nicht, brauchen wir nicht, beachten wir
     *        nicht
     */
    public static void main(String[] args) {
        // Ausgeben des Infix-Ausdrucks
        System.out.println("INFIX:    " + INFIX_EXPRESSION);
        // Einlesen des Infix-Ausdrucks und Erzeugen der Postfix-Entsprechung
        Infix parsedInfix = new Infix(INFIX_EXPRESSION);
        // Ausgeben des erzeugten Postfix-Ausdrucks
        System.out.println("POSTFIX:  " + parsedInfix.getPostfix());
        // Einlesen des Postfix-Ausdrucks und Berechnen des Ergebnisses
        Postfix evaluatedPostfix = new Postfix(parsedInfix);
        // Ausgeben des berechneten Ergebnisses
        System.out.println("ERGEBNIS: " + evaluatedPostfix.getResult());
    }

}

 

[xgrnsxs]

Das Problem mit den Zahlen von 0-9 stimmt so nicht.

Wenn ihr den String einlest und alle numerischen Zeichen (es gibt eine Methode die in einem String zwischen Buchstaben und Zahlen unterscheiden kann) bis zum nächsten Operator oder ( oder ) zusammen in einen "temporären" String kopiert und dann mittels Integer.parseInt(String temp) auf euren Stack pusht, dann könnt ihr auch mehrstellige Zahlen benutzen...

 

[rhô]

Hey,

mein Vorschlag wäre sich mal die Klasse Scanner in java.util anzusehen. Sie besitzt eine Methode nextInt(), die die nächste Zahl zurückgibt. Man kann das Programm so auch leicht für Kommazahlen modifizieren, indem man einfach statt nextInt() nextDouble() einfügt.