Assess () récursif dans la classe de l'arbre d'expression

evaluate expression-trees java methods recursion

Question

Je suis nouveau en Java et j'essaie d'ajouter une méthode d'évaluation à ma classe. La classe ExpTree et son programme de test m’ont été donnés. J'ai écrit mon code comme j'ai appris en classe, mais je ne sais pas pourquoi cela ne fonctionne pas.

Une méthode d'évaluation (), qui renvoie l'évaluation arithmétique de ExpTree. Cela doit être fait de manière récursive, vous aurez donc besoin de 2 méthodes pour le faire. Dans le cas où il en résulterait une division ou un mod par 0, il devrait émettre une nouvelle exception ArithmeticException avec une chaîne descriptive. Si l'arbre est vide, assessment () devrait également lancer une nouvelle exception ArithmeticException avec une chaîne descriptive.

Voici mon code:

// This will implement an "Expression Tree" which stores an arithmetic expression

import java.util.*;

public class ExpTree
{
    //-------data
    private ExpNode root;

    //-------constructor
    public ExpTree()
    {
        root = null;
    }

    //constructor where a string is passed in.  It is parsed and stored
    public ExpTree(String expString)
    {
        //declare StringTokenizer, Stacks, and other variables used in parsing
        StringTokenizer tokenizer = new StringTokenizer (expString, "()+-*/%", true);
        String token;
        ExpNode operator, leftOperand, rightOperand;
        Stack<ExpNode> operators = new Stack<ExpNode>();
        Stack<ExpNode> operands = new Stack<ExpNode>();

        //break up expString into tokens
        while (tokenizer.hasMoreTokens())
        {
            token = tokenizer.nextToken();

            // if the current token is a left paren, ignore it
            if (token.equals ("("))
                ;

            // if the current token is an operator, put it on the
            // operator stack
            else if ((token.equals ("+")) || (token.equals ("-")) ||
                        (token.equals ("*")) || (token.equals ("/"))  || (token.equals ("%")))
                operators.push (new ExpNode(token));

            //if the current token is a right paren, pop the operators stack
            //to get the operator, pop the operands stack twice to get the two
            //operands (stored as expression trees).   Then make the two operands
            //children of the operator and push back on the operands tree.
            else if (token.equals (")"))
            {
                operator = operators.pop();

                rightOperand = operands.pop();
                leftOperand = operands.pop();

                operator.setLeft(leftOperand);
                operator.setRight(rightOperand);

                operands.push(operator);
            }

            //otherwise, the token should be a number - put it in the operands stack
            else
                operands.push (new ExpNode(token));

        } // while (tokenizer.hasMoreTokens())

        //when finished parsing, the operands stack should contain the fully-built
        //expression tree.
        if (!operands.isEmpty())
            root = operands.pop();
    }

    //-------methods

    //isEmpty()
    public boolean isEmpty()
    {
        return (root == null);
    }

    //printTree methods - prints the tree in RNL order, with indents.  Called from "outside"
    public void printTree()
    {
        if (root == null)
            System.out.println("The tree is empty");
        else
            printTree(root, 0);    //start with the root with 0 indentations
    }

    //recursive, private version of printTree
    private void printTree(ExpNode subTree, int indents)
    {
        //if there is a right side, handle it first (with 1 more indent)
        if (subTree.getRight() != null)
            printTree(subTree.getRight(), indents+1);

        //then print the node itself (first move over the right amount of indents)
        System.out.println("\n\n\n");
        for (int i=0; i<indents; i++)
            System.out.print("\t");
        System.out.println(subTree);

        //if there is a left side, handle it first (with 1 more indent)
        if (subTree.getLeft() != null)
            printTree(subTree.getLeft(), indents+1);
    }

    //inorder traversal - starts the recursive calls to print inorder
    public String inOrder()
    {
        return inOrder(root);
    }

    //inorder traversal - recursive left side of tree, print node, right side of tree
    private String inOrder(ExpNode theTreeToTraverse)
    {
        if (theTreeToTraverse == null)
            return "";   //don't try to do anything if tree is null

        //else build up a String to return.  It will involve recursive calls
        String returnString = "";
        if (theTreeToTraverse.getLeft() != null)
        {
            returnString += "(" + inOrder(theTreeToTraverse.getLeft());
        }
        returnString += theTreeToTraverse;
        if (theTreeToTraverse.getRight() != null)
        {
            returnString += inOrder(theTreeToTraverse.getRight()) + ")";
        }

        return returnString;
    }

    //public version of evaluate  
    public double evaluate(){
    if (root == null)       //Am I null?
    throw new ArithmeticException("The tree is empty, nothing to be evaluated!");

    else                    //You handle it!
        return recursiveEvaluate(root);  
    }

    //Recursive version of evaluate
    private double recursiveEvaluate(ExpNode subTree){
        //If subTree is empty
        if (subTree == null)
            return 0;

    //What are you subTree? A number? An operator? 
    else if(subTree.getData().equals("+"))
        return recursiveEvaluate(subTree.getLeft()) +
                recursiveEvaluate(subTree.getRight()) ;

    else if(subTree.getData().equals("-"))
        return recursiveEvaluate(subTree.getLeft()) -
                recursiveEvaluate(subTree.getRight()) ;

    else if(subTree.getData().equals("*"))
        return recursiveEvaluate(subTree.getLeft()) *
                recursiveEvaluate(subTree.getRight()) ;

    else if(subTree.getData().equals("/")){
        double right = recursiveEvaluate(subTree.getRight());

    if(right == 0.0)
        throw new ArithmeticException("Divide by zero is undefined!");
            return recursiveEvaluate(subTree.getLeft()) / right;
    }

    else if(subTree.getData().equals("%")){
        double right = recursiveEvaluate(subTree.getRight());

    if(right == 0.0)
        throw new ArithmeticException("Mod by zero exception");
            return recursiveEvaluate(subTree.getLeft()) % right;
    }

    //Converting String type to double
    else
        return Double.parseDouble(subTree.getData());

    }

