TWiki> CS211 Web>CS211Lab8F12 (2012-10-24, Main.troy)EditAttach

CS 211 - Fall 2012

Lab 8

Due: Monday, October 29, 2012

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 anding of an item, such as the use of paratheses 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:

  • parantheses: ( )
  • curly braces: { }
  • square brackets: [ ]
  • angle brackets: < >
This program will require the use of a stack like the stack calculator; however, this program MUST use a dynamic array to hold the stack. 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 is to start with 2 positions in the array. When the array needs to grow, it size is to grow by 2 additional positions.

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.

Since the only input we really care about are the 8 characters that form the 4 symbol pairs, any other input on the line can be ignored.

Stack Use Algorithm

To check for balance symbols in an expression, the expression is read from left to right.

When an opening symbol is encountered, this symbol is pushed onto the stack. The opening symbols are: ( { [ and <.

When a closing symbol is encountered, check the symbol at the top of the stack.

If the symbol on the top of the stack is the corresponding opening symbol, pop the stack and continue.

If the symbol on the top of the stack is NOT the correspoding opening symbol (or the stack is stack is empty), the expression is NOT balanced.

When the end of the expression is encountered (i.e. the end of the input line), check to see if the stack is empty.
If the stack is empty, then the expression was balanced.

If the stack is NOT empty, the the expression was not balanced.

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 the values currently in the stack in proper order. Also, when the stack grows, you are to explicitly state the old and new size of the dynamic array as well as incidate the number of values copies from the current tot he 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. Then usig a simple if statement controls whether information should be output.

if ( debugMode == TRUE )

printf (" Debugging Information \n");

Program Submission

Your are to submit the programs for this lab via the Assignments Page in Blackboard.

To help the TA, name your file with your net-id and the assignment name, like:

  • ptroy1LabX.c

Submit this file via the Assignment Link for the Lab in Blackboard.

  1. In the CS 211 Web Pages in Blackboard, go to the Assignments Page
  2. Click on the link for the correct lab. This will open a web page with the title: "Upload Assignment: Lab X", where X is the number of the lab
  3. Scroll down and click on the button "Browse for Local File"
  4. Select the file that you created that contains the program. Then click OK.
  5. Repeat steps 3 and 4 for your second program.
  6. Click the submit button on the "Upload Assignment: Lab X" page.
  7. You should see the Submission History page that shows what you submitted. Verify you actually submitted the correct information.

Check out the following code regarding simple creation of a dynamic array

Suggested Program Template Layout

/* stack function signatures */

void push (char ** stack, int *tos, int *length, int val);

void pop (int *tos);

int top (char * stack, int tos);

int topAndPop (char* stack, int *tos);

int isFull (int tos, int length); /* note returns a boolean value */ int isEmpty (int tos); /* note returns a boolean value */

int main (int argc, char ** argv)

{

char *stack;

int length;

int tos;

...

}

-- Main.troy - 2012-10-24

Topic attachments
I Attachment Action Size Date Who Comment
C source code filec dynArr.c manage 1.1 K 2012-10-24 - 14:07 UnknownUser  
Topic revision: r2 - 2012-10-24 - 17:02:35 - Main.troy
 
Copyright 2016 The Board of Trustees
of the University of Illinois.webmaster@cs.uic.edu
WISEST
Helping Women Faculty Advance
Funded by NSF