In this project, we will implement the stack data structure and use it to compute the answer to infix equations. We will do this by using a stack to convert the infix equation to a postfix equation, and then we will use a stack to evaluate the postfix equation.

Files provided in the project:

1. stack.h. This file does not need to be changed, but you should understand its contents. This file contains structure definitions and the prototypes for the following stack functions:
   1. Stack newStack(int maximumStackSize). Malloc a new StackImp, malloc an array of Elements of size maximumStackSize (store the address in stackElements pointer), set maxSize to be maximumStackSize, initialize count to be 0, and return a pointer to the StackImp.
   2. void freeStack(Stack s). Free the array inside the StackImp and then free the memory allocated for the stack s.
   3. void push(Stack s, Element e). Given a Stack and an Element, push the element onto the stack and increment the count. Print an error message if the stack was already full.
   4. Element pop(Stack s). Given a stack s, remove the top element from the stack, decrement count, and return its value.
   5. int isEmpty(Stack s). Given a stack, return true (1) if it is empty and return false (0) otherwis
   6. Element topElement(Stack s). Given a stack, return the value of the element that is on top of the stack (without removing it).

2) stack.c. In this file, you should provide the function definitions for each of the stack functions listed above.

3. p1Input.txt This file contains some example infix equations for your code to solve. Each equation contains at least one of 4 operations: addition, subtraction, multiplication, and division with the corresponding symbols: +, -, *, /. You can assume that each operand is a single-digit integer (0 9) and that division is integer division (so any fractional portion is dropped, e.g., 5 / 2 = 2). There may or may not be parentheses in the equation. Note that this is just a sample input file. When we grade your programs, we will use different equations (same format). Feel free to modify this file to test your program.

4. p1Output.txt The output you should be generating for p1Input.txt.

5) abc123Project1.c You should rename this file to use your own abc123 prior to submitting on Blackboard. This file contains the main function. Note that you do not need to modify main, only the two functions after main. You can modify main if youd like to, but it is not necessary for this project. Inside of main, there is code that will open the p1Input.txt file, and it reads the file one line at a time until it reaches the end of the file. The line is stored as a null-terminated character array named infixString. We then pass this string to the first function that you are to implement:

int convertToPostfix(char *infixString, char *postfixString)

In this function, you are given pointers to two strings as input. The first one, infixString, is the infix equation that we just read from the file in main. The second one, postfixString, is an array where you should write the converted postfix string. The function returns an integer depending on if there are any errors that occurred in the formatting of the infix string. See function header in the file for more details. For full credit, your program should detect errors in the parentheses in the infix equation. For extra credit, your program should detect missing operators and missing operands.

When the function returns to main, we check to see if there was an error in the infix string. If there was an error, we print an error message and move onto the next infix string. If there was no error, then we pass your string in postfix representation to the second function that you are to implement:

int evaluatePostfix(char *postfixString)

In this function, we take as input your string variable containing the equation in postfix form, and we evaluate it. The function returns an integer containing the computed value of the equation.

6) Makefile. Update the makefile to reflect your abc123. You can implement your code however you like, however before submitting ensure your project compiles on the fox servers using this makefile. If it does not compile using the makefile then you will get 0 points! You can compile using the commandmake and you can execute your program using ./project1.

abc123Project file:

#include "Stack.h"

#define MAX_LINE_LENGTH 50

int convertToPostfix(char *infixString, char *postfixString); int evaluatePostfix(char *postfixString);

