Write a C program called balanced.c. You must use an Array-Based implementation of a Stack, not a Reference-Based Implementation of a Stack.

Main objective: Determine whether any expression with multiple kinds of brackets, braces and parentheses is balanced using an Array-Based Stack. You must implement the stack directly yourselves. Using a ReferenceBased Stack, or a stack library, or JCF stacks, or a list ADT will earn no credit.

Types of brackets: There are four parenthesis/bracket pairs:

( and )

[ and ]

{ and }

< and >

A line may contain other characters (including spaces) besides these 8 characters, but those characters are ignored. An expression is balanced if all the open parentheses are closed by a matching close parentheses, and nested parenthesis match, so that (for example) you cant have ] closing {, or a stray extra ) when there isnt an open (.

For example, the following lines are all not valid (N):

ab(x]w

alpha{ beta

(([[Turing]])

The ( quick [ brown ( fox ( jumped ) over ) the ] lazy ) dog )

< { }

> html <

And the following lines are all valid (Y):

ab[x]w

alpha{ betadelta}

([[Turing]])

The ( quick [ brown ( fox ( jumped ) over ) the ] lazy ) dog

metamorphosis

< html >

( [ < { } > ] ) < < ( ) > >

You must implement your solution to Lab4 using an Array-Based Stack. Furthermore, you have to write your own stack from scratch. You cannot use any built-in libraries for stacks or linked lists, nor can you use an ADT for lists or a Reference-Based stack.

Your program balanced.c will take two command line arguments naming the input and output files respectively (following the FileIO.c example thats in Some_Helpful_Background_on_C.pdf). It will read in each line in the input file, then print a separate line in the output file for each line in the input file. If the input line is valid (that is, balanced), then the output line should be the single character Y; if the input line is invalid (that is, not balanced), then the output line should be the single character N. You may assume that there arent more than 80 characters on any input line; this is important, since youre using an Array-Based implementation of Stacks.

Your program should contain functions corresponding to the usual stack interface (createStack, push, pop, isEmpty, peek and popall). Place the definition of these functions after all preprocessor directives but before the function main(). C requires that the signature of a function be known before the first call to the function. Recall that the signature is the name of the function, along with its return type and the type and number of the formal parameters. See Charlie McDowells C for Java Programmers book (Section 2.1, Declaring Functions) for two approaches showing how to declare functions before using them.

The function definition should take the form of (). Your main function will have some similarities to the FileIO.c example provided in Some_Helpful_Background_on_C.pdf, except that the while loop should contain appropriate calls to the stack functions. You cannot use built-in libraries for stacks or linked lists to do this assignment. You must write the functions yourself, using an Array-Based Stack.

One function in the library string.h that you will find useful is strlen(), which returns the length of its string argument. For example the following program prints out the length of a string entered on the command line.

/* * charCount.c * prints the number of characters in a string on the command line */

#include

#include

#include

int main(int argc, char* argv[ ]) {

if(argc<2){

printf("Usage: %s some-string ", argv[0]);

exit(EXIT_FAILURE);

}

printf("%s contains %d characters ", argv[1], strlen(argv[1]) );

return EXIT_SUCCESS;

}

Remember that a string in C is a char array, not a separate data type as it is in Java. (This may help you write your Stack implementation in C.) Recall also that arrays in C cannot be queried as to their length. How then does strlen() work? Actually a string in C is a little bit more than a char array. By convention C strings are terminated by the null character '\0'. This character acts as a sentinel, telling the functions in string.h where the end of the string is. Function strlen() returns the number of characters in its char* (char array) argument up to (but not including) the null character.

Also recall that arrays in C are passed by reference, not by value. An array name in C is literally the address of (i.e. a pointer to) the first element in the array. Arrays, strings, and pointer variables in C will be discussed in subsequent lab assignments.

To test balanced with specific input and output files, you may have to enter:

./balanced input_file output_file

unless your PATH already includes the current directory (.)

Write a Makefile that creates an executable binary file called balanced, and includes a clean utility.

input file:

b(x]w alpha{ beta (([[Turing]]) The ( quick [ brown ( fox ( jumped ) over ) the ] lazy ) dog ) < { } > html < ab[x]w alpha{ betadelta} ([[Turing]]) The ( quick [ brown ( fox ( jumped ) over ) the ] lazy ) dog metamorphosis < html > ( [ < { } > ] ) < < ( ) > >

Output File:

NNNNNNYYYYYYY