Convert infix expression (with parentheses) to binary tree

Question

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

I did everything necessary for the assignment, except for the part where I read the expressions in a string and saved it in a binary tree.

I created a class called BinaryTree. Its only field is a treenode called root. This treenode is defined as an inner class in BinaryTree. It has 3 fields, a common data field and two child (left and right) BinaryTree types.

It is very difficult for me to define an algorithm for reading in an expression, for example

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

and save it in a tree like this

/ ^ 2 * 3 5 + 2 3 

Can anyone help with the algorithm?

Answer 1

Take a look at the bypass algorithm. Material from Wikipedia:

In computer science, the shunting yard algorithm is a method for analyzing the mathematical expressions specified in infix notation. It can be used to create output in reverse fields (RPNs) or as an abstract syntax tree (AST). The algorithm was invented by Edsger Dijkstra and called the "shunting yard" algorithm because its operation resembles that of a railway shunting yard. Dijkstra first described the Shunting Court Algorithm in Mathematisch Centrum MR 34/61.

Answer 2

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