CSC 15 Lab 8


Checking for matching (), {} and [] using a Stack data structure.

A stack is a list (array) of values with a "top of the stack" value.
We add and delete values from the same end of the stack (in contrast to
a "queue").  Adding an element is called "push" and deleting is called 
"pop".  The last value we pushed onto the stack will be first value
popped.  This is called "LIFO" as in last-in-first-out behavior.

Say you have an expression such as ((3-4)*(4-1)) - we know the
parentheses all match - i.e., that this is a "well formed expression".
We can use a stack to verify this as follows:

  * Every time we see a left parenthesis '(', we push it on to a stack.
  * Every time we see a right parenthesis ')', we pop a '(' off the stack.
  * All other symbols are ignored.
  * If at the end of the string the stack becomes empty, that means 
      all parentheses have been matched.

On the other hand, if the at the end of the string there are still ('s
on the stack, that means we read an expression like ((5+4)-1, i.e.,
there's a ( that was not matched by a right parenthesis.

Similarly, if we had a string with an unmatched right parenthesis like
"(3+4))-1" that means when we read the extra ')', there will be no
corresponding '(' on the stack to pop: we can't pop an empty stack.

In Python, we can use an array/list for a stack:

   Stack = []   # empty stack
   Stack.append('[')  # "pushes" '[' on top of the stack.
   x = Stack.pop(len(Stack)-1)  # destructively deletes last element of stack

The pop operation also returns what was previously on the top of the stack.
To examine the top of the stack without deleting you can just look at
Stack[len(Stack)-1].
       
If we only had ( and ), then it is in fact possible to write the same
program using a simple counter.  However, the stack technique can be
extended to match not just ()'s but also []'s and {}'s.  The
algorithm is similar - when we see a left (, [, or { we push it onto
the stack.  When we see a right ), ], or }, we check the top of the
stack, if there's a corresponding (, [, or {, we pop, otherwise, we
know that there's a mismatch.

For example, with the string "[y=(x+4])", we will detect a mismatch
when we look at the ], because what's on the stack is not a [ but a (.


The following hash table or "association list" can be useful:

   Expect = {']':'[', ')':'(', '}':'{'}

That is, if the next input character is ']', then you should "expect" to
see '[' on the top of the stack.  You should pop the stack, and if it is
not what's expected (or if the stack is empty), then you have found an error.

In summary, there are three types of errors that you should detect:

  1. unmatched right delimiter: example (3+4)].  This error occurs when
     you see a right delimiter, ')', ']' or '}', but the stack is empty.
  2. mismatched delimiter.  example (()].  This error occurs when you
     see a right delimiter but the top-of-stack holds a left-delimiter
     of the wrong type.
  3. unmatched left delimiter: example [(3+x).  The error is detected only
     when you've reached the end of the input string, but the stack is
     not empty (no everything was popped).


######## It is recommended that you write this program in two parts:  #####

1. First write a version that stops as soon as it finds one error.  The 
   ouput of your program should be something like:

       Enter a string:  (3+4)
       All delimiters match
       Enter a string: 3-4)
       Unmatched )
       Enter a stirng: 3+(4-5]
       Mismatched ( and ]
       Enter a stirng: (3
       Unmatched (

   Your program can stop once the first error is detected.
       

PART II:
  Once you get that working, modify your program to detect more
errors, and output more information.  We need to know where the error
occurred.  Your program should record the indices of the errors.  To
do this, you should push on the stack not just a char like '[' but
also the index at which it occured.  You can push a tuple, for
example:

   Stack.append('[',3)
   x,i = Stack.pop(len(Stack)-1)

will assign x to '[' and i to 3.

(alternatively, pushing 3 is enough because given the index you can always
 find the corresponding character)

You should also try to catch more than one error, and provide as much help 
as possible to the user as to where the errors occured.  The output of 
better program should be similar to the following:

([)]}
^^^^^
21123
3 errors found:
1: mismatched [ and )
2: mismatched ( and ]
3: unmatched }

The output indicates that there are three errors and where the errors occured.

You should displayed detailed information for the first 9 errors.

Hint: to do this part, I suggest you separate your program into two
stages (two separate functions).  The first stage/function should find
all the errors and put them in an array.  The array should hold pairs
of indices (i,k) indicating where a mismatch occured.  The second
stage constructs all the strings that need to be printed from the
error information from the first stage.  You can record an error with
a pair (tuple of numbers).  For example (3,6) can indicate a mismatch
between the char at index 3 and the char at index 6.  (-1,3) can indicate
an unmatched right delimiter at index 3, (4,-1) can indicate an
unmatched left delimiter at index 4.  Collect all such error
information into an array and pass it to the second stage of your
program.


########## additional programming hint:

You can make python take "command line" arguments with

import sys  # at the top.

s = sys.argv[1]  # assign string s to first command line argument.

sys.argv is an array containing the name of the program at index 0, followed
by command-line arguments (as strings).  With this technique you can 
provide input to your program as you start it.  For example, I typed

  python match.py "([)]}"

to test the program.


######## Try your program with (at least) the following strings:

e1 = "[[{{[[{{}}]]}}]]{{[[{(())}]]}}{}{{{{}}}}[[[]]]"  # no errors
e2 = "{({[([{({{({{}})}})})]})}"  # errors exist

I will also test it with my own cases.