booleanEvaulation.c

#include  #include  #include  #include  #include "stack.h" #include "booleanEvaluation.h" #include "booleanWithError.h" /* printNames * input: none * output: none * * Prints names of the students who worked on this solution */ void printNames( ) { /* TODO : Fill in you and your partner's names (or N/A if you worked individually) */ printf("This solution was completed by: "); printf(" "); printf(" "); } /* evaluatePostfix * input: a postfix expression * output: T, F, or E * * Uses a stack to evaluates the postfix expression and returns the result as a string where "T" denotes true and "F" denotes false. * If the postfix expression is invalid it returns "E" to denote an error has occurred. */ char *evaluatePostfix( char *str ) { return booleanToString( ERROR ); } /* postfixToInfix * input: a postfix expression * output: the equivalent infix expression * * Uses a stack to convert str to its equivalent expression in infix. * You can assume that the postfix expression is valid */ char *postfixToInfix( char *str ) { return booleanToString( ERROR ); }

booleanEvaluation.h

#ifndef _booleanEvaluation_h #define _booleanEvaluation_h #include  #include  #include "stack.h" #include "booleanWithError.h" void printNames( ); char *evaluatePostfix( char *str ); char *postfixToInfix( char *str ); #endif

booleanWithError.c

#include "booleanWithError.h" /* strequals * input: two strings * output: boolean * * Returns ERROR if either of strings are NULL. * Returns TRUE if the strings are equal. * Returns FALSE if the strings are not equal. */ boolean strequals( char *str1, char *str2 ){ if( str1 == NULL || str2 == NULL ){ return ERROR; } return !strcmp( str1, str2 ); } /* strequals * input: a string * output: boolean * * Returns TRUE if the string is "T". * Returns FALSE if the string is "F". * Returns ERROR otherwise (including if the string is NULL). */ boolean stringToBoolean( char *str ){ boolean b; if( str==NULL ){ b = ERROR; } else if( strequals( str, "T" ) ){ b = TRUE; } else if( strequals( str, "F" ) ){ b = FALSE; } else{ b = ERROR; } return b; } /* booleanToString * input: a boolean * output: a string (this is malloc-ed so must be freed eventually!) * * Returns "T" if the boolean is TRUE. * Returns "F" if the boolean is FALSE. * Returns ERROR otherwise. */ char *booleanToString( boolean b ){ char *str = (char *)malloc( sizeof(char)*2 ); str[1] = '\0'; if( b == TRUE ){ str[0] = 'T'; } else if( b == FALSE ){ str[0] = 'F'; } else{ str[0] = 'E'; } return str; }

booleanWithError.h

#ifndef _booleanWithError_h #define _booleanWithError_h #include  #include  #include  typedef enum boolean { FALSE, TRUE, ERROR } boolean; boolean strequals( char *str1, char *str2 ); boolean stringToBoolean( char *str ); char *booleanToString( boolean b ); #endif

driver.c

