सी ++ प्रोग्राम किसी दिए गए उपसर्ग अभिव्यक्ति के लिए एक अभिव्यक्ति वृक्ष का निर्माण करने के लिए

एक्सप्रेशन ट्री मूल रूप से एक बाइनरी ट्री है जिसका उपयोग एक्सप्रेशन को दर्शाने के लिए किया जाता है। एक्सप्रेशन ट्री में, आंतरिक नोड्स ऑपरेटरों के अनुरूप होते हैं और प्रत्येक लीफ नोड ऑपरेंड के अनुरूप होते हैं। इन-ऑर्डर, प्री-ऑर्डर और पोस्ट-ऑर्डर ट्रैवर्सल में एक्सप्रेशन एक्सप्रेशन के लिए एक्सप्रेशन ट्री बनाने के लिए यहां एक C++ प्रोग्राम है।

एल्गोरिदम

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

उदाहरण कोड

#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();
}

आउटपुट

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