# Thread: Inserting infix into a binary tree

1. ## 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

2. I tried it again and I still can't figure it out. How the heck am I supposed to do this?

3. 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 (?

4. 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

5. And what about nested parenthesis?

6. Dangit, Salem what do you mean ;-;

7. No one can help? ;-; I am so dead

8. Helllp!

9. 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.

10. 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.

11. 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

12. 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

13. This is difficult ;-; must be careful

14. 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)

15. I do not understand what that all meant, URG I am dead