    //Public version of numPlus
    public int numPlus(){
        return recursiveNumPlus(root);
    }

    //Recursive version of numPlus
    private int recursiveNumPlus(ExpNode subTree){
        if (subTree == null)
            return 0;

    //If you are a '+' sign
    if(subTree.getData().equals("+"))
        return recursiveNumPlus(subTree.getLeft()) +
                recursiveNumPlus(subTree.getRight()) + 1;

    else
        return recursiveNumPlus(subTree.getLeft()) +
                recursiveNumPlus(subTree.getRight());
    }

}

//***************************************************************************
// ExpNode holds a "node" for an ExpTree.
class ExpNode
{
    //data
    private String data;
    private ExpNode left;
    private ExpNode right;

    //constructor
    public ExpNode(String el)
    {
        data = el;
        left = right = null;
    }

    //methods
    //toString() - this is how an ExpNode represents itself as a String
    public String toString()
    {
        return data;
    }

    //getLeft - returns the reference to the left subTree
    public ExpNode getLeft()
    {
        return left;
    }

    //getRight - returns the reference to the right subTree
    public ExpNode getRight()
    {
        return right;
    }

    //getData - returns the data (could be an operator or a number, so returns as a String)
    public String getData()
    {
        return data;
    }

    //setLeft - sets the left subTree to whatever is passed in
    public void setLeft(ExpNode newNode)
    {
        left = newNode;
    }

    //setRight - sets the right subTree to whatever is passed in
    public void setRight(ExpNode newNode)
    {
        right = newNode;
    }

}

Réponse acceptée

L’approche orientée objet de votre problème consiste à définir un type dédié à chaque type de noeud. Afin de garder la longueur de cette réponse raisonnable et d'éviter de faire vos devoirs, je ne montrerai qu'un exemple minimal pour les expressions entières impliquant uniquement l'addition et la multiplication.

La première étape consiste à définir ce qu'un nœud d'expression doit fournir. Pour cela, nous définissons l'interface ExprNode . Si vous n'avez pas encore appris le polymorphisme dans votre classe (ce qui devrait me surprendre), vous voudrez probablement arrêter de lire maintenant et revenir après l'avoir appris.

Nous voulons évaluer les nœuds afin d'ajouter une méthode d' evaluate qui devrait renvoyer la valeur de la sous-expression enracinée sur ce nœud. Nous reporterons son implémentation aux classes de nœuds spécifiques, car celles-ci sauront mieux s’évaluer elles-mêmes.

Nous souhaitons également formater les expressions afin d'ajouter une autre méthode pour formater la sous-expression en notation infixe.

public interface ExprNode {
    int evaluate();
    String asInfixString();
}

Voyons maintenant quels nœuds nous avons besoin. Certes, toute expression contiendra des nombres au niveau des feuilles, nous allons donc commencer à définir une classe pour elles. L'implémentation de ValueNode est très simple, pour ne pas dire triviale.

public interface ExprNode {
    int evaluate();
    String asInfixString();
}

Ensuite, nous avons nos deux opérations binaires + et * . L'implémentation des classes respectives est encore très simple.

public interface ExprNode {
    int evaluate();
    String asInfixString();
}
public interface ExprNode {
    int evaluate();
    String asInfixString();
}

Grâce à cela, nous pouvons construire avec élégance des arbres d’expression, les imprimer et les évaluer. Voici un exemple pour l'expression 2 * (3 + 4) .

public interface ExprNode {
    int evaluate();
    String asInfixString();
}

Il imprimera (2) * ((3) + (4)) = 14 .

Donc, pour votre ExprTree , il vous ExprTree vérifier si la root != null et si c'est le cas, return root.evaluate() .

Et si on veut plus d'expressions?

Clairement, nous allons définir un autre sous-type de ExprNode . Par exemple, nous pouvons définir plus d’opérateurs binaires pour gérer la soustraction et la division, un autre noeud unaire pour le moins unaire, etc. Chacune de ces classes doit implémenter l'interface dictée par ExprNode afin que chaque sous-classe puisse être utilisée de la même manière, encapsulant la logique de la façon dont elle s'auto évalue.

Et si on veut plus d'opérations?

Par exemple, nous pourrions vouloir formater des expressions en notation postfixée. Pour pouvoir le faire, nous pourrions ajouter une autre méthode asPostfixString à ExprNode . Cependant, c'est un peu gênant car cela signifie que nous devrons éditer toutes les sous-classes que nous avons implémentées jusqu'à présent, en ajoutant la nouvelle opération.

C'est un problème plutôt fondamental. Si vous disposez d'une structure composite pour encapsuler les opérations dans les nœuds, il est élégant et simple d'ajouter de nouveaux types de nœuds, mais difficile d'ajouter des opérations en mode. Si vous utilisez une sélection de cas dans chaque opération (un peu comme dans votre code), il est plus simple d'ajouter de nouvelles opérations, mais le code des opérations devient compliqué et il est difficile d'ajouter plus de types de nœuds être modifié). Ce dilemme est connu comme la tyrannie de la décomposition modèle dominante . Le modèle de visiteur est une tentative pour en sortir.

Quoi qu'il en soit, si vous prenez une classe Java de base, je pense que ce que vous êtes censé apprendre, c'est l'implémentation d'un arbre polymorphe avec des opérations définies dans les nœuds, comme indiqué ci-dessus.




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