Comp 271 lab 6 - using a stack
Goals
- using a stack
- language parsing
- unit testing
Overview
In class we discussed my simple parentheses-balance-checker, at balancer.zip.
When we encountered a '(', we pushed it onto a Stack<Character>.
When we encountered a ')', we popped the matching '(' from the stack.
If the stack was empty when it shouldn't have been, or nonempty when it
should have been, there was an error.
For parentheses alone, there was a simpler algorithm: start at 0,
increment for each '(', and decrement for each ')'. If we ever get a
negative value, or if the value at the end is not 0, there's an error.
But now let's add '{}' and '[]' to the list of possible grouping
characters. How can we tell when a string with all three kinds of
grouping symbols is balanced? This time, we need
the stack. Each time we encounter an opening symbol '({[', we push it.
Each time we encounter a closer ')}]', we pop from the stack and verify
that what was just popped "matches" (in the left-right sense) the
closing symbol we just encountered.
I have created some unit tests
for the parentheses-only case. You are to add appropriate unit tests
for the mixed-groupers situation. Note that in the parentheses-only
case, it was not possible for a popped character to fail to be a
LPAREN; in the mixed case it can be. You should test for this (eg
"([)]"); note that this is a negative test (ie the result is supposed to be false). You should create positive tests too, though the negative tests are probably more important.
To submit your project, create a zipfile and email it to me at
pld@cs.luc.edu.