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:

• `void push(char)`
• `void pop()` or `char pop()`

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:

• Test an expression that does not include any parentheses
• Test an expression that contains multiple, balanced sets of parentheses
• Test at least one expression that contains nested parentheses such as

((a - b) + 1) * (c / (e + f)) = x

• Test an expression that has unbalanced parentheses

Remember that these are the MINIMUM tests you should do.

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.

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)

• User Prompts [2 points]
• Starts the program with a brief explanation of what the program will do
• Prompts the user for input with guidance on the expected format
• Input Processing [4 points]
• Reads the expression from standard input
• Pushes "(" onto the stack
• Pops the top of the stack when ")" encountered
• Saves all the input characters into a string or other data structure to use in the output message
• Output [5 points]
• "Error" message when expression entered without any parentheses
• Gracefully fails if user enters an empty expression
• Repeats the input exactly as entered
• Correctly indicates if an expression is properly parenthesized
• Correctly indicates if an expression is NOT properly parenthsized
• Stack Implementation [4 points]
• Implements `push(char)`
• Implements `pop()`
• Uses an array or linked list to store input
• Implements a function to test if the stack is empty when the input has been processed (such as `top()` or `isEmpty()`)

Testing and Development (10 points)

• Functions give clear and complete pre- and post-conditions
• Test plan describes the possible problem situations
• Transcript records actual test runs
• Tests compare test cases to expected outcomes
• Summary at the end of the transcript explains why the program is correct