CSCI 3342 Submission 08
Checking for Balanced Symbols

Supplied file(s) $sup08/demo_bs_checker (the demo executable)
$sup08/bs_checker.txt (the TextItems file)
$sup08/sample_files.zip (a zip file of sample input files)
$sup08/demo_bs_checker_with_trace
$sup08/bs_checker_with_trace.txt
(a version of the executable which includes a tracing feature
that you do not have to implement, but which may be a
helpful reference during the development of your solution)
Files to submit bs_checker.cpp (your source code)
bs_checker (your executable)
my_tests.sh (your testing script)
Where to put them Copy them to the submissions/s08 folder in your uxx account.
When they're due Sunday, March 23, 2025 @11:59pm

Overview

This week you will develop a simplified "balanced symbol checker". That is, you will develop a simplified "utility" program that analyzes a file of text (a C++ or Java program, for example, but not necessarily) to see if each left parenthesis has a corresponding right parenthesis (and similarly for square and curly brackets) and to ensure that all symbols are properly nested if there is any nesting.

This is only a simplified checker because we assume that comments and quoted strings do not contain any single unmatched such symbols. This would not cause a C++ compiler any problem, as you know, but it would cause our program to report a problem where there isn't any when analyzing C++ or Java source code.

Also, for simplicity, we do not include the symbols < and > in our balance checking, since that would require additional programming to deal with things like the extraction and insertion operators (>> and <<) and the inequality symbols (<, >, <=, >=), in which those symbols do not appear in "balanced pairs".

Steps to Perform

  1. Download the sample executable and run it, first without any command-line parameters. This will show you the opening screen and the on-line program description, which consists of three screens of information that you should read carefully.
  2. Next, run the program with one command-line parameter which is the name of a non-existent file, and observe the behavior of the program in this case.
  3. We have provided a sample_files.zip containing both "good" and "bad" sample input files (that is files containing balanced symbols and files containing unbalanced symbols). However, it will be much better if you now create a few test input files of your own, perhaps even before looking at the provided sample input files. Experiment with your own sample input files to make the symbols we are checking both "unbalanced" and "balanced". Run the sample executable with your revised input file in each case.
  4. Continue this experimentation, with your own as well as the supplied sample files, until you thoroughly understand the problem of unbalanced symbols, and the behavior of this program in detecting and reporting the problem. You may also find it helpful to run the "enhanced" version of the program containing the tracing feature, with any or all of the sample input files.
  5. Write pseudocode for a solution of this problem and revise it until you are convinced that a program that implements your pseudocode will be the one you want.
  6. Translate your pseudocode into C++. Note that you are supplied with a "textitem" file (bs_checker.txt) which your program must access and display in the usual way.
  7. Continue testing your program until you are convinced it works correctly.
  8. Make a final check to ensure your source code is identified, formatted, and documented properly.
  9. Finally, submit the required files by copying them to the appropriate subdirectory in your uxx account.

Additional Notes, Requirements, Specifications and/or Hints (if any)

  1. Work some short paper-and-pencil examples (perhaps consisting only of the symbols we are checking) to get a feel for the difference between "balanced" and "unbalanced" in this context.
  2. Development of this program provides an even better opportunity than usual to hone your "incremental development skills". For example, you can begin by ignoring file input and just test a single string for "balance". You can also limit your testing for balance to parentheses only (ignoring square brackets and braces) until you get that working. And so on ...
  3. Here is a list of the various messages displayed by the program: 
    Could not open file filename.ext.
Program now terminating.

The file has matching symbols.

? at index ? on line ? does not match ? at index ? on line ?.

? at index ? on line ? is missing the corresponding open symbol.

? at index ? on line ? has no matching close symbol.

The file has unmatched symbols.
  4. And here is a big hint: I think you might find it very helpful to use a struct that contains three fields: a char field to hold a symbol of the kind you're looking for, and two int fields for the line number and position on the line where that symbol was found. Then have a stack of these structs, onto which you push each "left symbol" (and its info) that you see, and when you see the matching "right symbol" you pop off of the stack the struct with the corresponding "left symbol" . If you have all matching symbol pairs, this will give you an empty stack at the end; otherwise something is wrong, either along the way or at the end, and your program must recognize and report whatever has gone wrong.
  5. You may find it helpful to run the "enhanced" executable that has a tracing feature that shows you what is being pushed onto and popped off of the stack of symbols as a file is being examined for matching symbols. That version of the program behaves exactly like the other one, except if you add a lowercase t as a second command-line input, the tracing feature is activated and the tracing output is displayed.