Introduction
：
ptroy1projX.c ，
gcc ptroy1projX.c
a.out
：
./ a.out
：(pdf
( ( a a ) [ [ [ { [ x ] } ]]] )
：
)
：
–d ：
./ a.out –d
Requirement
CS211 – Programming Practicum Spring 2018
Programming Project 2
Due: Monday, 2/15/17 at 11:59 pm
Balanced Symbol Checker
For this lab, write a C program that will determine whether input is given with properly balanced
symbols. We will often use symbols together to specify the beginning and ending of an item, such as
the use of parentheses in a mathematic expression or the use of curly braces in a C, C++ or Java
program. For this program, we will be checking the following symbol pairs:
• parentheses: ( )
• curly braces: { }
• square brackets: [ ]
• angle brackets:
This program will require the use of a stack implemented in a dynamic array. This dynamic array is
to grow to a larger size when a push operation would be done to a full array causing an array
overflow. For this program, your dynamic array MUST start with 2 positions in the array. When the
array needs to grow, it size MUST grow by 2 additional positions each time (note the array to grow
in size from 2 to 4 to 6 to 8 to 10 to …).
The push operation is now defined as follows:
if (the stack array if full)
grow the array
add the value to the stack array
increment the top-of-stack value
The grow operation is defined as follows:
Allocate a new dynamic array of the larger size
Copy the existing values from the current stack array to the new dynamic array
Deallocate the current stack array
Have the stack array variable refer/point to the new dynamic array
Update the maximum stack size variable
Input
The input for this program will come from standard input. Each line of input will be a single
expression that is to be checked for balanced symbols. You may assume that each line of input is less
than 300 characters long. The program must loop to read in multiple lines of input. If the input on
the line contains only the letter q or Q, quit the program.
Since we have limited the length of the input and are trying to process one line of input at a time, the
best way to read the input is the fgets() function in the library. Since we are reading from
standard input, you are to use the value of stdin for the third parameter of fgets(). This causes fgets()
to read input from the standard input. You MUST use fgets() for this programming project to
read in the input. If you are not familiar with the fgets() functions, do a Google search and read.
The cplusplus.com website has a good reference page on fgets().
CS211 – Programming Practicum Spring 2018
Stack Use Algorithm
To check for balance symbols in an expression, the expression is inspected from left to right after the
entire line is read in.
When an opening symbol is encountered, this symbol is pushed onto the stack. The opening symbols
are: ( { [ and [ [ [ { [ x ] } ]]] )
Expression is balanced
( ( a a ) [ [ [ { [ x ] ]]] )
^ expecting }
( ( a a ) ) > [ [ [ { [ x ] } ]]] )
^ missing [ [ [ { [ x ] } ]]]
^ missing )
CS211 – Programming Practicum Spring 2018
Use of C struct and C functions
When writing your code, you MUST place all of the data items needed for the stack in a C struct
called “stack”. These data items must include the following (and may include others if needed).
the pointer to the dynamic array that actually holds the stack
the integer variable specifying the current size of the dynamic array
the integer variable specifying the top of the stack
The instance of this struct MUST be declared locally in main(). It may NOT be global. (Note: If you
want it to be declared locally in some other function other than main(), that is also OK.)
You MUST write functions for:
initializing the stack,
checking if the stack is empty,
pushing an element onto the stack,
popping an element off of the stack,
accessing the top element on the stack, and
resetting the stack so that it is empty and ready to be used again.
All of these functions MUST take as their first parameter a pointer to the struct that contains the
instance of the stack that is being used. The only exception to this is that the initializing function may
return a newly created instance and return a pointer to this instance.
Command Line Argument: Debug Mode
Your program is to be able to take one optional command line argument, the -d flag. When this flag
is given, your program is to run in “debug” mode. When in this mode, your program is to display a
message whenever an item is pushed or popped from the stack. This message must include the
character being pushed or popped. Also, when the stack grows, you are to explicitly state the old and
new size of the dynamic array as well as indicate the number of values copies from the current to the
new dynamic array.
When the flag is not given, this debugging information should not be displayed. One simple way to
set up a “debugging” mode is to use a boolean variable which is set to true when debugging mode is
turned on but false otherwise. This debugging mode variable can be set up as a global variable if
desired. Then using a simple if statement controls whether information should be output or not.
if ( debugMode == TRUE )
printf (“ Debugging Information \n”);
Program Submission
You are to submit the programs for this lab via the Information page in Blackboard.
To help the TA, name your file with your net-id and the assignment name, like:
• ptroy1projX.c
Where X is the number of the project assignment.