Parsing an Arithmetic Expression and Building a Tree from It in Java

Parsing an arithmetic expression and building a tree from it in Java

The "Five minute introduction to ANTLR" includes an arithmetic grammar example. It's worth checking out, especially since antlr is open source (BSD license).

Create a binary tree from an algebraic expression

Tree construction for prefix expressions

def insert

     Insert each token in the expression from left to right:

     (0) If the tree is empty, the first token in the expression (must
         be an operator) becomes the root

     (1) Else if the last inserted token is an
         operator, then insert the token as the left child of the last inserted
         node.

     (2) Else if the last inserted token is an operand, backtrack up the
         tree starting from the last inserted node and find the first node with a NULL
         right child, insert the token there. **Note**: don't insert into the last inserted 
         node. 
end def

Let's do an example: + 2 + 1 1

Apply (0).

  +

Apply (1).

  +
 /
2 

Apply (2).

  +
 / \
2   +

Apply (1).

  +
 / \
2   +
   /
  1 

Finally, apply (2).

  +
 / \
2   +
   / \
  1   1

This algorithm has been tested against - * / 15 - 7 + 1 1 3 + 2 + 1 1

So the Tree.insert implementation is those three rules.

insert(rootNode, token)
  //create new node with token
  if (isLastTokenOperator)//case 1
      //insert into last inserted's left child
  else {                  //case 2
      //backtrack: get node with NULL right child
      //insert
  }
  //maintain state
  lastInsertedNode = ?, isLastTokenOperator = ?

Evaluating the tree is a little funny, because you have to start from the bottom-right of the tree. Perform a reverse post-order traversal. Visit the right child first.

evalPostorder(node)
  if (node == null) then return 0
  int rightVal = evalPostorder(node.right)
  int leftVal = evalPostorder(node.left)
  if(isOperator(node.value)) 
       return rightVal <operator> leftVal    
  else
       return node.value

Given the simplicity of constructing a tree from a prefix expression, I'd suggest using the standard stack algorithm to convert from infix to prefix. In practice you'd use a stack algorithm to evaluate an infix expression.

Parsing of math expression gives wrong tree

Yes I would parse the equation, it just looks like you miss a key part of the order of operations/parsing. You need to include an additional check for double negatives.

The key factor here is that: In a situation with two identical operators then the left most operation is always carried out first.

First lets narrow down the issue.

This 1-5*(-2)+3 is equal to 1--10+3.

Now for our purposes lets assign a positive to the first operator because it helps illustrate a point:

1--10+3 is the same as +1--10+3

Now if we where to run +1--10+3 through a correct parser we would know that this -- is equal to + but only when used in the following situation:

+X--Y = X+Y

So now our parser has turned the original expression of 1--10+3 into 1+10+3 and we know that is equal to 14.

So all up: Yes you need a parser, but pay special attention to how +X--Y and X+Y work.

Also take a look at this answer: https://stackoverflow.com/a/26227947/1270000

Algorithm to build a tree that represent a prefix expression

Actually, you parse the String from left to right:

public class Parser {
    private final String prefix;
    int pos = 0;

    public Parser(String prefix) {
        this.prefix = prefix;
    }

    public Noeud parse() {
        char c = prefix.charAt(pos);
        pos++;
        String token = Character.toString(c);
        if (Character.isDigit(c)) {
            return new Noeud(token);
        }
        return new Noeud(token, parse(), parse());
    }
}

The basic algorithm to read a Node is:

• read a character (the next token).
• if that character is a digit, then return a new leaf node.
• otherwise read two more nodes, and construct a new node with those as left and right child.

Your constructTree function would be this:

public static Noeud constructTree(String prefix) {
    return new Parser(prefix).parse();
}

Techniques needed to write an arithmetic expression parser

Without knowledge of compilation techniques it would be ugly. But there is no need to learn a ton of compilation for an introductory example like this.

Look at something like http://www.codeproject.com/Articles/345888/How-to-write-a-simple-interpreter-in-JavaScript and see if it makes sense to you.

---

Related Topics