Problèmes de construction d'arborescence d'expression à partir de la notation postfixe

algorithm expression-trees language-agnostic postfix-notation

Question

J'écris actuellement un impromètre pour les expressions mathématiques simples (constantes et arithmétique simple).

Le problème que je rencontre est la construction d'un arbre d'expression à partir d'une expression au format postfixée. Ce que j'ai fait fonctionne bien dans la plupart des scénarios, mais pas avec cet exemple de Wikipedia .

Si j’évalue l’expression 3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3 , j’obtiens le résultat 3,0001220703125 alors que le résultat devrait être 3,001953125 . La raison en est que l’arbre d’expression ressemble à 3+((4*2)/((1-5)^(2^3))) au lieu de (3+((4*2)/(((1-5)^2)^3))) .

La notation postfixée de l'expression originale ressemble à 3 4 2 * 1 5 âˆ' 2 3 ^ ^ / +

Des suggestions sur la manière d'obtenir l'arbre d'expression tel que je le souhaite?
Ci-dessous est le postfixe du code de l'arbre d'expression et quelques tests qui sont en C # mais qui devraient être assez explicites.

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();
}

Et quelques tests:

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();
}

Réponse acceptée

La page WikiPedia contient cette remarque:

^ est évalué de droite à gauche

Je ne vois pas votre code en tenant compte de cela, ^ est traité de la même façon que les autres opérateurs, comme associatif gauche.

Cela signifie que votre interprétation pourrait être fausse:

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

et votre code et votre réponse d'origine (3 000 1220 703125) sont corrects.




Sous licence: CC-BY-SA with attribution
Non affilié à Stack Overflow
Est-ce KB légal? Oui, apprenez pourquoi
Sous licence: CC-BY-SA with attribution
Non affilié à Stack Overflow
Est-ce KB légal? Oui, apprenez pourquoi