ExpressionTree.cpp

#include <iostream>
#include <string>
using namespace std;
const int Size = 50;

struct BSTNode
{
    string data;
    BSTNode* LChild;
    BSTNode* RChild;
} *root = NULL;

struct Stack
{
    BSTNode* arr[Size];
    int top = -1;
};

void push(Stack &stack, BSTNode* node)
{
    if (stack.top == Size - 1)
    {
        cout << "Stack is full" << node->data << endl;
        return;
    }
    stack.arr[++stack.top] = node;
}

BSTNode* pop(Stack &stack)
{
    if (stack.top == -1)
    {
        return NULL;
    }
    return stack.arr[stack.top--];
}
void preOrder(BSTNode* node){
    if (node != NULL)
    {
        cout<<node->data<<" ";
        preOrder(node->LChild);
        preOrder(node->RChild);
    }
    
}
void InOrder(BSTNode* node){
    if (node != NULL)
    {
        InOrder(node->LChild);
        cout<<node->data<<" ";
        InOrder(node->RChild);
    }
    
}
void postOrder(BSTNode* node){
    if (node != NULL)
    {
        postOrder(node->LChild);
        postOrder(node->RChild);
        cout<<node->data<<" ";
    }
}
BSTNode* create_tree(BSTNode* node,Stack& stack,string exp){
    string c;
    for (size_t i = 0; i < exp.length(); i++)
    {
        c = exp[i];
        if ((exp[i] >= 'a' && exp[i] <= 'z') || (exp[i] >= '0' && exp[i]<= '9'))
        {
            //push the operands in postfix stack
            BSTNode* newNode = (BSTNode*)malloc(sizeof(BSTNode));
            newNode->data = c;
            newNode->LChild = NULL;
            newNode->RChild = NULL;
            push(stack,newNode);
            node = newNode;
        }
        else
        {
            //if the operator is "<=",">=","==","!=","&&","||"
            if (((exp[i] =='!'||exp[i] =='='|| exp[i] =='<' || exp[i] =='>') && exp[i+1] == '=') || ((exp[i] =='&' && exp[i+1] == '&') || exp[i] == '|' && exp[i+1] == '|'))
            {
                c+= exp[i+1];
                //skip the other character b/c it is part of the operator
                i++;
            }
            BSTNode* newNode = (BSTNode*)malloc(sizeof(BSTNode));
            newNode->data = c;
            newNode->RChild = pop(stack);
            newNode->LChild = pop(stack);
            push(stack,newNode);
            node = newNode;
        }
    }
    return node;
}
int main(int argc, char const *argv[])
{
    Stack stack;
    string exp;
    cout << "Enter the postfix expression: ";
    getline(cin, exp);
    root = create_tree(root,stack,exp);
    preOrder(root);
    return 0;
}