Thread: Inserting infix into a binary tree

This shows the general technique of recursive descent.
It evaluates expressions like
4 + (((3 + 5) * 6 + 8 + 4));
val = 64

Code:

#include <iostream>
using std::cout;
using std::cin;
using std::endl;

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

enum { END_FILE, END_STATEMENT, PLUS, MINUS,
       MULTIPLY, DIVIDE, LEFT_PARAN, RIGHT_PARAN, NUMBER};

struct Token {
    int type;
    int val;
};

void read_next_token();
bool match(int token_type);
int start();
int expr();
int term();
int factor();

Token next_token;


int main(void)
{
    int val;
    
    read_next_token();
    val = start();
    cout << "val = " <<  val << endl;
    return 0;
}

        

void read_next_token()
{
    int c;

    next_token.type = END_FILE;
    next_token.val  = 0;
    
    while((c = cin.get()) && isspace(c))
        continue;

    if (isdigit(c)) {
        int n = 0;
        
        cin.putback(c);
        cin >> n;
        next_token.type = NUMBER;
        next_token.val  = n;
        return;
    }
    
    switch(c) {
    case ';':
        next_token.type = END_STATEMENT;
        break;
    case '+':
        next_token.type = PLUS;
        break;
    case '-':
        next_token.type = MINUS;
        break;
    case '*':
        next_token.type = MULTIPLY;
        break;
    case '/':
        next_token.type = DIVIDE;
        break;
    case '(':
        next_token.type = LEFT_PARAN;
        break;
    case ')':
        next_token.type = RIGHT_PARAN;
        break;
    }
}

bool match(int token_type)
{
    bool ret;
    
    if (next_token.type == token_type) {
        read_next_token();
        ret = true;
    } else {
        ret = false;
    }

    return ret;
}

int start()
{
    int val = expr();
    return val;
}

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;
}

int term()
{
    int val;

    val = factor();

    switch(next_token.type) {
    case MULTIPLY:
        match(MULTIPLY);
        val *= term();
        break;
    case DIVIDE:
        match(DIVIDE);
        val /= term();
        break;
    default:
        break;
    }

    return val;
}
    

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

Urg I just give up. I am never going to get this done. the struct is a simple

struct node{
char data;
node *left, *right;
}

that's it.

I don't know how I'd insert into a tree using recursive descent either. No idea whatsoever

It's easy to insert using recursive descent.

Code:

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

What type of tree would generate if next_token.type is
a NUMBER like 4? Just a single node tree with
'4'
What about a left param? Just a single node tree
'('

Now how would you code expr

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;
}

You would first generate a tree from term. Call that
tree left. Set right = 0.
If next_token.type == PLUS you generate
a tree from expr and assign that to right. Similarly for
next_token.type == MINUS. Then to generate the tree
for expr you would right something like this

Code:

if (right != 0) {
      root = new_node(left, right);
} else {
      root = left;
}

It's really easy for all of the functions. Just add a little error
checking in match and your finished.

Is there any place I can talk to you besides this board?

Code:

void traverseInOrder(node *root){
	
	if (!root)		//test first to see if done
		return;
		
	traverseInOrder(root->left);
	cout << root->data << " ";	
	traverseInOrder(root->right);	   
}


void traversePreOrder(node *root){
	
	if (!root)		//test first to see if done
		return;
		
	cout << root -> data << " ";		
	traversePreOrder(root -> left);
	traversePreOrder(root -> right);	
}


void traversePostOrder(node *root){
	
	if (!root)		//test first to see if done
		return;
		
	traversePostOrder(root -> left);
	traversePostOrder(root -> right);
	cout << root -> data << " ";	
}

I can get those three of your list