#include  #include  #include  #include "stack.h" #include "booleanEvaluation.h" #define BUFFER_SIZE 100 const char DATA_FILE_NAME[] = "postfixTestData.txt"; const char PTI_FILE_NAME[] = "postfixToInfixTestData.txt"; void testFile( const char dataFile[], char *(*f)( char *)); void trimSpaceChars( char *buffer ); int main( int argc, char *argv[] ) { printf(" "); printNames( ); printf(" "); printf("Test evaluatePostfix: "); printf("---------------------- "); testFile( DATA_FILE_NAME, evaluatePostfix ); printf(" "); printf("Test postfixToInfix: "); printf("---------------------- "); testFile( PTI_FILE_NAME, postfixToInfix ); return 0; } /* testFile * input: name of input file, function to test * output: none * * Runs the specified function on inputs from the given file. * Prints whether the given function returns the correct value * This is the only function that prints in your program. */ void testFile( const char dataFile[], char *(*f)( char *)) { char *strcopy; char inputBuffer[BUFFER_SIZE] = ""; char solutionBuffer[BUFFER_SIZE] = ""; char *result; // Try to open the data file FILE *data = fopen( dataFile, "r" ); if( data==NULL ) { printf("Failed to open input file %s ", dataFile); exit(-1); } while( TRUE ) { // Read solution line if( fgets( solutionBuffer, 100, data )==NULL ) { break; } trimSpaceChars( solutionBuffer ); // Read line of operations if( fgets( inputBuffer, 100, data )==NULL ) { printf("File formatting incorrect "); break; } trimSpaceChars( inputBuffer ); strcopy = (char *)malloc( strlen(inputBuffer)+1 ); strcpy( strcopy, inputBuffer ); // process the boolean string result = f( strcopy ); // check if result = provided solution if( strcmp(solutionBuffer, result)==0 ) { printf("\"%s\" = %s Your solution is correct ", inputBuffer, solutionBuffer); } else { printf("\"%s\" Your solution is incorrect ", inputBuffer); printf("Expected %s but your function returned %s ", solutionBuffer, result); } free( result ); free( strcopy ); } fclose( data ); } /* trimSpaceChars * input: a string * output: none * * Removes leading and trailing white space characters for the string */ void trimSpaceChars( char *buffer ) { int i=0; int j=0; //skip leading white space while( isspace(buffer[i]) ) i++; while( i 
 
 
stack.c
 
#include "stack.h" /* * Default starting size for the stack */ int const STACK_STARTING_CAPACITY = 50; /* createStack * input: none * output: a pointer to a stack (this is malloc-ed so must be freed eventually!) * * Creates a new empty stack and returns a pointer to it. */ Stack *createStack( ){ Stack *ps = (Stack *)malloc( sizeof(Stack) ); ps->top = -1; ps->capacity = STACK_STARTING_CAPACITY; ps->data = (char **)malloc( sizeof(char *)*STACK_STARTING_CAPACITY ); return ps; } /* freeStack * input: a pointer to a stack * output: none * * frees the given stack pointer. Also call freeStackElements if you want to free every element in the stack. */ void freeStack( Stack *ps ){ free(ps->data); free(ps); } /* freeStackElements * input: a pointer to a stack * output: none * * pops and then frees all of the elements currently in the stack. Does not free the stack itself. Call freeStack to also free the stack. */ void freeStackElements( Stack *ps ){ while( isEmpty(ps) == FALSE ){ free( pop(ps) ); } } /* pop * input: a pointer to a stack * output: a string * * pops and returns the char* stored in the top element in the stack. It does not free the pop-ed element. */ char *pop( Stack *ps ){ if( isEmpty( ps ) ){ /* no element to return */ return NULL; } return ps->data[ ps->top-- ]; } /* push * input: a pointer to a stack, a string * output: none * * pushes the string onto the top of the given stack. */ void push( Stack *ps, char *str ){ if( isFull( ps ) ){ /* resize the array */ ps->capacity *= 2; ps->data = (char **)realloc( ps->data, ps->capacity*sizeof(char *) ); } ps->data[ ++ps->top ] = str; } /* top * input: a pointer to a stack * output: a string * * returns the string on top of the stack */ char *top( Stack *ps ){ if( isEmpty( ps ) ){ /* no element to return */ return NULL; } return ps->data[ ps->top ]; } /* isEmpty * input: a pointer to a stack * output: a boolean * * returns TRUE if the stack is empty and FALSE otherwise */ boolean isEmpty( Stack *ps ){ if( ps->top == -1 ){ return TRUE; } return FALSE; } /* isFull * input: a pointer to a stack * output: a boolean * * returns TRUE if the stack is at capacity currently and FALSE otherwise * Note that the stack handle resizing automatically so you do not need to ever run this as a user of stack. */ boolean isFull( Stack *ps ){ if( ps->capacity == ps->top+1 ){ return TRUE; } return FALSE; }
 
 
 
stack.h
 
 
 
