Question
Input:
There are two input files: course data and queries. See cs2123p2Driver.c for more information.
Read the infix expressions
Convert the infix to postfix
Evaluate the postfix expression, producing an array of booleans (one entry for each course).
Print the infix expression, the postfix form of the expression, and evaluated result. The driver does this.
Approaches for Evaluating Operators
Approach #1: Iterate over the list of courses and then evaluate the query for each course. The operator evaluation result is simply true or false (since only one course is considered).
For N courses, this approach evaluates the same query N times.
The operator result (i.e., a boolean) must be stacked.
Additional functions provided:
void printQueryResult(Course courseM[], int iNumCourse, QueryResult resultM[])
Prints the courses which have a corresponding element in the resultM array turned on.
int never(Course *pCourse, Attr attr)
Determines whether a course has a particular attribute (type and value). If it doesn't, never returns TRUE; otherwise, it returns FALSE.
int getCourseData(Course courseM[])
Gets course data and their corresponding attributes (type and values).
Use of union
Since the evaluation needs two types of elements, we will use union as shown in the include file.
Some Files for your use:
p2Query.txt - data file containing infix expressions which are evaluated as queries
p2Course.txt - course data file similar to program #0.
cs2123p2.h - include file for Program #2
cs2123p2Driver.c - driver program that I provided. It has several useful routines to help reduce your effort. Please review this code
Your coding:
Create your code in cs2123p2.c (not cs2123p2Driver.c). Based on what the driver calls, you need to create these functions:
int convertToPostFix(char *pszInfix, Out out)
It returns 0 if it converted successfully. Otherwise, it returns a value which indicates an error in
the infix data (e.g., missing left paren, missing right paren)
It populates the out array using the addOut function (provided in the driver).
void printCourseData(Course courseM[], int iNumCourse)
This was done in program #0.
void evaluatePostfix(PostfixOut out, Course courseM[], int iNumCourse
, QueryResult resultM[])
This evaluates a postfix expression (which is in out) using the courseM array. For each course satisfying the posftfix query,
it sets its corresponding position in resultM to TRUE.
int atLeastOne(Course *pCourse, Attr attr)
Determines whether a course has a particular attribute (type and value). If it does, atLeastOne returns TRUE; otherwise, it returns FALSE.
int only(Course *pCourse, Attr attr)
This looks at EACH attribute in the course's attrM array for the specified course. If the attribute's szAttrType matches the specified szAttrType, then its corresponding szAttrValue must match the specfied attribute value. If it doesn't match the attribute value, FALSE is returned. only examines each of the attributes for the specified course.
You will also have to provide code for AND and OR.
Requirements:
You should not have to modify cs2123p2Driver.c.
Make certain you free up allocated memory (e.g., stack).
Sample Output (partial):
ID Course Name
Attr Value
CS1083 Intro I
LANG JAVA
PROF ROBBINS
PROF HOLLAND
PROF SHERETTE
PROF ROBINSON
PROF ZHU
RECIT N
DEPT CS
MAT2233 Discrete Math
PREREQ MAT1214
PREREQ CS1713
PROF SHERETTE
PROF TANG
RECIT N
DEPT MAT
MAT3333 Math Found
PREREQ MAT1223
PREREQ CS1713
PROF SHERETTE
PROF TANG
RECIT N
DEPT MAT
CS1713 Intro II
PREREQ CS1083
LANG C
PROF CLARK
PROF HOLLAND
PROF SHERETTE
PROF ROBINSON
PROF ZHU
RECIT Y
DEPT CS
CS2123 Data Structures
PREREQ CS1713
LANG C
PROF CLARK
PROF SHERETTE
PROF ROBINSON
PROF KORKMAZ
PROF TOSUN
RECIT Y
DEPT CS
CS3843 Comp Org
PREREQ CS2123
LANG C
LANG IA32
PROF CLARK
PROF TIAN
PROF MUZAHID
RECIT Y
DEPT CS
CS3723 Pgm Lang
PREREQ CS3443
PREREQ MAT2233
LANG C
LANG CPP
LANG JAVA
LANG LISP
LANG PYTHON
PROF CLARK
RECIT N
DEPT CS
CS3423 Sys Pgm
PREREQ CS2123
PROF MAYNARD
PROF LAMA
PROF CLARK
LANG C
LANG PERL
LANG BASH
RECIT Y
DEPT CS
CS3443 App Pgm
PREREQ CS2123
PROF BYLANDER
PROF ROBINSON
PROF NIU
RECIT N
DEPT CS
LANG JAVA
CS4713 Compiler
PREREQ CS3723
PREREQ CS3843
PROF CLARK
RECIT N
DEPT CS
LANG JAVA
CS3343 Anlys of Algo
PREREQ CS2123
PREREQ MAT3333
PREREQ MAT2233
PROF SHERETTE
PROF GIBSON
PROF BYLANDER
RECIT Y
DEPT CS
LANG JAVA
Query # 1: RECIT = N
RECIT N =
Query Result:
ID Course Name
CS1083 Intro I
MAT2233 Discrete Math
MAT3333 Math Found
CS3723 Pgm Lang
CS3443 App Pgm
CS4713 Compiler
Query # 2: RECIT = Y
RECIT Y =
Query Result:
ID Course Name
CS1713 Intro II
CS2123 Data Structures
CS3843 Comp Org
CS3423 Sys Pgm
CS3343 Anlys of Algo
Query # 3: PROF = CLARK
PROF CLARK =
Query Result:
ID Course Name
CS1713 Intro II
CS2123 Data Structures
CS3843 Comp Org
CS3723 Pgm Lang
CS3423 Sys Pgm
CS4713 Compiler
Query # 4: PROF NEVER CLARK
PROF CLARK NEVER
Query Result:
ID Course Name
CS1083 Intro I
MAT2233 Discrete Math
MAT3333 Math Found
CS3443 App Pgm
CS3343 Anlys of Algo
Query # 5: PROF ONLY CLARK
PROF CLARK ONLY
Query Result:
ID Course Name
CS3723 Pgm Lang
CS4713 Compiler
Query # 6: PROF = CLARK AND RECIT = N
PROF CLARK = RECIT N = AND
Query Result:
ID Course Name
CS3723 Pgm Lang
CS4713 Compiler
Input files
p2Course.txt
p2Query.txt
Explanation / Answer
#include #include #include #include #include "cs2123p2.h" // The following structure is used by the categorize function to help // categorize tokens and provide the precedence. static struct { char szSymbol[MAX_TOKEN + 1]; // token symbol such as "(" int iCategory; // CAT_OPERATOR, CAT_OPERAND, CAT_LPAREN or CAT_RPAREN int iPrecedence; // 0 - lowest precedence, 3 - highest precedence } symbolDefM[] = { {"(", CAT_LPAREN, 0} , {")", CAT_RPAREN, 0} , {"=", CAT_OPERATOR, 2} , {"NEVER", CAT_OPERATOR, 2} , {"ONLY", CAT_OPERATOR, 2} , {"AND", CAT_OPERATOR, 1} , {"OR", CAT_OPERATOR, 1} , {"", 0, 0} }; // Stack implementation using arrays. You are not required to document these. void push(Stack stack, Element value) { if (stack->iCount >= MAX_STACK_ELEM) ErrExit(ERR_STACK_USAGE , "Attempt to PUSH more than %d values on the array stack" , MAX_STACK_ELEM); stack->stackElementM[stack->iCount] = value; stack->iCount++; } Element pop(Stack stack) { if (isEmpty(stack)) ErrExit(ERR_STACK_USAGE , "Attempt to POP an empty array stack"); stack->iCount--; return stack->stackElementM[stack->iCount]; } Element topElement(Stack stack) { if (isEmpty(stack)) ErrExit(ERR_STACK_USAGE , "Attempt to examine topElement of an empty array stack"); return stack->stackElementM[stack->iCount-1]; // return the top } int isEmpty(Stack stack) { return stack->iCount iCount = 0; return stack; } void freeStack(Stack stack) { free (stack); } // File pointers for the course file and the query file FILE *pFileCourse; // Used with the -c Course File FILE *pFileQuery; // Used with the -q Query File // Main program for the driver int main(int argc, char *argv[]) { Course courseM[MAX_COURSE]; // Course array int iNumberOfCourses = 0; // Number of courses char *pszCourseFileNm = NULL; // Pointer to an argv[] for course file name char *pszQueryFileNm = NULL; // Pointer to an argv[] for query file name // get the file names from the command argument switches processCommandSwitches(argc, argv, &pszCourseFileNm, &pszQueryFileNm); // Open the Course File if a file name was provided if (pszCourseFileNm == NULL) exitUsage(USAGE_ERR, ERR_MISSING_SWITCH, "-c"); pFileCourse = fopen(pszCourseFileNm, "r"); if (pFileCourse == NULL) exitUsage(USAGE_ERR, "Invalid course file name, found " , pszCourseFileNm); // Open the Query file if a file name was provided if (pszQueryFileNm == NULL) exitUsage(USAGE_ERR, ERR_MISSING_SWITCH, "-q"); pFileQuery = fopen(pszQueryFileNm, "r"); if (pFileQuery == NULL) exitUsage(USAGE_ERR, "Invalid query file name, found " , pszQueryFileNm); // get and print the course data including attributes iNumberOfCourses = getCourseData(courseM); fclose(pFileCourse); printCourseData(courseM, iNumberOfCourses); // Read and process the queries readAndProcessQueries(courseM, iNumberOfCourses); fclose(pFileQuery); printf(" "); fclose(stdout); return 0; } /******************** readAndProcessQueries ************************************** void readAndProcessQueries(Course courseM[], int iNumberOfCourses) Purpose: Reads queries from the Query File, converts them to postfix (via convertToPostfix), evaluates the postfix (via evaluatePostfix), and shows the courses that satisified the queries (via printQueryResult). Parameters: i Course courseM[] array of courses and attributes i int iNumCourse number of courses in courseM Notes: - References the global: pFileQuery **************************************************************************/ void readAndProcessQueries(Course courseM[], int iNumberOfCourses) { // Allocate the memory for the postfix result PostfixOut postfixOut = malloc(sizeof(PostfixOutImp)); // array (which corresponds to courseM via subscript) of booleans // showing which courses satisfied a query QueryResult queryResultM[MAX_COURSE]; char szInputBuffer[100]; // entire input line int rc; int iLineCount = 0; // read text lines containing expressions until EOF while (fgets(szInputBuffer, 100, pFileQuery) != NULL) { iLineCount++; // Ignore the line if it only contains a linefeed if (szInputBuffer[0] == ' ') continue; printf("Query # %d: %s", iLineCount, szInputBuffer); postfixOut->iPostfixOutCount = 0; // reset out to empty // Invoke the student's convertToPostfix function rc = convertToPostfix(szInputBuffer, postfixOut); switch (rc) { case 0: // ok so print the postfix and evaluate it printPostfixOut(postfixOut); evaluatePostfix(postfixOut, courseM, iNumberOfCourses, queryResultM); printQueryResult(courseM, iNumberOfCourses, queryResultM); break; case WARN_MISSING_LPAREN: printf(" Warning: missing left parenthesis "); break; case WARN_MISSING_RPAREN: printf(" Warning: missing right parenthesis "); break; case WARN_MISSING_OPERATOR: printf(" Warning: missing operator "); break; case WARN_MISSING_OPERAND: printf(" Warning: missing operand "); break; default: printf(" warning = %d ", rc); } } printf(" "); free(postfixOut); } /******************** printQueryResult ************************************** void printQueryResult(Course courseM[], int iNumCourse, QueryResult resultM[]) Purpose: Prints the courses which have a corresponding element in the resultM array turned ON. Parameters: i Course courseM[] array of courses and attributes i int iNumCourse number of courses in courseM i QueryResult resultM[] array (which corresponds to courseM bia subscript) of booleans showing which courses satisfied a query Notes: **************************************************************************/ void printQueryResult(Course courseM[], int iNumCourse, QueryResult resultM[]) { int i; printf(" Query Result: "); printf(" %-7s %-20s ", "ID", "Course Name"); // Loop through each course for (i = 0; i