Homework 4: Balanced Parentheses

Purpose

This programming assignment is designed to give you practice in creating and using stacks to solve a problem. It will also give you the opportunity to practice using arrays or linked lists (your choice) as well as handling input from the keyboard.

Problem Description

This program should read a complex mathematical expression from the keyboard (i.e. from stdin) and analyze it to determine if the parentheses in the expression are balanced. In other words, your program should check that for every "(" in the expression, there is a corresponding ")". If the number of "(" and ")" are equal, then the expression is correctly parenthesized. If they are not equal, then there is a mismatch, and the expression is incorrectly parenthesized.

This program could be also used to check program files such as those used in Scheme. With some changes, it can also be used to check a C program file to determine if the "{" and "}" braces are appropriately balanced.

Since this homework assignment is intended to give practice in using a stack implementation, your solution MUST include a stack and implement the following functions:

Input

Your program should print a message to the user, indicating what type of input is expected. Then, it should read in a single line of input that contains a mathematical expression such as:

(a + b) * (c - d) / (f * 5) = y

You may assume that the length of the expression will not be greater than 50 characters (including spaces).

You should not assume that the expression will contain ANY parentheses and check for that possibility in your testing.

Expected Output

Your program should repeat back the expression as entered by the user and include a message informing the user whether or not the expression is correctly parenthesized. Such as:

The parentheses in: (a + b) * (c - d) / (f * 5) = y are correctly balanced.

or, if they are not balanced ....

The parentheses in: (a + b) * (c - d / (f * 5) = y are NOT balanced.

If the expression did not contain any parentheses, you should print a message to that effect, such as:

The expression: e = mc^2 does not contain parentheses.

Testing

Testing should include a plan for how you intend to verify that the program is working correctly as well as test cases that might "break" your code:

Remember that these are the MINIMUM tests you should do.

Grading

This homework programming assignment will make use of the general grading form for program style. Points may be deducted for poor programming style. You must also follow the information on the class style guide.

Additonally:

No global variables are allowed. Submissions that do not compile (for any reason) will receive a zero, and re-submissions will be graded as late (-10% per day). We compile using the clang compiler on MathLAN to compile and test your submissions, and any submission that seg faults on valid input will be penalized 20%. Any submission that does not include BOTH a hard copy (signed) submitted in class and your digital copy sent on time to the grader account (csc161-02-grader@grinnell.edu) will be penalized 10%.

Additionally, these specific criteria will be used to grade this assignment, which is worth 25 points.

Main Program (15 points)

Testing and Development (10 points)