-1

只担心在测试类中完成第一个测试，因为树的根是运算符“+”，它的操作数/“子”是 3 和 4。由于根是“+”，我想弹出左边child 和 right child 并将节点推送到堆栈。试图理解为什么我不能使用 Stack 类中的 pop() 方法。

节点类

public class Node < E > {
 E data;
 Node < E > left;
 Node < E > right;

 public Node(E data) {
  this.data = data;
 }

 public Node(E data, Node < E > left, Node < E > right) {
  this.data = data;
  this.left = left;
  this.right = right;
 }

 public String toString() {
  return data.toString();
 }

}

ExpressionTree 类导入 java.util.Stack;

public class ExpressionTree {
 Node < String > root;

 public void buildTree(String expression) {
  Stack < Node < String >> s = new Stack < Node < String >> ();

  String expArray[] = expression.split(" ");
  for (String st: expArray) {
   switch (st) {
    case "+":
    case "-":
    case "*":
    case "/":
     Node < String > right = s.pop();
     s.push((new Node < String > (st, s.pop(), right)));
     break;
    default:
     s.push(new Node < String > (st));


   }
  }

  root = s.pop();
 }

 public void printExpression() {
  printExpression(root);
  System.out.println();
 }

 private void printExpression(Node < String > n) {
  if (n != null) {
   printExpression(n.left);
   System.out.print(n);
   printExpression(n.right);
  }
 }

 public int evaluateExpression() {

  return evaluateExpression(root);
 }

 public int evaluateExpression(Node < String > n) {
  Stack < Node < String >> s = new Stack < Node < String >> ();
  n = root;
  if (n == null) {
   return 0;
  } else {
   if (n.data.equals("+")) {
    s.pop(n.left);
    s.pop(n.right);
    s.push(n);
    evaluateExpression(n);
   }
  }
  return 0;
 }

}

测试班

public class ExpressionTreeTest {

 public static void main(String[] args) {
  ExpressionTree et = new ExpressionTree();
  et.buildTree("3 4 +"); //infix: 3 + 4
  et.printExpression();
  System.out.println(et.evaluateExpression());

  /*et.buildTree("3 4 2 * 1 5 - / +"); //infix: 3+4*2/(1-5)
    et.printExpression();
    System.out.println(et.evaluateExpression());

    et.buildTree("3 4 5 * 2 / +"); //infix: 3+4*5/2
    et.printExpression();
    System.out.println(et.evaluateExpression());

    et.buildTree("12 8 + 6 5 - * 3 2 - 2 3 + * /"); //infix: (12+8)*(6-
    5)/((3-2)*(2+3))
    et.printExpression();
    System.out.println(et.evaluateExpression());*/


 }

}
4

1 回答 1

1

从代码开始

s.pop(n.left);
s.pop(n.right);

正如Stack API所示，pop 函数不带任何参数。

它“[r] 删除此堆栈顶部的对象并将该对象作为此函数的值返回。”

如果要删除特定对象而不是堆栈顶部的任何对象，则应该使用另一个类。

于 2017-10-01T01:03:34.330 回答