Question

C++ Programming

Implement a class ExprTree for representing expression trees, including:

1. The operations to build an expression tree from a postfix arithmetic expression.
2. A recursive function to "evaluate" a non-empty expression tree using these rules:
   - If the tree has only one node (which must be a leaf), then the evaluation of the tree returns the real number (type double) that is the node's entry.
- If the tree has more tha one node, and the root contains an "operator" (+, -, %, /), then first evaluate the left subtree, then the right subtree, and apply the "operator" on these two values to get the result.

Your main function should perform the following tasks:
   1. Prompt for input of a postfix expression. Print the expression.
2. Parse the postfix expression and build the expression tree (Hint: using a Stack to store the operations while building the expression tree).
3. Evaluate the expression tree. Print the result.
   4. Repeat steps 1-3 for three postfix expressions.

Answer 1

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

struct Node
{
char data;
Node* l, *r;
};

bool isOperatorOrNot(char c)
{
if (c == '+' || c == '-' ||
c == '*' || c == '/' ||
c == '^')
return true;
return false;
}

void inorderTraversal(Node *t)
{
if(t)
{
inorderTraversal(t->l);
cout<<t->data<<" " ;
inorderTraversal(t->r);
}
}

Node* createNewNode(int v)
{
Node *temp = new Node;
temp->l = temp->r = NULL;
temp->data = v;
return temp;
};

Node* createTree(char postfixExpre[])
{
stack<Node *> st;
Node *t, *t1, *t2;


for (int i=0; i<strlen(postfixExpre); i++)
{
  
if (!isOperatorOrNot(postfixExpre[i]))
{
t = createNewNode(postfixExpre[i]);
st.push(t);
}
else
{
t = createNewNode(postfixExpre[i]);

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

  
t->r = t1;
t->l = t2;


st.push(t);
}
}

  
t = st.top();
st.pop();

return t;
}

int main()
{

int i=0;
char postfixExpre1[100];
  

while(i<3)
{
printf("\nEnter Postfix Expression\n");
cin>>postfixExpre1;
cout<<"Expression is "<<postfixExpre1<<endl;
Node* r = createTree(postfixExpre1);
cout<<"infix expression is \n";
inorderTraversal(r);
i++;
}
  
  
  
  
  
return 0;
}

==================================================

akshay@akshay-Inspiron-3537:~/Chegg$ g++ exp.cpp
akshay@akshay-Inspiron-3537:~/Chegg$ ./a.out

Enter Postfix Expression
ab+
Expression is ab+
infix expression is
a + b
Enter Postfix Expression
bc+
Expression is bc+
infix expression is
b + c
Enter Postfix Expression
cd*
Expression is cd*
infix expression is
c * d