Chương trình C ++ để tạo một cây biểu thức cho một biểu thức tiền tố nhất định

Cây biểu thức về cơ bản là một cây nhị phân được sử dụng để biểu diễn các biểu thức. Trong một cây biểu thức, các nút bên trong tương ứng với các toán tử và mỗi nút lá tương ứng với các toán hạng. Đây là một chương trình C ++ để xây dựng một cây biểu thức cho một biểu thức tiền tố trong các trình duyệt inorder, preorder và postorder.

Thuật toán

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

Mã mẫu

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

Đầu ra

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