java - 解析字符串以在 Java 中构造树

Question

我不知道该采取什么方向 - 我正在尝试解析表达式“(4 + 3)”，并从中构建一个树。但是，在我的 EvalExp 方法中，我不知道从这里该做什么。表达式的顺序应该是值/运算符/值/运算符，所以我放入了 2 个堆栈，以识别其中一个。有什么想法我接下来应该做什么吗？

public class Tree {

    class ExprTreeNode {

        ExprTreeNode left, right;
        boolean isLeaf;
        int value;
        char op;

        public ExprTreeNode(int value) {
            this.value = value;
            this.op = op;
            this.left = null;
            this.right = null;
        }


    }

    private Stack opStk = new Stack();
    private Stack valStk = new Stack();
    private ExprTreeNode root;


    public Tree(String s) {

        root = (ExprTreeNode) EvalExp(s);
    }

    public Object EvalExp(String str) {

        Scanner s = null;

        try {
            s = new Scanner(str);

            while (s.hasNext()) {

                // push to val stk
                if (s.hasNextInt()) {   
                    valStk.push(s.next());
                } else {
                    opStk.push(s.next());
                }

            }

        } finally {

            if (s != null) {
                s.close();
            }
        }

        //return the root node
        return valStk.peek();
    }

Answer 1

为什么不使用递归下降解析器而不是显式堆栈？应该是

static ExprTreeNode parseExpr(Scanner s) {
  ExprTreeNode left = parsePrimary(s);
  if (s.hasNext("\\+")) {
    s.next("\\+");
    ExprTreeNode right = parseExpr(s);
    return new ExprTreeNode('+', left, right);
  }
  return left;
}

public static ExprTreeNode parsePrimary(Scanner s) {
  return new ExprTreeNode(parseNextInt());
}