Expression binary tree

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.


Here is the code that I made so far:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
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.
Here is the new code that I made:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
template<class T>
void Tree<T>::Expr(Node<T> *&node, char expr[], int &i)
	{
		i++;
		if(i >= strlen(expr)) return;
		char x = expr[i];
		node = new Node<T>;
		node->Left = NULL;
		node->Right = NULL;
		if(x == '(')
			{
				Expr(node->Left, expr, i);
				i++;
				x = expr[i];
			}
		if(x >= '0' && x <= '9')
			{
				node->data = x;
				return;
			}
		if(x == '+' || x == '-' || x == '*' || x == '/')
			{
				node->data = x;
				Expr(node->Right, expr, i);
			}
		if(x == ')') return;
	}


But it works only for expressions like: (5+2) :/
Topic archived. No new replies allowed.