Expression Tree

 

What is an Expression Tree?

  • An expression tree is a binary tree used to represent arithmetic expressions.

  • In an expression tree:

    • Each internal node (non-leaf) contains an operator (+, -, *, /).

    • Each leaf node contains an operand (like a number or variable).

Example:

Expression:


(3 + 5) * (2 - 4)

Expression Tree:


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

How to create an Expression Tree from an Expression?

There are two common ways:

  • From postfix (easiest and standard)

  • From infix (needs more work like using a stack and precedence rules)

We usually use postfix expression to easily build the tree.

Steps to Create from Postfix:

  1. Read the postfix expression left to right.

  2. If operand → create a node and push onto stack.

  3. If operator →

    • Pop two nodes from stack.

    • Create a new node with the operator.

    • Set the two popped nodes as children (left and right).

    • Push the new node back onto the stack.

  4. After all symbols are processed, top of stack is the root of the expression tree.


Algorithm (from postfix)

Create an empty stack
For each symbol in postfix expression:
    if symbol is operand:
        create node, push it onto stack
    else if symbol is operator:
        pop two nodes
        create new node with operator
        set popped nodes as left and right children
        push new node onto stack
Root = top of stack

Simple C Program to Create and Traverse an Expression Tree
Note; The input must be an expression with single digits  Eg:23+45-*

#include<stdio.h>
#include<stdlib.h>
#include<ctype.h> // for isdigit()

// Tree node structure
struct Node {
    char data;
    struct Node *left, *right;
};

// Stack node structure
struct Stack {
    struct Node* data;
    struct Stack* next;
};

struct Stack* top = NULL;

// Function to create new tree node
struct Node* createNode(char value) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = value;
    newNode->left = newNode->right = NULL;
    return newNode;
}

// Stack operations
void push(struct Node* treeNode) {
    struct Stack* temp = (struct Stack*)malloc(sizeof(struct Stack));
    temp->data = treeNode;
    temp->next = top;
    top = temp;
}

struct Node* pop() {
    if (top == NULL) return NULL;
    struct Stack* temp = top;
    struct Node* res = top->data;
    top = top->next;
    free(temp);
    return res;
}

// Create Expression Tree from postfix expression
struct Node* createExpressionTree(char postfix[]) {
    int i = 0;
    char symbol;
    while ((symbol = postfix[i]) != '\0') {
        if (isdigit(symbol)) { // Operand
            struct Node* operandNode = createNode(symbol);
            push(operandNode);
        } else { // Operator
            struct Node* operatorNode = createNode(symbol);
            operatorNode->right = pop();
            operatorNode->left = pop();
            push(operatorNode);
        }
        i++;
    }
    return pop(); // Root node
}

// Inorder traversal (infix)
void inorder(struct Node* root) {
    if (root != NULL) {
        if(root->left && root->right) printf("(");
        inorder(root->left);
        printf("%c", root->data);
        inorder(root->right);
        if(root->left && root->right) printf(")");
    }
}

// Preorder traversal (prefix)
void preorder(struct Node* root) {
    if (root != NULL) {
        printf("%c", root->data);
        preorder(root->left);
        preorder(root->right);
    }
}

// Postorder traversal (postfix)
void postorder(struct Node* root) {
    if (root != NULL) {
        postorder(root->left);
        postorder(root->right);
        printf("%c", root->data);
    }
}

int main() {
    struct Node* root = NULL;
    int choice;
    char postfix[100];

    do {
        printf("\nMenu\n----\n");
        printf("1. Create Expression Tree\n");
        printf("2. Inorder Traversal (Infix Expression)\n");
        printf("3. Preorder Traversal (Prefix Expression)\n");
        printf("4. Postorder Traversal (Postfix Expression)\n");
        printf("5. Exit\n");
        printf("Enter your choice: ");
        scanf("%d", &choice);
        getchar(); // clear input buffer

        switch(choice) {
            case 1:
                printf("Enter postfix expression: ");
                scanf("%s", postfix);
                root = createExpressionTree(postfix);
                printf("Expression Tree Created Successfully.\n");
                break;
            case 2:
                if(root == NULL) printf("Create the tree first!\n");
                else {
                    printf("Inorder Traversal (Infix): ");
                    inorder(root);
                    printf("\n");
                }
                break;
            case 3:
                if(root == NULL) printf("Create the tree first!\n");
                else {
                    printf("Preorder Traversal (Prefix): ");
                    preorder(root);
                    printf("\n");
                }
                break;
            case 4:
                if(root == NULL) printf("Create the tree first!\n");
                else {
                    printf("Postorder Traversal (Postfix): ");
                    postorder(root);
                    printf("\n");
                }
                break;
            case 5:
                printf("Exiting program.\n");
                exit(0);
            default:
                printf("Invalid choice! Try again.\n");
        }

    } while(1);

    return 0;
}

Comments

Post a Comment

Popular posts from this blog

Data Structures Lab PCCSL307 KTU 2024 Scheme - Dr Binu V P

About Me    Learn the theory Data Structures and Algorithms PCCST303 Scheme and Assessments Experiment List and References Lab Assignments Format of the Lab Record Lab Cycle ( Mandatory Programs) 1.Polynomial Addition Using Arrays 2.Sparse Matrix- Transpose and Addition 3.Stack    Implement  stack using array    Infix to Postfix Conversion and Evaluation 4.Queue    Queue using array     Circular Queue using array     Double ended Queue using array 5.Singly Linked List      Singly  Linked list and operations     Stack using linked list     Queue using linked list    Polynomial addition using linked list    Polynomial multiplication using linked list     Priority Queue-Post office customers simulation     Circular Queue using Linked List 6. Doubly Linked List      Doubly Linked List- Operations     Double Ended Queue ...
Read more

Sparse Matrix - Transpose and Addition

Image
  A sparse matrix is a special type of matrix in which most of the elements are zero or have some default value. In contrast, a dense matrix is one in which most of the elements are non-zero. Sparse matrices are used in various fields, including computer science, numerical analysis, and scientific computing, when dealing with large datasets or systems where efficiency and memory usage are crucial.   As a rule of thumb, if 2/3 of the total elements in a matrix are zeros, it can be called a sparse matrix . Using a sparse matrix representation — where only the non-zero values are stored — the space used for representing data and the time for scanning the matrix are reduced significantly. In many real-world problems — like graphs, networks, or scientific simulations — the majority of elements in the matrix are zero . Such a matrix is called a Sparse Matrix . Formally: A matrix in which the number of zero elements is significantly greater than the number of non-zero elements. ...
Read more

Polynomial Addition using Arrays

Polynomial  Addition We can represent a polynomial as a collection of terms and every term is having a coefficient and exponent. So, we can represent this as a list of terms having coefficients and exponents.  Each term of a polynomial (like 3 x 2 3x^2 , 5 x 1 5x^1 , − 7 x 0 -7x^0 ) can be stored in a structure having two parts: coefficient (like 3, 5, -7) exponent (like 2, 1, 0) An array of such structures represents the whole polynomial. Structure Definition (Example in C) struct Term { int coeff; // Coefficient of the term int expo; // Exponent of the term }; And then you can declare: struct Term poly1 [10], poly2 [10], polyResult [20]; to represent polynomials. Algorithm to Add Two Polynomials Assumption : Both polynomials are sorted in decreasing order of exponents . Steps : Initialize three pointers (indexes): i = 0 for first polynomial (poly1), j = 0 for second polynomial (poly2), k = 0 for result polynomial (polyR...
Read more