Question

Arithmetic expressions such as

                                2 * (9 / -3)                                                                   

have an inherent tree-like structure. For example, Figure A is a representation of the expression in Equation (1). This kind of tree is called an expression tree.

The terminal nodes (leaves) of an expression tree are the variables or constants in the expression (2, 9, 3). The non-terminal nodes of an expression tree are the operators (*, / and -). Notice that the parentheses which appear in Equation (1) do not appear in the tree. Nevertheless, the tree representation has captured the intent of the parentheses since the subtraction is lower in the tree than the multiplication.

Figure A: Tree representing the expression 2 * (9 / -3).

The common arithmetic operators are either unary or binary. For example, addition, subtraction, multiplication, and division are all binary operations and negation is a unary operation. Therefore, the non-terminal nodes of the corresponding expression trees have either one or two non-empty subtrees. That is, expression trees are usually binary trees.

QUESTIONS:

Create an expression tree program that reads a prefix* arithmetic expression and displays it in a binary tree form. Assume that the expression consists of single-digit, nonnegative integers (‘0’ to ‘9’) and four basic arithmetic operators (‘+’, ‘-‘, ‘*’, and ‘/’). Further, assume that the arithmetic expression is input from the keyboard with all the characters on one line.

Then, using traversal techniques display the arithmetic expression in preorder, inorder and postorder notations. Finally evaluates the expression and output the result. Display suitable messages.

Answer 1

// PLEASE LIKE THE SOLUTION
// FEEL FREE TO DISCUSS IN COMMENT SECTION
// C++ PROGRAM

#include<bits/stdc++.h>
using namespace std;

typedef struct expressionTree{
   char val;
   expressionTree *left, *right;
}Node;

// build tree
char* build(Node** root, char* ch){
   if (*ch == '\0'){
       return NULL;
   }

   while (1){
       char* q = NULL;
       if (*root == NULL){
           // build child
           Node* temp = (Node*)malloc(sizeof(Node));
           temp->val = *ch;
           temp->left = NULL;
           temp->right = NULL;
           *root = temp;
       }
       else{
           // if operand
           if (*ch >='0' && *ch <='9'){
               return ch;
           }
          
           // build left
           q = build(&(*root)->left, ch+1);

           // build right
           q = build(&(*root)->right, q+1);

           return q;
       }
   }
}

void preorder(Node* root){
   if(root == NULL){
       return;
   }
   else{
       cout<<(root->val)<<" ";
       preorder(root->left);
       preorder(root->right);
   }
}

void inorder(Node* root){
   if(root == NULL){
       return;
   }
   else{
       inorder(root->left);
       cout<<(root->val)<<" ";
       inorder(root->right);
   }
}

void postorder(Node* root){
   if(root == NULL){
       return;
   }
   else{
       preorder(root->left);
       preorder(root->right);
       cout<<(root->val)<<" ";
   }
}

// evaluate
double evaluate(char a[]){
   int n=strlen(a);
  
   // stack
   stack<double> st;
   for(int i=n-1;i>=0;i--){
       //cout<<a[i]<< " ";
       if(a[i] >= '0' && a[i] <= '9'){
           st.push(a[i]-'0');
       }
       if(a[i] == '*'){
           double t1 = st.top();
           st.pop();

           double t2 = st.top();
           st.pop();

           double r = t1*t2;
           st.push(r);
       }

       if(a[i] == '/'){
           double t1 = st.top();
           st.pop();

           double t2 = st.top();
           st.pop();

           double r = t1/t2;
           st.push(r);
       }

       if(a[i] == '+'){
           double t1 = st.top();
           st.pop();

           double t2 = st.top();
           st.pop();

           double r = t1+t2;
           st.push(r);
       }

       if(a[i] == '-'){
           double t1 = st.top();
           st.pop();

           double t2 = st.top();
           st.pop();

           double r = t1-t2;
           st.push(r);
       }
      
   }

   return st.top();
}

// Driver program to test above
int main(){
   Node* root = NULL;
   char a[100];
   scanf("%s",a);

   build(&root, a);
   printf("PreOrder = ");
   preorder(root);
   printf("\n");
  
   printf("InOrder = ");
   inorder(root);
   printf("\n");

   printf("PostOrder = ");
   postorder(root);
   printf("\n");

   double re = evaluate(a);
   cout<<"Evaluation = "<<re<<endl;
   return 0;
}

// SAMPLE OUTPUT