This lab is a follow-up of Lab 1. In this lab, we want to build an expression tr
ID: 3743132 • Letter: T
Question
This lab is a follow-up of Lab 1.
In this lab, we want to build an expression tree for a given arithmetic expression. Modify the mutually recursive codes expr.c so that the function eval_expr() returns an expression tree which is of the type btree (instead of returning an integer). Thus, the prototypes of eval_expr_1(), eval_expr_2(), eval_expr_3(), and eval_expr_4() are:
Other functions that evaluate expressions are modified similarly.
Also, you need to modify the main program main.c so that instead of printing out the integer value for the given arithmetic expression, the program
prints out the expression tree by using an postorder traversal, using a recursive function
Suppose the expression is
the expression tree is
The postorder traversal of the expression tree prints out the following expression in postfix notation:
Observe that in a postfix notation, there is no need to use parenthesis.
The postfix expression can be evaluated using an operand stack.
Note that we get the same result as that obtained when evaluating the expression in infix notation:
You are provided with the tree module that consists of bTree.h and bTree.c.
TASK 1 Modify the expr.c from Lab 1 so that it returns an expression tree. In main.c, perform a postorder traversal on the expression printing the expression in postfix notation.
The commands to compile and execute the program are as follows:
gcc -c expr.c
gcc -c error.c
gcc -c input_token.c
gcc -c bTree.c
gcc main.c expr.o input_token.o error.o bTree.o -o evalInfix
TASK 2 You are provided with the stack module that consists of stack.h and stack.c. Given that an input is in postfix notation, write a program main1.c that evaluates the expression in postfix notation (which is read from the input using the input token module) using an operand stack.
The commands to compile and execute the program are as follows:
gcc -c stack.c
gcc main1.c input_token.o error.o stack.o -lm -o evalPostfix
TESTING
Next, we can execute first evalInfix on an input file to produce an output in postfix notation, which is then passed to evalPostfix for execution using the pipe facility in Linux.
evalInfix data1 | evalPostfix
which should produce the output:
expression result = 597656328
FILES:
******************************************************************EXPR.C******************************************************************
******************************************************************EXPR.H******************************************************************
******************************************************************INPUT_TOKEN.C******************************************************************
******************************************************************INPUT_TOKEN.H******************************************************************
******************************************************************ERROR.C******************************************************************
******************************************************************ERROR.H******************************************************************
******************************************************************MAIN.C******************************************************************
******************************************************************BTREE.C******************************************************************
******************************************************************BTREE.H******************************************************************
******************************************************************STACK.C******************************************************************
******************************************************************STACK.H******************************************************************
Explanation / Answer
//main.c
#include "input_token.h"
#include "expr.h"
#include "error.h"
#include "BTree.h"
main(int argc, char *argv[])
{ Tree val;
fpi = fopen( *++argv, "r" );
val = evaluate_expression();
//In order traversal
printf("In-order traversal: ");
in_order_traversal(val);
printf(" ");
//Post order traversal
printf("Post-order traversal: ");
post_order_traversal(val);
printf(" ");
//Evaluate expression
int total = eval(val);
printf("The integer value evaluated is %d ", total);
}
----------------------------------------------------------------------------
//input_token.c
#include "input_token.h"
#include "error.h"
void get_operand(int *w) {
int c;
*w = 0;
while ((c = getc(fpi)) != EOF)
if (c >= '0' && c <= '9') *w = 10*(*w) + c - 48;
else {ungetc(c,fpi); return;}
}
int get_token(int *w) {
int c;
while ((c = getc(fpi)) != EOF)
if ( c=='(' ) return(OpenBracket);
else if ( c==')' ) return(CloseBracket);
else if ( c=='+' ) return(Plus);
else if ( c=='-' ) return(Minus);
else if ( c=='*' ) return(Mult);
else if ( c=='/' ) return(Divide);
else if ( c>='0' && c<='9' ) {ungetc(c,fpi);get_operand(w);return(Operand);}
else if ( c>=33 && c<=126 ) error(1);
return(EOF);
}
---------------------------------------------------------------------------
//input_token.h
#include <stdio.h>
FILE *fpi;
/*
#define EOF -1 */
#define OpenBracket 0
#define CloseBracket 1
#define Plus 2
#define Minus 3
#define Mult 4
#define Divide 5
#define Operand 6
int get_token(int *w);
------------------------------------------------------------------------
//BTree.c
#include "BTree.h"
#include "input_token.h"
struct BinaryTree
{
DATA val;
struct BinaryTree* left;
struct BinaryTree* right;
};
Tree LeafTree(DATA d) {
Tree t;
t = malloc(sizeof(Tree));
t->val = d;
t->left = NULL;
t->right = NULL;
return t;
}
Tree BTree(DATA d, Tree l, Tree r) {
Tree t;
t = malloc(sizeof(Tree));
t->val = d;
t->left = l;
t->right = r;
return t;
}
bool isLeaf(Tree root) {
return root->left == NULL && root->right == NULL;
}
DATA getData(Tree root) {
return root->val;
}
Tree getLeft(Tree root) {
return root->left;
}
Tree getRight(Tree root) {
return root->right;
}
void in_order_traversal(Tree t) {
if(isLeaf(t)) {
printf("%d", t->val);
return;
}
printf("(");
in_order_traversal(t->left);
if(t->val==Plus) { printf("+"); }
else if(t->val==Minus) {printf("-");}
else if(t->val==Mult) { printf("*");}
else if(t->val==Divide) { printf("/");}
else {printf("%c", t->val);}
in_order_traversal(t->right);
printf(")");
}
void post_order_traversal(Tree t) {
if(isLeaf(t)) {
printf("%d ", t->val);
return;
}
post_order_traversal(t->left);
post_order_traversal(t->right);
if(t->val==Plus) { printf("+ "); }
else if(t->val==Minus) {printf("- ");}
else if(t->val==Mult) { printf("* ");}
else if(t->val==Divide) { printf("/");}
else {printf("%d ", t->val);}
}
int eval(Tree t) {
if(isLeaf(t)) {return t->val;}
int lval = eval(t->left);
int rval = eval(t->right);
if(t->val==Plus) { return lval+rval;}
else if(t->val==Minus) { return lval-rval;}
else if(t->val==Mult) { return lval*rval;}
else if(t->val==Divide) { return lval/rval;}
}
-------------------------------------------------------------------
//BTree.h
#ifndef BTree_H
#define BTree_H
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
typedef int DATA;
typedef struct BinaryTree* Tree;
Tree LeafTree(DATA d);
Tree BTree(DATA d, Tree l, Tree r);
bool isLeaf(Tree root);
DATA getData(Tree root);
Tree getLeft(Tree root);
Tree getRight(Tree root);
void in_order_traversal(Tree t);
void post_order_traversal(Tree t);
int eval(Tree t);
#endif
-------------------------------------------------------------------
//error.c
#include <stdio.h>
#include <stdlib.h>
void error( int i )
{
fprintf(stderr, "error: %d ", i);
exit(i);
}
----------------------------------------------------------------
//error.h
void error( int i );
-------------------------------------------------------------------
//expr.c
#include "input_token.h"
#include "error.h"
#include "BTree.h"
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
Tree eval_expr_4(Tree opn1, int opr1, Tree opn2, int opr2);
Tree eval_expr_3(Tree opn1, int opr1, Tree opn2);
Tree eval_expr_2(Tree opn1, int opr1);
Tree eval_expr_1(Tree opn1);
Tree eval_expr();
Tree evaluate_expression() {
int w;
Tree val;
if (get_token(&w)!=OpenBracket) error(-1);
val = eval_expr();
if (get_token(&w)!=EOF) error(-2);
return val;
}
Tree eval_expr()
/* have seen
(
read until we find a matching parenthesis.
the expression enclosed is evaluated.
return the integer value computed.
*/
{int w;
switch (get_token(&w))
{ case OpenBracket:
return(eval_expr_1(eval_expr()));
case CloseBracket:
error(2);
case Plus:
error(3);
case Minus:
error(4);
case Mult:
error(5);
case Divide:
error(6);
case Operand:
return(eval_expr_1(LeafTree(w)));
case EOF:
error(7);
}
}
Tree eval_expr_1(Tree opn1)
/* have seen
( opn1
where opn1 is an operand
read until we find a matching parenthesis.
the expression enclosed is evaluated.
return the integer value computed.
*/
{int w;
switch (get_token(&w))
{ case OpenBracket:
error(8);
case CloseBracket:
return(opn1);
case Plus:
return(eval_expr_2(opn1,Plus));
case Minus:
return(eval_expr_2(opn1,Minus));
case Mult:
return(eval_expr_2(opn1,Mult));
case Divide:
return(eval_expr_2(opn1,Divide));
case Operand:
error(10);
case EOF:
error(11);
}
}
Tree eval_expr_2(Tree opn1,int opr1)
/* have seen
( opn1 opr1
where opn1 is an operand
and opr1 is an operator
read until we find a matching parenthesis.
the expression enclosed is evaluated.
return the integer value computed.
*/
{int w;
switch (get_token(&w))
{ case OpenBracket:
return(eval_expr_3(opn1,opr1,eval_expr()));
case CloseBracket:
error(12);
case Plus:
error(13);
case Minus:
error(14);
case Mult:
error(15);
case Divide:
error(16);
case Operand:
return(eval_expr_3(opn1,opr1,LeafTree(w)));
case EOF:
error(17);
}
}
Tree eval_expr_3(Tree opn1,int opr1, Tree opn2)
/* have seen
( opn1 opr1 opn2
where opn1 and opn2 are operands,
opr1 is an operator
read until we find a matching parenthesis.
the expression enclosed is evaluated.
return the integer value computed.
*/
{int w;
switch (get_token(&w))
{ case OpenBracket:
error(18);
case CloseBracket:
switch (opr1)
{ case Plus: return (BTree (Plus, opn1, opn2));
case Minus: return (BTree (Minus, opn1, opn2));
case Mult: return (BTree (Mult, opn1, opn2));
case Divide: return (BTree (Divide, opn1, opn2));
}
case Plus:
switch (opr1)
{
case Plus: return (eval_expr_2(BTree(Plus,opn1,opn2),Plus));
case Minus: return(eval_expr_2(BTree(Minus,opn1,opn2),Plus));
case Mult: return(eval_expr_2(BTree(Mult,opn1,opn2),Plus));
case Divide: return(eval_expr_2(BTree(Divide,opn1,opn2),Plus));
}
case Minus:
switch (opr1)
{ case Plus: return(eval_expr_2(BTree(Plus,opn1,opn2),Minus));
case Minus: return(eval_expr_2(BTree(Minus,opn1,opn2),Minus));
case Mult: return(eval_expr_2(BTree(Mult,opn1,opn2),Minus));
case Divide: return(eval_expr_2(BTree(Divide,opn1,opn2),Minus));
}
case Mult:
switch (opr1)
{ case Plus: return(eval_expr_4(opn1,opr1,opn2,Mult));
case Minus: return(eval_expr_4(opn1,opr1,opn2,Mult));
case Mult: return(eval_expr_2(BTree(Mult,opn1,opn2),Mult));
case Divide: return(eval_expr_2(BTree(Divide,opn1,opn2),Mult));
}
case Divide:
switch (opr1)
{ case Plus: return(eval_expr_4(opn1,opr1,opn2,Divide));
case Minus: return(eval_expr_4(opn1,opr1,opn2,Divide));
case Mult: return(eval_expr_2(BTree(Mult,opn1,opn2),Divide));
case Divide: return(eval_expr_2(BTree(Divide,opn1,opn2),Divide));
}
case Operand:
error(20);
case EOF:
error(21);
}
}
Tree eval_expr_4(Tree opn1, int opr1, Tree opn2, int opr2)
/* have seen
( opn1 opr1 opn2 opr2
where opn1 and opn2 are operands,
opr1 and opr2 are operators
read until we find a matching parenthesis.
the expression enclosed is evaluated.
return the integer value computed.
*/
{int w;
switch (get_token(&w))
{ case OpenBracket:
switch (opr2)
{case Mult: return(eval_expr_3(opn1,opr1,BTree(Mult,opn2,eval_expr())));
case Divide: return(eval_expr_3(opn1,opr1,BTree(Divide,opn2,eval_expr())));
}
case CloseBracket:
error(22);
case Plus:
error(23);
case Minus:
error(24);
case Mult:
error(25);
case Divide:
error(26);
case Operand:
switch (opr2)
{ case Mult: return(eval_expr_3(opn1,opr1,BTree(Mult,opn2,LeafTree(w))));
case Divide: return(eval_expr_3(opn1,opr1,BTree(Divide,opn2,LeafTree(w))));
}
case EOF:
error(27);
}
}//end
------------------------------------------------------------------------------------------------------------------
//expr.h
#include "BTree.h"
Tree evaluate_expression();
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.