booleanEvaluation.c

#include

#include

#include

#include

#include "stack.h"

#include "booleanEvaluation.h"

#include "booleanWithError.h"

/* 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.*/

TODO

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*/

TODO

char *postfixToInfix( char *str )

{

return booleanToString( ERROR );

}

booleanEvaluation.h

#ifndef _booleanEvaluation_h

#define _booleanEvaluation_h

#include

#include

#include "stack.h"

#include "booleanWithError.h"

char *evaluatePostfix( char *str );

char *postfixToInfix( char *str );

#endif

Including files

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

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;

}

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(" ");

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

{

// Replace the newline with a null char

if( buffer[i]==' ' )

{

buffer[j]='\0';

break;

}

buffer[j] = buffer[i];

i++;

j++;

}

j--;

//truncate trailing white space

while( isspace(buffer[j]) )

j--;

buffer[j+1]='\0';}

postfixTestData.txt

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

postfixToInfixTestData.txt

( 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

Evaluate Postfix (10 points) Sketch of algorithm for evaluating postfix strings: (1) Create stack s. (2) For each token, x, in the postfix expression: 1 If x is 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 compute x opl (see unary table below) iii push the result into s 3 Else if x is a binary operator i pop an operand, op2, from s ii pop an operand, op1, from s iii compute opl op2 x iv push the result into s (3) If you do not have enough operands in s to perform an operation you should return an error in the boolean. (4) Likewise, if s contains more than one operand after all of the tokens are evaluated you should return an error in the boolean. (5) Otherwise pop and return the only value in s. Unary operations: opl NOT !op1 Binary operations: opl op2 AND opl op2 NAND opl op 2 OR opl && op2 !(op1 && op2) opl || op 2 opl op2 NOR opl op2 XOR opl op2 COND opl op2 BICOND !(opl || op2) opl ! = op2 !opl || op2 opl == op2 Convert Infix to Postfix (10 points) Sketch of algorithm for converting postfix strings to infix strings: (1) Create stack s. (2) For each token, x, in the postfix expression: 1 If x is T or F push it into the stack s. 2 Else if x is a unary operator i pop an operand, op1, from s ii push the string "(op1 x)" into s 3 Else if x is a binary operator i pop an operand, op2, from s ii pop an operand, op1, from s iii push the string "(opl x op2) into s (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. Hints for memory management: Every string that you push into your stack should be malloc-ed. You should free strings after popping them (be sure to use them before freeing them). Operator tokens will be freed after usage since they are not put into the stack. Evaluate Postfix (10 points) Sketch of algorithm for evaluating postfix strings: (1) Create stack s. (2) For each token, x, in the postfix expression: 1 If x is 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 compute x opl (see unary table below) iii push the result into s 3 Else if x is a binary operator i pop an operand, op2, from s ii pop an operand, op1, from s iii compute opl op2 x iv push the result into s (3) If you do not have enough operands in s to perform an operation you should return an error in the boolean. (4) Likewise, if s contains more than one operand after all of the tokens are evaluated you should return an error in the boolean. (5) Otherwise pop and return the only value in s. Unary operations: opl NOT !op1 Binary operations: opl op2 AND opl op2 NAND opl op 2 OR opl && op2 !(op1 && op2) opl || op 2 opl op2 NOR opl op2 XOR opl op2 COND opl op2 BICOND !(opl || op2) opl ! = op2 !opl || op2 opl == op2 Convert Infix to Postfix (10 points) Sketch of algorithm for converting postfix strings to infix strings: (1) Create stack s. (2) For each token, x, in the postfix expression: 1 If x is T or F push it into the stack s. 2 Else if x is a unary operator i pop an operand, op1, from s ii push the string "(op1 x)" into s 3 Else if x is a binary operator i pop an operand, op2, from s ii pop an operand, op1, from s iii push the string "(opl x op2) into s (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. Hints for memory management: Every string that you push into your stack should be malloc-ed. You should free strings after popping them (be sure to use them before freeing them). Operator tokens will be freed after usage since they are not put into the stack