Converting a Postfix Notation to an ExpressionTree

问题:

As it is said in the title I am trying to create a code which converts a postfix notation to an expression tree. Here you can check the constructor :

  public byte type;         // 0    : operator, 1: operand (a number)
  public char operator;     // One of '+', '-', '*', '/'
  public int operand;       // A number
ExpressionTreeNode(byte type){this.type = type; left=right=null;}

and Here is my code :

    public static ExpressionTreeNode Postfix2ExpressionTree(String postfixExpr){

            Stack s = new Stack<Object>();
            ExpressionTreeNode root = new ExpressionTreeNode((byte) 0);
            root.operator = postfixExpr.charAt(postfixExpr.length()-1);
            String number = "";

            for(int i = 0;i<postfixExpr.length()-1;i++){

                if(Character.isDigit(postfixExpr.charAt(i)) == true){

                     number = number + postfixExpr.charAt(i);
                     if(Character.isDigit(postfixExpr.charAt(i+1)) == false){
                         ExpressionTreeNode node = new ExpressionTreeNode((byte) 1);
                         node.operand = Integer.valueOf(number);
                         node.right = null;
                         node.left = null;

                         s.push(node);
                         number = "";
                            }    
                         }
                if(i == postfixExpr.length()-2){

                    root.right = (ExpressionTreeNode) s.pop();
                    root.left =(ExpressionTreeNode) s.pop();
                    s.push(root);
                    break;
                }
                else {
                    if(postfixExpr.charAt(i) == '+' || postfixExpr.charAt(i) == '*' || postfixExpr.charAt(i) == '-' || postfixExpr.charAt(i) == '/' ){


                    ExpressionTreeNode node = new ExpressionTreeNode((byte)0);
                    node.operand = postfixExpr.charAt(i);
                    node.right = (ExpressionTreeNode) s.pop();
                    node.left = (ExpressionTreeNode) s.pop();

                    s.push(node);

                    }

                }

            }

        return (ExpressionTreeNode) s.pop();
      }

I check every character one by one with charAt() method. Simply 1-push every operand into the stack 2-when operator is encountered pop two operand from the stack and assign them to right and left of operator then push the new node to the stack. 3- and finally I push the root to the stack then return it.

No error occurs when I try to run but also it is not working in the right way too. I checked the code many times but I couldn't solve it.If anyone sees the mistake and help me , that would be great.

回答1:

A postfix expression is parsed from left to right - don't look at postfixExpr.length()-1 before you are there.

Do not create and handle a root node in any special way. It will be top of the stack after the parse.

Here's an error:

node.operand = postfixExpr.charAt(i);

This must be stored in node.operator.

This is how I would implement it:

public interface Entry {
  int evaluate();
}
public class Value implements Entry {
  private int value;
  public Value( int value ){
    this.value = value;
  }
  public int  evaluate(){
    return value;
  }
}
public class Operation implements Entry {
  private char operator;
  private Entry left;
  private Entry right;
  public Operation( char operator, Entry left, Entry right ){
    this.operator = operator;
    this.left = left;
    this.right = right;
  }
  public int  evaluate(){
    int l = left.evaluate();
    int r = right.evaluate();
    switch(operator){
    case '+':
      return l + r;
    case '-':
      return l - r;
    case '*':
      return l * r;
    case '/':
      return l / r;
    }
    throw new IllegalStateException( "operator " + operator );
  }
}
public class Parser {
  private Stack<Entry> stack = new Stack<>();
  Pattern pat = Pattern.compile( "[-+*/]" );
  Scanner scanner;
  public void parse( String ex ){
    scanner = new Scanner( ex );
    while( scanner.hasNext() ){
      while( scanner.hasNextInt() ){
        stack.push( new Value( scanner.nextInt() ) );
      }
      while( scanner.hasNext( pat ) ){
        char op = scanner.next( pat ).charAt( 0 );
        Entry right = stack.pop();
        Entry left = stack.pop();
        stack.push( new Operation( op, left, right ) );
      }
    }
  }
  public Entry get(){
    return stack.pop();
  }
}

There is absolutely no error handling, so think about adding that.