LAB 4 -- Implementing a stack for parentheses matching

In this lab you will design implement a stack on top of a linked list, and solve the so-called parentheses matching problem using it. Make sure that you understand the workings of a linked list. Although it is easy to modify the code in the previous lecture notes to suit the purpose of this lab, we recommend implementing your linked list from scratch.

Description of the problem

You may be wondering how the C++ compiler parses your text ( and makes sense of it). In this lab you will get a flavor of this, by solving a much less complicated yet similar problem.

Consider an arithmetic expression (or a C++ program) that contains parentheses, '(' and ')' . Ignoring all other characters in the text, you can still decide if all parentheses are correctly matched. Here are a few examples:

   ( )               --  correct
   ( ( ) )           --  correct
   ( ( ) ) ( )       --  correct
   ( ( ( ) ) ( ) )   --  correct
   ( ) )             --  incorrect (closed paren with no open paren)
   ) (               --  incorrect
   ( ( ) ) ) (       --  incorrect

As you can see, the number of open and closed parens being equal does not guarantee that the parens are matching.

The situation can be worse if there are two kinds of parens that should be matching in a program, such as '{', '}' and '(', ')'. The situation when these parenthesis are weirdly mismatched in a C++ program must be a familiar one :-) . A few examples:

  { ( ) }           -- correct
  { ( { } ) () }    -- correct
  { ( } )           -- incorrect
  ( ( { ) } )       -- incorrect

Clearly, separately matching the kinds of parentheses does not guarantee the correctness of the overall structure - observe that in third example both braces and parens are matched if we ignore the other kind. Also notice that we can put as many matched parens as we like around that example, and that still won't make it correct.

An algorithm that checks whether the matching in a given text is correct is as follows:

  0. Create an empty stack S.
  1. While( there are characters left ){
  2.   Read a character ch. 
  3.   If is ch an opening paren (of any kind), push it onto S
  4.   Else 
  5.      If  ch  is a closing paren (of any kind), look at the top of S.
  6.        If S is empty as this point, report failure. 
  7.        If the top of S is the opening paren that corresponds to c,
            then pop S and continue to 1, this paren matches OK.
  8.        Else report failure.  
  9. If at the end of input the stack S is not empty, return failure.
     Else return success.

The failure reported on line 6 is due to finding a closing paren without any preceding opening paren that might correspond to it. On line 8 it is due to mismatches like { ( } ), and on line 9 it is due to having more opening parens of some kind than closing ones.

Task I

Implement this algorithm for matching parens of one kind, '(', ')'. Read the text to be matched from a file, and ignore any other characters in it except '(', ')'. That way you can check correctness of a LISP program. Since a user usually wants to know exactly where the mismatch occured, print out that information for him.

Task II

Implement this algorithm for matching parens of two kinds, '(', ')' and '{', '}'. Read the text from a file. That way you can check parentheses matching in a C++ program. Print some useful diagnostics in case of failure.

Task III (extra credit)

In many programming languages strings are delimited by quotes " ". Any parens that appear inside the quotes must be ignored for meaningful parentheses matching check. Make you program ignore the contents of strings when checking the matching. Thus, the following is legal:

main(){
  cout << " :-) " ; 
}

Reminder: reading characters from a file

The following program reads a file and counts the number of opening and closing parens '(', ')' in it. As we saw, this is by far not enough to check the matching, so treat the following code is intended to merely refresh your memory of standard libraries.

#include <iostream.h>
#include <fstream.h>
#include <stdlib.h>   // for exit(..)

int main(){
  ifstream f;
  f.open( "test1.txt" );

  if( ! f ){
    cout << "Error opening file. Quitting.\n";
    exit(-1);
  }

  int open_count = 0;
  int close_count = 0;
  int line_count = 0;

  char ch;
  while( f.get( ch ) ){    // fills ch with the next char from file,
                           // returns false if the end of file (EOF) 
                           // is reached
    if( ch == '(' ) 
      open_count++;
    else if( ch == ')' )
      close_count++;
    else if( ch == '\n' )
      line_count++;
  }   
  
  cout << open_count << " of ) ,  \n";   
  cout << close_count << " of ( , \n";
  cout << line_count  << " lines. \n";
    
  return 0;
}