#ifndef _stack_h #define _stack_h #include  #include "booleanWithError.h" typedef struct Stack { char **data; //string data stored in the stack int top; //index of the last element in the array int capacity; //current capacity of stack } Stack; Stack *createStack( ); void freeStack( Stack *ps ); void freeStackElements( Stack *ps ); char *pop( Stack *ps ); void push( Stack *ps, char *str ); char *top( Stack *ps ); boolean isEmpty( Stack *ps ); boolean isFull( Stack *ps ); #endif
 
 
 
POST FIX TEST DATA
 
F T NOT T F NOT T T T AND F T F AND F F T AND F F F AND F T T NAND T T F NAND T F T NAND T F F NAND T T T OR T T F OR T F T OR F F F OR F T T XOR T T F XOR T F T XOR F F F XOR F T T NOR F T F NOR F F T NOR T F F NOR T T T COND F T F COND T F T COND T F F COND T T T BICOND F T F BICOND F F T BICOND T F F BICOND E T T T T F AND T OR F T F AND T OR NOT E T F AND OR E T F T T AND OR T T F NOR T F NAND XOR F T F NOR T F NAND XOR T F AND T OR NOT BICOND
 
 
 
POST FIX TO IN FIX TEST DATA
 
( T NAND F ) T F NAND ( ( T AND F ) OR T ) T F AND T OR ( NOT ( ( T AND F ) OR T ) ) T F AND T OR NOT ( F COND ( T OR ( T XOR ( T NOR T ) ) ) ) F T T T T NOR XOR OR COND
  CS2124 Data Structures - Spring 2021 Assignment 2: Stacks Due 2/24/21 by 11:59pm Evaluate Postfix (10 points) Sketch of algorithm for evaluating a postfix string: (1) Create stack s. (2) For each token, s, in the postfix expression: 1 If x is Tor F push it into the stack 8. 2 Else if is a unary operator i If you do not have at least one operand in s, you should return an error in the boolean (remember to free your data). ii pop an operand, opl, from s iii compute & opl (see unary table) iv push the result into s v free opl and 2 3 Else if is a binary operator i If you do not have at least two operands in s, you should return an error in the boolean (remember to free your data) ii pop an operand, op2, from s iii pop an operand, opl, from s iv compute opl op2 = (see binary table) v push the result into s vi free opl, op2, and a (3) If s contains more than one operand after all of the tokens are evaluated you should return an error in the boolean. (4) Otherwise pop and return the only value in s. (5) Be sure to free all remaining malloced data before leaving the function (including when returning an error). Do not free the returned string. Operator Type Usage Calculation unary operator opl NOT binary operator binary operator binary operator binary operator binary operator binary operator opl op2 AND opl op2 NAND opl op2 OR opl op2 NOR opl op2 XOR opl op2 COND opl op2 BICOND lop1 opl && op2 !Topl && op2) opl || op2 !(opl || op2) opl != op2 Toplop2 binary operator opl == op2 Convert Infix to Postfix (10 points) Sketch of algorithm for converting a postfix strings to an infix strings: (1) Create stack s. (2) For each token, x, in the postfix expression: 1 If ris T or F push it into the stack s. 2 Else if x is a unary operator i pop an operand, opl, from s ii push the string "c opl)" into s iii free opl and 3 Else if x is a binary operator i pop an operand, op 2, from s ii pop an operand, opl, from s ili push the string "ople op2)" into s iv free opl, op2, and a (3) You assume that the postfix string is well formatted (feel free to imple- ment error checking if you would like). (4) pop and return the value in s. (5) Be sure to free all remaining malloced data before leaving the function (including when returning an error). Do not free the returned string. Hints for memory management:  Every string that you push into your stack should be malloced. Using the provided function "boolean ToString" from the file "boolean WithError.c" will make this easier. It also a couple other handy functions that you should consider using. . I would recommend not using "strtok" to tokenize your string (it will require significantly more work on your part). Instead you should use the "tokenizeString" we wrote in class. See the posted solution for Extra Practice Assignment #1. . You should free strings after popping them from your stack (be sure to use them before freeing them).  Operator tokens aren't pushed in the stack and can be freed immediately after usage. . Be sure to free all of your malloced data before returning. This included freeing your data in the case of an error. Deliverables: Your solution should be submitted as "boolean Evaluation.c", "boolean Evalu- ation.h", and "makefile". Also attach any additional files you create to solve this problem. Upload these files to Blackboard under Assignment 2. Do not zip your files. To receive full credit, your code must compile and execute. You should use valgrind to ensure that you do not have any memory leaks. Remember: The program you submit should be the work of only you and one other partner. Cheating will be reported to SCCS. Both the copier and copiee will be held responsible.  CS2124 Data Structures - Spring 2021 Assignment 2: Stacks Due 2/24/21 by 11:59pm Evaluate Postfix (10 points) Sketch of algorithm for evaluating a postfix string: (1) Create stack s. (2) For each token, s, in the postfix expression: 1 If x is Tor F push it into the stack 8. 2 Else if is a unary operator i If you do not have at least one operand in s, you should return an error in the boolean (remember to free your data). ii pop an operand, opl, from s iii compute & opl (see unary table) iv push the result into s v free opl and 2 3 Else if is a binary operator i If you do not have at least two operands in s, you should return an error in the boolean (remember to free your data) ii pop an operand, op2, from s iii pop an operand, opl, from s iv compute opl op2 = (see binary table) v push the result into s vi free opl, op2, and a (3) If s contains more than one operand after all of the tokens are evaluated you should return an error in the boolean. (4) Otherwise pop and return the only value in s. (5) Be sure to free all remaining malloced data before leaving the function (including when returning an error). Do not free the returned string. Operator Type Usage Calculation unary operator opl NOT binary operator binary operator binary operator binary operator binary operator binary operator opl op2 AND opl op2 NAND opl op2 OR opl op2 NOR opl op2 XOR opl op2 COND opl op2 BICOND lop1 opl && op2 !Topl && op2) opl || op2 !(opl || op2) opl != op2 Toplop2 binary operator opl == op2 Convert Infix to Postfix (10 points) Sketch of algorithm for converting a postfix strings to an infix strings: (1) Create stack s. (2) For each token, x, in the postfix expression: 1 If ris T or F push it into the stack s. 2 Else if x is a unary operator i pop an operand, opl, from s ii push the string "c opl)" into s iii free opl and 3 Else if x is a binary operator i pop an operand, op 2, from s ii pop an operand, opl, from s ili push the string "ople op2)" into s iv free opl, op2, and a (3) You assume that the postfix string is well formatted (feel free to imple- ment error checking if you would like). (4) pop and return the value in s. (5) Be sure to free all remaining malloced data before leaving the function (including when returning an error). Do not free the returned string. Hints for memory management:  Every string that you push into your stack should be malloced. Using the provided function "boolean ToString" from the file "boolean WithError.c" will make this easier. It also a couple other handy functions that you should consider using. . I would recommend not using "strtok" to tokenize your string (it will require significantly more work on your part). Instead you should use the "tokenizeString" we wrote in class. See the posted solution for Extra Practice Assignment #1. . You should free strings after popping them from your stack (be sure to use them before freeing them).  Operator tokens aren't pushed in the stack and can be freed immediately after usage. . Be sure to free all of your malloced data before returning. This included freeing your data in the case of an error. Deliverables: Your solution should be submitted as "boolean Evaluation.c", "boolean Evalu- ation.h", and "makefile". Also attach any additional files you create to solve this problem. Upload these files to Blackboard under Assignment 2. Do not zip your files. To receive full credit, your code must compile and execute. You should use valgrind to ensure that you do not have any memory leaks. Remember: The program you submit should be the work of only you and one other partner. Cheating will be reported to SCCS. Both the copier and copiee will be held responsible