In this C++ assignment you are to read two (2) post-fix expressions from a comma
ID: 3689645 • Letter: I
Question
In this C++ assignment you are to read two (2) post-fix expressions from a command line, build a parse tree, and compare the two trees against each other for equivalency. The equivalency between two parse trees is defined as identity: If two trees are identical in the structure and the values return value 1. Return value 0, if two trees are structurally equivalent, that is two trees have the same shape but the operators or operands values can be different. Finally, return -1 if the two trees have different shape.
Before you start building the code and the algorithm that compares these trees, build a Tests.txt file with all tets necessary to convince yourself that your code works (make sure you cover all scenarios that will test the equivalency function).
Step 0: build a Tests.txt file
Step 1: read in the post-fix expression 1 from a command line and build an expression tree that corresponds to the expression
Step 2: repeat step 1 for expression 2
Step 3: write a recursive algorithm that will traverse both trees at the same time (side by side) and compares the structure and the values stored in two parse trees you built in steps 1 and 2.
A couple of examples:
The requirements for the expression tree in the post-fix notation are as follows:
To recap, the postfix expressions (often referred to as "Reverse Polish Notation") are arithmetic expressions built around a user-implemented stack data structure. These expressions have an advantage over ordinary (in-fix) expressions in that every expression can be written without parentheses. In other words, there is no need to use the parentheses to apply the order of operation when evaluating an expression. Each binary operator expression will be defined as a postfix expression N operands and N-1 operators. The unary operators will have the same number of operators and operands. Each operand is pushed onto the stack. Each binary operator causes the top two operands to be popped off the stack; the first popped operand becomes the second argument to the operator, and the second popped operand becomes the first argurment. The operation is then performed on these two operands, and the result is pushed onto the stack. The unary operations are performed in a similar patter but with one operand.
Four error conditions can occur:
- SYNTAX ERROR: valid postfix expressions should consist only of blanks, positive decimal integer operands, and the binary integer operators +, -, *, /, and an unary operator sqrt. The operands and operators will be separated by one or more blanks. Zero or more blanks may appear at either the beginning or the end of the expression. Negative operands are not allowed in the input expression (although the evaluation of a given expression may produce a negative result).
- STACK UNDERFLOW: postfix expressions are evaluated from left to right. An underflow error will occur if, at any time during expression evaluation, the number of operators enountered up to that point does not match the number of operands.
- TOO MANY OPERANDS: If, after evaluating the entire postfix expression, the stack contains more than one value, then the given postfix expression contained too many operands.
- DIVDE BY ZERO: If the top operand on the stack is a 0 when the / operator is detected, then a divide-by-zero error will occur. This error cannot be readily detected without evaluation of the expression.
You are required to implement binary operations: /;*;-;+ and an unary operation sqrt. Examples of valid postfix expressions include the following:
12 (returns 12)
16 sqrt (returns 4)
100 567 - (returns -467)
1 3 + 4 5 * / (returns [1 + 3] / [4 * 5] = 4 / 20 = 0)
11 22 33 44 55 66 77 88 + - * / / * +
The following are examples of invalid postfix expressions:
12 3f - (syntax error)
1 + (stack underflow)
1 2 * / 3 4 - (stack underflow)
11 23 79 * (too many operands)
8 3 + 4 6 * (too many operands)
1 33 22 11 + - / (divide by zero error)
Make sure that all objects are correctly allocated on the heal and after the algorithm is finished checking the equivalence, deallocate all objects from heap and gracefully terminate your application. Your program has to be able to parse and build a tree of any shape, size or combination of operators and values.
Explanation / Answer
Sample code logic-
/*TREE STRUCTURE*/
struct tree
{
int value;
struct tree *right,*left;
};
/*Method to create tree*/
void create(struct tree *p)
{
int choice;
cout<<" Enter value";
cin>>p->value;
cout<<" Do you Want to Enter left Child? "<<p->value<<" .1.YES/2.NO";
cin>>choice;
if(choice==1)
{
p->left=(tree*)malloc(sizeof(tree));
create(p->left);
}
else
{
p->left=NULL;
}
cout<<"Do you Want to Enter Right Child?"<<p->value<<" .1.YES/2.NO";
cin>>choice;
if(choice==1)
{
p->right=(tree*)malloc(sizeof(tree));
create(p->right);
}
else
{
p->right=NULL;
}
}
/*METHOD FOR COMPARING TWO TREES*/
int compare(struct tree *p,struct tree *q)
{
if(p==NULL&&q==NULL)
return 1;
else if(p==NULL||q==NULL)
return 0;
else if(p->value==q->value)
{
int s1=compare(p->left,q->left);
int s2=compare(p->right,q->right);
return s1*s2;
}
else
return 0;
}
void main()
{
clrscr();
cout<<" The Comparision of Two Trees ";
struct tree *t1;
cout<<"Enter First Tree ";
t1=(tree*)malloc(sizeof(tree));
create(t1);
struct tree *t2;
cout<<" Enter Second Tree ";
t2=(tree*)malloc(sizeof(tree));
create(t2);
if(compare(t1,t2)==1)
cout<<"Both Trees Are Similar";
else
cout<<"Both Trees Are not Similar";
}
note-by using the above code with required modification for reading a symbol the given question can be answered.