Evaluación recursiva () en la clase de árbol de expresión

evaluate expression-trees java methods recursion

Pregunta

Soy nuevo en Java y estoy tratando de agregar un método de evaluación a mi clase. Me dan la clase ExpTree y su programa de prueba. Escribí mi código como aprendí en la clase, pero no sé por qué no funciona.

Un método eval (), que devuelve la evaluación aritmética del ExpTree. Esto debe hacerse recursivamente, por lo que necesitará 2 métodos para hacerlo. En el caso en que resultaría en división o mod por 0, debería lanzar una nueva ArithmeticException con una cadena descriptiva. Si el árbol está vacío, eval () también debe lanzar una nueva ArithmeticException con una cadena descriptiva.

Aquí está mi código:

// 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;
    }

}

Respuesta aceptada

El enfoque orientado a objetos para su problema es definir un tipo dedicado para cada tipo de nodo. Para mantener la longitud de esta respuesta razonable y para evitar hacer tu tarea, solo mostraré un ejemplo mínimo para expresiones enteras que solo involucran sumas y multiplicaciones.

El primer paso es definir qué debe proporcionar un nodo de expresión. Para ello, definimos la interfaz ExprNode . Si aún no aprendió sobre el polimorfismo en su clase (lo que debería sorprenderme) probablemente querrá dejar de leer ahora y volver después de haberlo aprendido.

Queremos evaluar los nodos, así que agregaremos un método de evaluate que debería devolver el valor de la sub-expresión enraizada en ese nodo. Aplazaremos su implementación a las clases de nodo específicas, ya que éstas sabrán mejor cómo evaluarse a sí mismas.

También queremos dar formato a las expresiones, así que agregaremos otro método para formatear la subexpresión en notación de infijo.

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

Ahora, veamos que nodos necesitamos. Ciertamente, cualquier expresión contendrá números en las hojas, así que mejor comenzaremos a definir una clase para ellos. La implementación de ValueNode es realmente simple, por no decir trivial.

public final class ValueNode implements ExprNode {

    private final int value;

    public ValueNode(final int value) {
        this.value = value;
    }

    @Override
    public int evaluate() {
        return this.value;
    }

    @Override
    public String asInfixString() {
        return String.valueOf(this.value);
    }
}

A continuación, tenemos nuestras dos operaciones binarias + y * . La implementación de las respectivas clases es de nuevo muy simple.

public final class PlusNode implements ExprNode {

    private final ExprNode lhs;
    private final ExprNode rhs;

    public PlusNode(final ExprNode lhs, final ExprNode rhs) {
        this.lhs = lhs;
        this.rhs = rhs;
    }

    @Override
    public int evaluate() {
        return this.lhs.evaluate() + this.rhs.evaluate();
    }

    @Override
    public String asInfixString() {
        return String.format("(%s) + (%s)",
                             this.lhs.asInfixString(),
                             this.rhs.asInfixString());
    }
}
public final class TimesNode implements ExprNode {

    private final ExprNode lhs;
    private final ExprNode rhs;

    public TimesNode(final ExprNode lhs, final ExprNode rhs) {
        this.lhs = lhs;
        this.rhs = rhs;
    }

    @Override
    public int evaluate() {
        return this.lhs.evaluate() * this.rhs.evaluate();
    }

    @Override
    public String asInfixString() {
        return String.format("(%s) * (%s)",
                             this.lhs.asInfixString(),
                             this.rhs.asInfixString());
    }
}

Equipados con eso, podemos construir con elegancia árboles de expresión, imprimirlos y evaluarlos. Aquí hay un ejemplo para la expresión 2 * (3 + 4) .

ExprNode expr = new TimesNode(
        new ValueNode(2),
        new PlusNode(new ValueNode(3), new ValueNode(4)));
System.out.println(expr.asInfixString() + " = " + expr.evaluate());

Imprimirá (2) * ((3) + (4)) = 14 .

Entonces, para su ExprTree , simplemente verificará si la root != null return root.evaluate() y si es así, return root.evaluate() .

¿Y si queremos más expresiones?

Claramente, definiremos otro subtipo de ExprNode . Por ejemplo, podemos definir más operadores binarios para manejar la resta y la división, otro nodo unario para el menos unario y así sucesivamente. Cada una de estas clases debe implementar la interfaz dictada por ExprNode para que cualquier subclase se pueda utilizar de la misma manera, encapsulando la lógica de cómo se evalúa a sí misma.

¿Y si queremos más operaciones?

Por ejemplo, podríamos querer formatear expresiones en notación postfix. Para poder hacer esto, podríamos agregar otro método como asPostfixString a ExprNode . Sin embargo, esto es un poco incómodo ya que significa que tendremos que ir a editar todas las subclases que hemos implementado hasta ahora, agregando la nueva operación.

Este es un problema bastante fundamental. Si diseña una estructura compuesta para encapsular las operaciones en los nodos, entonces es elegante de usar y simple de agregar nuevos tipos de nodos, pero es difícil agregar operaciones de modo. Si está utilizando una selección de casos en cada operación (algo así como en su código), es más sencillo agregar nuevas operaciones, pero el código para las operaciones se complica y es difícil agregar más tipos de nodos (el código para todas las operaciones debe ser alterado). Este dilema es conocido como la tiranía de la descomposición del modelo dominante . El patrón de visitante es un intento de salir de él.

De todos modos, si está tomando una clase Java básica, creo que lo que se espera que aprenda es implementar un árbol polimórfico con las operaciones definidas en los nodos como se muestra arriba.



Licencia bajo: CC-BY-SA with attribution
No afiliado con Stack Overflow
Licencia bajo: CC-BY-SA with attribution
No afiliado con Stack Overflow