再帰で算術式ツリーを単純化するには？

Question

どのように式ツリーを単純化するために再帰を使用しますか？たとえば：

私はいくつかの異なるものを試してみたが、私はそれを簡素化することができる午前方法でツリーを再帰する方法を見つけ出すことはできません。ありがとう。

public static LinkedBinaryTree<String> simplify(LinkedBinaryTree<String> tree) throws IllegalArgumentException { 
    // TODO: Implement this method 
    if (!isArithmeticExpression(tree) || tree == null) { 
     throw new IllegalArgumentException("Invalid arithmetic expression or Tree is null"); 
    } 

    return simplify(tree.root(), tree); 
} 

public static LinkedBinaryTree<String> simplify(Position<String> p, LinkedBinaryTree<String> tree) { 
    //  if (tree.isExternal(p)) { 
    //   return tree; 
    //  } 
    if (isAlphaNumeric(p.getElement())) { 

    } 

    if (p.getElement().equals("+") || p.getElement().equals("+") || p.getElement().equals("+")) { 

    } 

    String element = p.getElement(); 
    char charLeft = tree.left(p).getElement().charAt(0); 
    char charRight = tree.right(p).getElement().charAt(0); 
    String stringLeft = tree.left(p).getElement(); 
    String stringRight = tree.right(p).getElement(); 

    //  if (stringLeft.equals("+") || stringLeft.equals("-") || stringLeft.equals("*")) { 
    //   simplify(tree.left(p), tree); 
    //  } 

    //  if (!(Character.isLetter(charLeft) || Character.isDigit(charLeft))) { 
    //   
    //  } 

    return null; 

} 

Answer 1

ここで正しい方向にあなたを入れてくれる疑似コードがあります。

public int calculate() { 
    return calculateNode(rootNode) 
} 

private int calculateNode(Node node) { 
    if (node.isOperator()){ 
     int operandLeft = calculateNode(node.leftChild(); 
     int operandRight = calculateNode(node.leftChild(); 
     return node.getOperator().operateOn(operandLeft, operandRight); 
    } else { 
     return node.getValue()  
    } 
} 

機能calculate()は再帰のセット全体ツリー上の機能であることを意味します。

そして、再帰関数calculateNode(Node node)の重要なことは、when-a-node-is-a-numberの終了条件を見ることですが、再帰関数は、話をするために一度の呼び出し。

Answer 2

これはあくまでも一例ですが、あなたのニーズにさらにそれを適応させることができます。

int simplify(Node root) { 

    if(root == null) { 
     return 0; 
    } 
    int result; 

    switch (root.value) { 
     case "-": 
      result = simplify(root.left) - simplify(root.right); 
      break; 
     case "+": 
      result = simplify(root.left) + simplify(root.right); 
      break; 
     default: 
      return Integer.parseInt(root.value); 

    } 
    return result; 
} 

だから、アイデアがあなたのtreeを通過することです、あなたはここで2ケースを持つことができます。

• を

  ノードの値はオペランドです。この場合、指定されたオペランドを適用している間、右と左のノードに再帰的に行きます。

• ノードの値は数字です。値を返すだけです。