Expression Evaluation Homework Solution using C

Question 1.

For the coding part of the assignment, first, you will create a typedef struct called Expression for holding expressions, and a function that can evaluate expressions built using your struct. This struct will have three components: a Data typedef union type, and two pointers to Expression's leftArgument and rightArgument. The Data union type contains either an Operation typedef enum or a char pointer. An Operation enum can be one of CONS, FIRST, or REST. Expression's can be used to represent things like:

FIRST(REST(CONS("a", CONS( "b", "c"))))

This would evaluate the string "b". Here CONS is intended to mean concatenate, REST is intended to return all characters from a string except the first, and FIRST is intended to return the first character of a string. For edge cases, FIRST applied to a NULL pointer returns NULL, REST on a NULL pointer or a single char returns NULL, CONS returns the other argument if either argument is NULL. Each of CONS, FIRST, and REST is assumed to take two arguments, but in the case of FIRST, and REST the second argument is ignored and so could be set to NULL. A Data struct using a char pointer as for an Expression still can be thought of as having two arguments, but in this case, both are ignored.

Put the definitions of Expression, Data, Operation in the header file expressions.h . Create three files test1.h, test2.h, test3.h, each should have one Expression tree in it (a global variable declaration Expression tree = ...; ) built out of Expression's and making use of each of the three operations and string literals.

You should have a file evaluator.c which contains a function of prototype: int eval(Expression E);

which recursively calculates the string (as a char*) of the supplied expression. Use malloc for appropriate memory allocations.

Finally, you will create a program driver.c which has the main() function. You should have a Makefile with targets test1, test2, test3, all, and clean. The test1, test2, test3 targets, test the evaluation of the given test1.h, test2.h, test3.h expression tree, all make each of test1, test2, and test3, clean gets rid of any intermediary files. The grader will switch into your Hw1 folder after unzipping Hw1.zip, and delete any executables. Then the grader will type:

make test1

to run the first test1. Similarly, for each of the other tests. Next,

./test1 will be typed. This should cause the main function in driver.c to be called. As make test1 was used, test1.h should have been included in the driver.c (similarly, if make test2 was called test2.h should have been included, etc). The function main should call eval(tree) and then write the output to the file output.txt.

The next requirement to complete c assignment is that each of the make targets test1, test2, test3 depends on sub-targets for each of the stages of the compilation phase test1. By default, if you type "gcc myfile.c" it runs the preprocessor, compiles this, and then links the result. Instead, you should have targets like preprocesstest1 which uses gcc's -E flag to output the result of just the preprocessor; compiletest1 which uses the -S flag to compile the result to assembly; assembletest1, which uses the as the command to produce object code; and linktest1 which uses ld to link the objects code together. So that you have actually looked at what each phase outputs, after you are done your project above type, "make compiletest1", copy the file evaluator.s to experiment.s. Find where in the assembly that FIRST of expressions is computed. Make a file first.s where you have copied and pasted this part of the assembly code for the grader to look and at the top of the file say what line it came from in experiments.

Solution:

Driver:

#include #include #include "expressions.h" int main() { char* result = eval(tree); FILE *f; f = fopen("output.txt", "w"); if (!f) { printf("Can not open output file\n"); return 1; } if (result != NULL) { fprintf(f, "%s\n", result); free(result); } else { fprintf(f, "NULL"); } fclose(f); return 0; }

Evaluator:

#include #include #include #include "expressions.h" char* eval(Expression e) { if (e.leftArgument == NULL && e.rightArgument == NULL) { int l1 = strlen(e.data.s); char* result = (char*)malloc(sizeof(char) * (l1 + 1)); strcpy(result, e.data.s); return result; } char* e1; char* e2; if (e.leftArgument != NULL) { e1 = eval(*e.leftArgument); } if (e.rightArgument != NULL) { e2 = eval(*e.rightArgument); } if (e.data.op == CONS) { if (e1 == NULL || e2 == NULL) { if (e.leftArgument != NULL) { free(e1); } if (e.rightArgument != NULL) { free(e2); } return NULL; } int l1 = strlen(e1); int l2 = strlen(e2); char* result = (char*)malloc(sizeof(char) * (l1 + l2 + 1)); strcpy(result, e1); strcat(result, e2); free(e1); free(e2); return result; } else if (e.data.op == FIRST){ if (e1 == NULL) { return NULL; } int l1 = strlen(e1); if (l1 < 1) { free(e1); return NULL; } char* result = (char*)malloc(sizeof(char) * 2); strncpy(result, e1, 1); result[1] = 0; free(e1); return result; } else { if (e1 == NULL) { return NULL; } int l1 = strlen(e1); if (l1 < 2) { free(e1); return NULL; } char* result = (char*)malloc(sizeof(char) * l1); strncpy(result, e1+1, l1-1); free(e1); return result; } }

Expressions:

#ifndef _EXPRESSIONS_H_ #define _EXPRESSIONS_H_ #include typedef enum { CONS, REST, FIRST } Operation; typedef union { Operation op; char* s; } Data; typedef struct expression{ Data data; struct expression* leftArgument; struct expression* rightArgument; } Expression; extern Expression tree; char* eval(Expression e); #endif

Test 1:

#ifndef _TEST_H_ #define _TEST_H_ #include #include "expressions.h" Expression a = { {.s = "Hello world!"}, NULL, NULL }; Expression b = { {.op = FIRST}, &a, NULL }; Expression c = { {.s = "!W"}, NULL, NULL }; Expression d = { {.op = REST}, &c, NULL }; Expression tree = { {.op = CONS}, &b, &d }; #endif

Test 2:

#ifndef _TEST_H_ #define _TEST_H_ #include #include "expressions.h" Expression a = { {.s = "!Hello world"}, NULL, NULL }; Expression b = { {.s = "!?"}, NULL, NULL }; Expression c = { {.op = FIRST}, &b, NULL }; Expression d = { {.op = CONS}, &a, &c }; Expression tree = { {.op = REST}, &d, NULL }; #endif

Test 3:

#ifndef _TEST_H_ #define _TEST_H_ #include #include "expressions.h" Expression a = { {.s = "ABCDEFGHIJKLM"}, NULL, NULL }; Expression b = { {.s = "MNOPQRSTUVWXYZ"}, NULL, NULL }; Expression c = { {.op = REST}, &b, NULL }; Expression d = { {.op = CONS}, &a, &c }; Expression tree = { {.op = FIRST}, &d, NULL }; #endif