Hello. I want to add mathematical expression in a binary tree but I have some problems with the algorithm. I found this one:
If the current token is a '(', add a new node as the left child of the current node, and descend to the left child.
If the current token is in the list ['+','-','/','*'], set the root value of the current node to the operator represented by the current token. Add a new node as the right child of the current node and descend to the right child.
If the current token is a number, set the root value of the current node to the number and return to the parent.
If the current token is a ')', go to the parent of the current node.
template<class T>
void Tree<T>::Expr(Node<T> *node, char expr[], int &i)
{
i++;
T x = expr[i];
if(x == '(')
{
node = node->Left;
node = new Node<T>;
node->Left = NULL;
node->Right = NULL;
Expr(node, expr, i);
}
if(x == '+' || x == '-' || x == '*' || x == '/')
{
node->data = x;
node = node->Right;
node = new Node<T>;
node->Left = NULL;
node->Right = NULL;
Expr(node, expr, i);
}
if(x >= '0' && x <= '9')
{
node->data = x;
return;
}
if(x == ')') return;
}
I know that it is a big mess and it doesn't follow the algorithm but this is the problem.
For example if the token is '(' I go to the left child of the current node. Then lets say that the next token in the expression is a number. I add this number to the current node and I must go back. But how can I go back to the parent? I will go back to line 13 and the program will end. What should be the structure that I must use?
I will be very thankful if someone can explain me the structureof the algorithm or give me a good source to study from.