Converting an infix expression (with parentheses) into a binary tree

Question

As part of a Java assignment, I have to take an input arithmetic expression and store it in a binary tree.

I have done everything necessary for the assignment except for the part where I read in the string of the expression and store it in the binary tree.

I have created a class called BinaryTree. Its only field is a treenode called root. This treenode is defined as an innerclass in BinaryTree. It has 3 fields, a generic data field, and two children (left and right) that are type BinaryTree.

I'm having a very difficult time defining an algorithm for reading in an expression such as

(5*(2+3)^3)/2

and storing it in a tree like this

             /
        ^          2
    *       3
  5   +
     2  3

Can anyone help with the algorithm?

Solution 1

Take a look at the shunting-yard algorithm. From Wikipedia:

In computer science, the shunting-yard algorithm is a method for parsing mathematical expressions specified in infix notation. It can be used to produce output in Reverse Polish notation (RPN) or as an abstract syntax tree (AST). The algorithm was invented by Edsger Dijkstra and named the "shunting yard" algorithm because its operation resembles that of a railroad shunting yard. Dijkstra first described the Shunting Yard Algorithm in Mathematisch Centrum report MR 34/61.

Solution 2

Here is some C++ code to create a binary expression tree that uses two stacks, one for the operators and another for the operands. Eventually, the operand stack contains one element, the complete binary expression tree.