Building an Expression Tree

chris2810 · 07-12-2011, 05:15 PM

Hi,

i have a problem.
I tried a lot of things, but i can´t figure it out.

Maybe someone can help.

I want to build an expression tree from a math expression in objective-c.

I have pseudo code, but i can´t do it in Objective-C.

Here is the pseudo code.

PopConnectPush
{

pop the top node off the operator stack and call it N;
pop the top node off the tree stack and make it N's right child;
pop the top node off the tree stack and make it N's left child;
push N back into the tree stack;

}

Convert Expression to Tree

initialize operator and tree stacks;

while (there are tokens remaining in the expression)
{
T = next token from expression;
if (T == '(')
{
create a node and store T in it;
push the node onto the operator stack;
}
else if (T is a variable or numeric literal)
{
create a node and store T in it;
push the node onto the tree stack;
}
else if (T is '+', '-', '+', or '/')
{
create a node and store T in it;
if ((operator stack is empty) or
(the value at the top of the operator stack is '(') or
(priority(operator at top of stack) < priority(T)))
{
push the node onto the operator stack;
}
else // clear operator stack and push new one onto it
{
do
{
PopConnectPush;
}
while ((the operator stack is not empty) and
(the top of the operator stack is not '(') and
(priority(T) < priority(operator at top of stack)));

create a node and store T in it;
push the node onto operator stack;
}
else if (T is ')') // clear operator stack back to the '('
{
while (top of operator stack is not '(')
{
PopConnectPush;
}
}
else
{
report error!
}
}

// no more tokens left in expression
while (operator stack is not empty)
{
PopConnectPush;
}

// pointer to root of final tree is on top of the tree stack
}