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 more than 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.


######## 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 out
   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]
       Unmatched ( and ]
       

2. Once you get that working, modify your program to 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.

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.

If there are more than 9 errors, you can just output something that says that
there are too many errors to display accurately.

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 a data structure.  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 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