C Programming Implement a class ExprTree for representing ex

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.

Hints:
1. The function to parse a postfix expression and build the expression tree could be like this:
void parsePostfix(String expression)

The expression would consist of real numbers (non-zero, positive values), and the four operands. The number and operator are separated by a space.

2. To construct the expression tree for a given postfix expression, use the following algorithm:
a. Create a stack
b. Read next input symbol
c. If the symbol is a numeric value, create a new expression tree with a single node representing the value and push it onto the stack.
d. If the symbol is an operator, pop out two trees (T1 and T2) from the stack. Create a newtree with the operator as the root and T1 and T2 as two children. Push this new tree back onto the stack.
e. Repeat this procedure until the whole input is read.
f. At the end, the stack willl contain a single tree which would be the output.

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.

Solution

#include <iostream>
#include <conio.h>
#include <string.h>
using namespace std;
struct node
{
int data;
node *next;
}*p = NULL, *top = NULL, *save = NULL, *ptr;
void push(int x)
{
p = new node;
p->data = x;
p->next = NULL;
if (top == NULL)
{
top = p;
}
else
{
save = top;
top = p;
p->next = save;
}
}
char pop()
{
if (top == NULL)
{
cout<<\"underflow!!\";
}
else
{
ptr = top;
top = top->next;
return(ptr->data);
delete ptr;
}
}
int main()
{
char x[30];
int a, b;
cout<<\"enter the balanced expression\ \";
cin>>x;
for (int i = 0; i < strlen(x); i++)
{
if (x[i] >= 48 && x[i] <= 57)
push(x[i]-\'0\');
else if (x[i] >= 42 && x[i] <= 47)
{
a=pop();
b=pop();
switch(x[i])
{
case \'+\':
push(a+b);
break;
case \'-\':
push(a-b);
break;
case \'*\':
push(a*b);
break;
case \'/\':
push(a/b);
break;
}
}
}
cout<<\"ans is \"<<pop()<<endl;
getch();
}