C++ Program to Create Expression Tree from Postfix Expression

This is a C++ Program to create an expression tree and print the various traversals using postfix expression.

Here is source code of the C++ Program to Construct an Expression Tree for a Postfix Expression. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

```
#include <iostream>
```
```
#include <conio.h>
```
```
 
```
```
using namespace std;
```
```
 
```
```
struct node
```
```
{
```
```
        char data;
```
```
        node *left;
```
```
        node *right;
```
```
};
```
```
 
```
```
char postfix[35];
```
```
int top = -1;
```
```
node *arr[35];
```
```
 
```
```
int r(char inputchar)
```

{ //for checking symbol is operand or operator

    if (inputchar == '+' || inputchar == '-' || inputchar == '*' || inputchar

```
            == '/')
```
```
        return (-1);
```

    else if (inputchar >= 'a' || inputchar <= 'z')

```
        return (1);
```

    else if (inputchar >= 'A' || inputchar <= 'Z')

```
        return (1);
```
```
    else
```
```
        return (-99); //for error
```
```
}
```
```
 
```

//it is used for inseting an single element in//a tree, i.e. is pushing of single element.

```
void push(node *tree)
```
```
{
```
```
    top++;
```
```
    arr[top] = tree;
```
```
}
```
```
 
```
```
node *pop()
```
```
{
```
```
    top--;
```
```
    return (arr[top + 1]);
```
```
}
```
```
 
```
```
void create_expr_tree(char *suffix)
```
```
{
```
```
    char symbol;
```
```
    node *newl, *ptr1, *ptr2;
```

    int flag; //flag=-1 when operator and flag=1 when operand

    symbol = suffix[0]; //Read the first symbol from the postfix expr.

    for (int i = 1; symbol != NULL; i++)

```
    { //continue till end of the expr.
```

        flag = r(symbol); //check symbol is operand or operator.

        if (flag == 1)//if symbol is operand.

```
        {
```
```
            newl = new node;
```
```
            newl->data = symbol;
```
```
            newl->left = NULL;
```
```
            newl->right = NULL;
```
```
            push(newl);
```
```
        }
```
```
        else
```

        { //If the symbol is operator//pop two top elements.

```
            ptr1 = pop();
```
```
            ptr2 = pop();
```
```
            newl = new node;
```
```
            newl->data = symbol;
```
```
            newl->left = ptr2;
```
```
            newl->right = ptr1;
```
```
            push(newl);
```
```
        }
```
```
        symbol = suffix[i];
```
```
    }
```
```
}
```
```
 
```
```
void preOrder(node *tree)
```
```
{
```
```
    if (tree != NULL)
```
```
    {
```
```
        cout << tree->data;
```
```
        preOrder(tree->left);
```
```
        preOrder(tree->right);
```
```
    }
```
```
}
```
```
 
```
```
void inOrder(node *tree)
```
```
{
```
```
    if (tree != NULL)
```
```
    {
```
```
        inOrder(tree->left);
```
```
        cout << tree->data;
```
```
        inOrder(tree->right);
```
```
    }
```
```
}
```
```
 
```
```
void postOrder(node *tree)
```
```
{
```
```
    if (tree != NULL)
```
```
    {
```
```
        postOrder(tree->left);
```
```
        postOrder(tree->right);
```
```
        cout << tree->data;
```
```
    }
```
```
}
```
```
 
```
```
int main(int argc, char **argv)
```
```
{
```

    cout << "Enter Postfix Expression : ";

```
    cin >> postfix;
```
```
 
```
```
    //Creation of Expression Tree
```
```
    create_expr_tree(postfix);
```
```
 
```

    //Traversal Operation on expression tree

    cout << "\nIn-Order Traversal :   ";

```
    inOrder(arr[0]);
```
```
 
```

    cout << "\nPre-Order Traversal :  ";

```
    preOrder(arr[0]);
```
```
 
```

    cout << "\nPost-Order Traversal : ";

```
    postOrder(arr[0]);
```
```
    return 0;
```
```
}
```

Output:

$ g++ ExpressionTreePostfix.cpp
$ a.out
 
Enter Postfix Expression : 32+5*
 
In-Order Traversal :   3+2*5
Pre-Order Traversal :  *+325
Post-Order Traversal : 32+5*
 
------------------
(program exited with code: 0)
Press return to continue

Sanfoundry Global Education & Learning Series – 1000 C++ Programs.

Here’s the list of Best Books in C++ Programming, Data Structures and Algorithms.

« Prev - C++ Program to Count the Number of Nodes in Binary Tree

» Next - C++ Program to Create Expression Tree from Infix Expression

Related Posts:

Check Programming Books
Practice Design & Analysis of Algorithms MCQ
Check Data Structure Books
Practice Programming MCQs
Practice Computer Science MCQs

Recommended Articles: