ExpressionTree.cpp

#include <iostream>
using namespace std;

class TreeNode
{
public:
  char data;
  TreeNode *lChild, *rChild;
  TreeNode(char data, TreeNode *left = NULL, TreeNode *right = NULL)
  {
    this->data = data;
    this->lChild = left;
    this->rChild = right;
  }
};

class Stack
{
public:
  TreeNode *treeNode;
  Stack *next;
  Stack(TreeNode *treeNode)
  {
    this->treeNode = treeNode;
    next = NULL;
  }
};

class ExpressionTree
{
private:
  Stack *top;

public:
  ExpressionTree()
  {
    top = NULL;
  }

  void push(TreeNode *ptr)
  {
    if (top == NULL)
      top = new Stack(ptr);
    else
    {
      Stack *nptr = new Stack(ptr);
      nptr->next = top;
      top = nptr;
    }
  }

  TreeNode *pop()
  {
    TreeNode *ptr = top->treeNode;
    top = top->next;
    return ptr;
  }

  TreeNode *peek()
  {
    return top->treeNode;
  }
  // function to insert character
  void insert(char val)
  {
    // If the encountered character is Number make a node an push it on stack
    if (isOperand(val))
    {
      TreeNode *nptr = new TreeNode(val);
      push(nptr);
    }
    // else if it is operator then make a node and left and
    else if (isOperator(val))
    {
      TreeNode *nptr = new TreeNode(val);
      nptr->lChild = pop();
      nptr->rChild = pop();
      push(nptr);
    }
  }

  bool isOperand(char ch)
  {
    return ch >= '0' && ch <= '9' || ch >= 'A' && ch <= 'Z' || ch >= 'a' && ch <= 'z';
  }

  bool isOperator(char ch)
  {
    return ch == '+' || ch == '-' || ch == '*' || ch == '/';
  }
  // function to construct expression Tree
  void construct(string eqn)
  {
    for (int i = eqn.length() - 1; i >= 0; i--)
      insert(eqn[i]);
  }
  void inOrder(TreeNode *ptr)
  {
    if (ptr != NULL)
    {
      inOrder(ptr->lChild);
      cout << ptr->data;
      inOrder(ptr->rChild);
    }
  }
};

int main()
{
  string exp;
  ExpressionTree et;
  cout << "Enter expression in Prefix form: ";
  cin >> exp;
  et.construct(exp);
  cout << "In-order Traversal of Expression Tree : ";
  et.inOrder(et.peek());
  return 0;
};