# Inserting infix into a binary tree

Show 80 post(s) from this thread on one page
Page 1 of 2 12 Last
• 01-19-2003
Nakeerb
Inserting infix into a binary tree
For example:

(3 + 4) - (1 * 2) + 1

is

Code:

+
/          \
-            1
/          \
+            *
/    \      /    \
3      4    1      2

precondition:
The infix expression is being entered one character at a time.

The expression is FULLY parenthesized, like (6-4) or (3+(4-2)) or ((2-1)*6) or (((2+1)-4)^2)

postconditions:

Each node will consist of an operator (root) with two children or a digit with no children (BTW no digits ever have children obviously. Children of operators are either digits or a new subtree).

You can use pre-order and post-order traversal to output the tree in prefix and postfix, and use inorder traversal to evaluate the infix expression

____________

My question is, how do I store the infix expression into a binary tree? I know how to do everything else
• 01-19-2003
Nakeerb
I tried it again and I still can't figure it out. How the heck am I supposed to do this?
• 01-19-2003
Nakeerb
Hmmm, does this also work for nested parenthetical statements? You'd have to detect the first ), yes, but then the items before it and after the last (?
• 01-19-2003
Nakeerb
The problem states there will always be parenthesis. Any operand-operator-operand statement has ( and ) around it

Also the problem speaks of writing constructors for two types of nodes, one that will accept an operator and two digits, or a digit node containing a digit and has both left and right pointers NULL. You assume the input will always be correct.

I just don't understand how that would work... a constructor for nodes? Na, how would this help
• 01-19-2003
Nakeerb
• 01-19-2003
Nakeerb
Dangit, Salem what do you mean ;-;
• 01-19-2003
Nakeerb
No one can help? ;-; I am so dead
• 01-19-2003
Nakeerb
Helllp!
• 01-19-2003
Cela
If you keep bumping your thread someone's gonna delete it. Salem told you exactly how to solve your problem, read his post until it sinks in.
• 01-20-2003
Nick
You can search for recursive descent. You can pretty much ignore
any of the technical sites. Left factoring and all of the
complicated stuft isn't needed. Try to understand a recursive
description of the language | stands for or and -> stands
for "is defined as".

expr-> term | term + expr | term - expr
term-> factor * term | factor / term | factor
factor-> (expr) | num
num-> [0..N]

The actual code will use a function called match(t) that
will check the next token against t. If t equals the
next token then it will read the next token and return true
else it will just return false.

Here is example of how expr could be coded
Code:

int expr()
{
int val = 0;

val = term();

switch(next_token.type) {
case PLUS:
match(PLUS);
val += expr();
break;
case MINUS:
match(MINUS);
val -= expr();
break;
default:
break;
}

return val;
}

A function such as factor could be coded
Code:

int factor()
{
int val = 0;

switch(next_token.type) {
case NUMBER:
val = next_token.val;
break;
case LEFT_PARAN:
match(LEFT_PARAN);
val = expr();
match(RIGHT_PARAN);
break;
default:
break;
}

return val;
}

This preserves the structure of the expression but
it evaluates it. Instead of doing that you could pass
in the root of each subtree and have each function
add a node to the tree.
• 01-20-2003
Nakeerb
Ahh I see how it works. I need to modify it though, this does not work for expressions like "(((3+4)-3)-2)" because it only checks for numbers before and after, not when you have two parentheses next to each other
• 01-20-2003
Nakeerb
This also does not build the binary tree in terms of a node holding an operator as data, with two children being separate nodes with integers as the data
• 01-20-2003
Nakeerb
This is difficult ;-; must be careful
• 01-20-2003
Nick
If you write a recursive descent parser that evaluates
an expression then you can easily change it to generate
an infix tree.

It would handle all parens and expressions in the language
automatically. For example

(((3+4)-3)-2)
This would
be parsed like this
expr
term
factor
(expr)
(term - expr)
(factor - term)
((expr) - factor)
((term - expr) - num)
((factor - term) - num)
(((expr) - factor) - num)
(((term + expr) - num) - num)
(((factor + term) - num) - num)
(((num + factor) - num) - num)
(((num + num) - num) - num)
• 01-20-2003
Nakeerb
I do not understand what that all meant, URG I am dead
Show 80 post(s) from this thread on one page
Page 1 of 2 12 Last