Draw the Initial Expression Tree

C++ Program to Construct an Expression Tree for a given Prefix Expression

---

An expression tree is basically a binary tree which is used to represent expressions. In an expression tree, internal nodes correspond to operators and each leaf nodes correspond to operands. Here is a C++ program to construct an expression tree for a prefix Expression in inorder, preorder and postorder traversals.

Algorithm

Begin    class ExpressionTree which has following functions:    function push() to push nodes into the tree:    If stack is null       then push the node as first element    Else       push the node and make it top        function pop() to pop out nodes from the tree:    If stack is null       then print underflow    Else       Pop out the node and update top        function insert() to insert characters:    If it is digit       then push it.    Else if it is operator       Then pop it.    Else       Print "invalid Expression"          function postOrder() for postorder traversal:    If tree is not empty       postOrder(ptr->l)       postOrder(ptr->r)       Print root as ptr->d     function inOrder() for inorder traversal:    If tree is not empty       inOrder(ptr->l)       Print root as ptr->d       inOrder(ptr->r)     function preOrder() for preorder traversal:    If tree is not empty       Print root as ptr->d       preOrder(ptr->l)       preOrder(ptr->r) End

Example Code

#include <iostream> #include <cstdlib> #include <cstdio> #include <cstring> using namespace std;  class TreeN//node declaration {    public: char d;    TreeN *l, *r;    TreeN(char d) {       this->d = d;       this->l = NULL;       this->r = NULL;    } };  class StackNod// stack declaration {    public: TreeN *treeN;    StackNod *n;    StackNod(TreeN*treeN)//constructor {       this->treeN = treeN;       n = NULL;    } };  class ExpressionTree {    private: StackNod *top;    public: ExpressionTree() {       top = NULL;    }    void clear() {       top = NULL;    }     void push(TreeN *ptr) {       if (top == NULL)          top = new StackNod(ptr);       else {          StackNod *nptr = new StackNod(ptr);          nptr->n = top;          top = nptr;       }    }     TreeN *pop() {       if (top == NULL) {          cout<<"Underflow"<<endl;       } else {          TreeN *ptr = top->treeN;          top = top->n;          return ptr;       }    }     TreeN *peek() {       return top->treeN;    }     void insert(char val) {       if (isDigit(val)) {          TreeN *nptr = new TreeN(val);          push(nptr);       } else if (isOperator(val)) {          TreeN *nptr = new TreeN(val);          nptr->l = pop();          nptr->r= pop();          push(nptr);       } else {          cout<<"Invalid Expression"<<endl;          return;       }    }     bool isDigit(char ch) {       return ch >= '0' && ch <= '9';    }     bool isOperator(char ch) {       return ch == '+' || ch == '-' || ch == '*' || ch == '/';    }     int toDigit(char ch) {       return ch - '0';    }     void buildTree(string eqn) {       for (int i = eqn.length() - 1; i >= 0; i--)          insert(eqn[i]);    }     void postfix() {       postOrder(peek());    }     void postOrder(TreeN*ptr) {       if (ptr != NULL) {          postOrder(ptr->l);          postOrder(ptr->r);          cout<<ptr->d;       }    }    void infix() {       inOrder(peek());    }     void inOrder(TreeN *ptr) {       if (ptr != NULL) {          inOrder(ptr->l);          cout<<ptr->d;          inOrder(ptr->r);       }    }    void prefix() {       preOrder(peek());    }     void preOrder(TreeN *ptr) {       if (ptr != NULL) {          cout<<ptr->d;          preOrder(ptr->l);          preOrder(ptr->r);       }    } };  int main() {    string s;    ExpressionTree et;    cout<<"\nEnter equation in Prefix form: ";    cin>>s;    et.buildTree(s);    cout<<"\nPrefix : ";    et.prefix();    cout<<"\n\nInfix : ";    et.infix();    cout<<"\n\nPostfix : ";    et.postfix(); }

Output

Enter equation in Prefix form: ++7*626 Prefix : ++7*626 Infix : 7+6*2+6 Postfix : 762*+6+

Published on 03-Apr-2019 14:24:04

• Related Questions & Answers
• C++ Program to Construct an Expression Tree for a Postfix Expression
• Python Program to Construct an Expression Tree of a given Expression
• Algorithm to construct an Expression Tree in Data Structure
• Construct the Regular expression for the given languages.
• C Program to construct DFA for Regular Expression (a+aa*b)*
• C++ Program to Implement Expression Tree Algorithm
• Convert Infix to Prefix Expression
• Construct the Regular expression for the given languages by the user.
• Program to build and evaluate an expression tree using Python
• Construct NFA with Epsilon moves for regular expression a+ba*.
• Evaluation of Expression Tree in C++
• Expression Tree with Example in C++
• What is an expression tree in DBMS?
• Convert Ternary Expression to a Binary Tree in C++
• Construct a Finite Automata for the regular expression ((a+b)(a+b))*.

jacobsonafor1997.blogspot.com

Source: https://www.tutorialspoint.com/cplusplus-program-to-construct-an-expression-tree-for-a-given-prefix-expression

Share this post