int main() { FILE *inputFile; inputFile = fopen("p1Input.txt", "r"); if(inputFile == NULL){

perror("Error opening file"); return -1; }

//This string will hold the infix equations that are read from inputFile, one at a time. char infixString[MAX_LINE_LENGTH];

//Use fgets to read the next line from the inputFile. //Store the line into infixString. //The while loop repeats until there are no more lines in the file. while(fgets(infixString, MAX_LINE_LENGTH, inputFile)!=NULL){

//If the line is blank, skip it. if(infixString[0] == ' ') continue;

printf("Current infix string: %s",infixString);

//postfixString is a string to store the equation from szInfixString converted into postfix. char postfixString[MAX_LINE_LENGTH];

//Call the convertToPostfix function (that you are to implement below main). int returnMessage = convertToPostfix(infixString,postfixString);

//convertToPostfix should return an integer letting us know if the infix string was in a valid format. //If the format is valid (we returned 0), then we call the evalutaePostfix function (that you are to implement below), and print the result of the evalution. //If the format is not valid (we returned something other than 0), then we print the corresponding error message. switch(returnMessage) {

case 0: //0 means the infix string had no errors. Go ahead and evaluate the postfix string. printf("Postfix string: %s ",postfixString); int result = evaluatePostfix(postfixString); printf("It evaluates to %d. ",result); break; case 1: //1 means the infix string is missing a left parenthesis. printf("WARNING: Missing left parenthesis. "); break; case 2: //2 means the infix string is missing a right parenthesis. printf("WARNING: Missing right parenthesis. "); break; case 3: // 3 means missing operator. printf("WARNING: Missing operator. "); break; case 4: //4 means missing operand. printf("WARNING: Missing operand. "); break; default: printf("WARNING: %d. ", returnMessage);

}

printf(" "); }

fclose(inputFile);

return 0; }

/******* int convertToPostfix(char *infixString, char *postfixString)

Input: infixString is a character array of length <= MAX_LINE_LENGTH that contains an equation in infix format. postfixString is a currently empty character array of length <= MAX_LINE_LENGTH that we should fill with a postfix representation of infixString.

Output: We return an integer based on any errors found in infixString. If there are no errors, return 0. If there is a missing (, return 1. If there is a missing ), return 2. If there is a missing operator, return 3 (for extra credit). If there is a missing operand, return 4 (for extra credit). *********/ int convertToPostfix(char *infixString, char *postfixString){

}

/************ evaluatePostfix(char *postfixString)

Input: postfixString is a string of length <= MAX_LINE_LENGTH that contains an equation in postfix representation. If your convertToPostfix() function is correct, this string should be in a valid postfix format.

Output: Return an integer representing what the postfix equation evaluated to. ************/ int evaluatePostfix(char *postfixString){

}

stack.h file:

/**************************** Stack.h

Purpose: Struct definition of a Stack. Define the function protoypes used by Stacks. *************************/

#include #include

//We want two different types of stacks in our program. //When converting infix to postfix, we want a stack to store operators and parenthesis (characters). //When evaluating a postfix string, we want a stack to store operands (integers). //Therefore we are defining an Element to be the union of a char and int, and we can define our Stack to be a Stack of Elements. typedef union{ int operand; char operation; } Element;

//Defining the a struct for a Stack Implementation. typedef struct { //The maximum size of the stack. int maxSize; //The number of elements currently in the stack. int count; //Pointer to an array of Elements to store data in the stack. Element *stackElements; } StackImp;

//Defining a Stack to be a StackImp Pointer. typedef StackImp *Stack;

/*****FUNCTION PROTOTYPES**********/

//Malloc a new StackImp, malloc an array of Elements of size maximumStackSize (store the address in stackElements pointer), set maxSize to be maximumStackSize, initialize count to be 0, and return a pointer to the StackImp. Stack newStack(int maximumStackSize);

//Free stackElements and then free the Stack s. void freeStack(Stack s);

//Push a new Element e onto the Stack s, and increment the count variable. Print an error message if the stack was already full. void push(Stack s, Element e);

//Pop an element off the stack, decrement the count variable, and return the element's value. Element pop(Stack s);

//Return true (1) if stack is empty and false (0) otherwise. int isEmpty(Stack s);

//Return the value of the top element of the stack (without removing it). Element topElement(Stack s);

p1input.txt file:

5 + 3 8 * 2 - 1 9 / 3 + 2 * 8 + 3 4 * ( 2 - 7 ) + 3 ( 3 * 6 2 - 5 / 2 ) ) 1 + 2 ( * 8 6 2

make file:

# Define the machine object files for your program OBJECTS = wel501Project1.o Stack.o # Define your include file INCLUDES = Stack.h

# make for the executable project1: ${OBJECTS} gcc -g -o project1 ${OBJECTS}

# Simple suffix rules for the .o %.o: %.c ${INCLUDES} gcc -g -c $<

# Clean the .o files clean: rm -f ${OBJECTS}