解析一個字符串構造一個樹在Java中

Question

我不知道要採取什麼方向 - 我試圖解析表達式「（4 + 3）」，並從它建立一棵樹。但是，在我的EvalExp方法中，我不知道該從這裏做什麼。表達式的排序應該是值/運算符/值/運算符，所以我已經放入了兩個堆棧來標識。任何想法接下來我應該做什麼？

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()); 
}