Probleme beim Erstellen des Ausdrucksbaums aus der Postfix-Notation

algorithm expression-trees language-agnostic postfix-notation

Frage

Ich schreibe gerade einen Impreter für einfache mathematische Ausdrücke (Konstanten und einfache Arithmetik).

Das Problem, das ich habe, ist mit dem Aufbau eines Ausdrucksbaums von einem postfix formatierten Ausdruck. Was ich getan habe, funktioniert in den meisten Szenarien gut, aber nicht mit diesem Beispiel aus Wikipedia .

Wenn ich den Ausdruck 3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3 3,0001220703125 , 3,0001220703125 ich das Ergebnis 3,0001220703125 , obwohl das Ergebnis 3,001953125 sein 3,001953125 . Der Grund dafür scheint zu sein, dass der Ausdrucksbaum aussieht wie 3+((4*2)/((1-5)^(2^3))) anstelle von (3+((4*2)/(((1-5)^2)^3))) .

Die Postfix-Notation des ursprünglichen Ausdrucks sieht wie folgt aus 3 4 2 * 1 5 âˆ' 2 3 ^ ^ / +

Irgendwelche Vorschläge, wie man den Ausdrucksbaum bekommt, wie ich es will?
Unten ist das Postfix zu Ausdrucksbaumcode und einigen Tests, die in C # sind, aber sollte ziemlich selbsterklärend sein.

public MathExpression Parse()
{
    var tokens = this.ToPostFix(_tokens);
    var stack = new Stack<MathExpression>();
    foreach(token in tokens)
    {
        if(token.IsOperand())
        {
            // Push the operand on the stack.
            stack.Push(new ConstantExpression(token.Value));
        }
        else
        {
            Debug.Assert(token.Type == TokenType.Operator, "Expected operator.");
            var op = (Operator)token.Value;
            var right = stack.Pop();
            var left = stack.Pop();
            var expression = new ArithmeticExpression(op, left, right);
            stack.Push(expression);
        }
    }
    Debug.Assert(stack.Count == 1, "More than one expression on stack.");
    return stack.Pop();
}

Und einige Tests:

[Test]
public void Wikipedia_Example_Can_Be_Evaluated()
{
    var expected = 3+4*2/(1-5)^2^3; // 3,001953125
    var actual = MathExpression.Parse("3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3")
                               .Evaluate(); // 3,0001220703125
    Assert.AreEqual(expected, actual); // Not equal :(
}

[Test]
public void Can_Convert_To_Prefix()
{
    string expected = "3 4 2 * 1 5 − 2 3 ^ ^ / +"
    string actual = MathExpression.ToPostFix("3+4*2/(1-5)^2^3")
    Assert.AreEqual(expected, actual); // Works as expected
}

Akzeptierte Antwort

Die WikiPedia-Seite enthält diese Bemerkung:

^ wird von rechts nach links ausgewertet

Ich sehe nicht, dass Ihr Code dies berücksichtigt, ^ wird genauso behandelt wie die anderen Operatoren, wie links assoziativ.

Das bedeutet, dass Ihre Interpretation falsch sein könnte:

x ^ 2 ^ 3 => x^(2^3) => x 2 3 ^ ^

und Ihr Code und die ursprüngliche Antwort (30001220703125) sind korrekt.



Lizenziert unter: CC-BY-SA with attribution
Nicht verbunden mit Stack Overflow
Ist diese KB legal? Ja, lerne warum
Lizenziert unter: CC-BY-SA with attribution
Nicht verbunden mit Stack Overflow
Ist diese KB legal? Ja, lerne warum