Assignment 1: Problem Solving Example

First, the easy parts

Let's start with some ideas:

Clearly, it's unbalanced if there are more of one kind of parentheses (say, left) than the other kind (say, right).
In a balanced set of parentheses, every right parenthesis corresponds to a unique left one. There's no ambiguity or choice about this. If we could identify pairs and check them off, and there are no pairs left, we're done.

Counting is easy. We could count the number of left parentheses, and then separately count the number of right parentheses.

Suppose we wrote one method for each task:

    static int countLeftParens ( ...) 
    {
    }

    static int countRightParens ( ...) 
    {
    }

At this point, let's not worry about the parameters (is it a string? array of chars?). We could then write code like:

    static int countLeftParens ( ...) 
    {
    }

    static int countRightParens ( ...) 
    {
    }

Then, we can use this

    static boolean checkBalanced (String s)
    {
        int numLeft = countLeftParens ( ... )
        int numRight = countRightParens ( ... )
        if (numLeft != numRight) {
            // Not balanced
        }
    }

If there are equal number, then we can set about seeing if they are actually well-formed.

At this point, we could go ahead and fill in some detail, then implement and test the above methods. But let's pause for a moment and ask ... do we really need two separate methods?

Here's a more compact approach:

    static boolean checkBalanced (String s)
    {
        char[] letters = s.toCharArray ();
        int numLeft = countChar (letters, '(')
        int numRight = countChar (letters, ')')

        System.out.println ("numLeft=" + numLeft + " numRight=" + numRight);
        if (numLeft != numRight) {
            // Not balanced
	    return false;
        }
    } 

    static int countChar (char[] letters, char c)
    {
    }

We've outlined a more general purpose "look for a particular char and count its occurences" method that we use twice, one with the left paren and once with the right paren.

Note:

We've now defined the parameters more precisely.
The string is converted into a char array. Although we could have written the method using charAt() method of string, the array will prove useful later.
Even though we don't need to print the values of numLeft and numRight we should do so as pro-active debugging. That is, we include various println's to make sure we get our expected results. (We can take them out later.)

A1.2 Exercise: Write the code that should go into the method countChar() above. Then, include all the 5 test strings from the previous page in main() and test that the counts are correct.

The one hard part

OK, so now if the counts are correct, what's next?

Let's try and match the parens. For example, with

    String s = "(a(bc)d)(e)f"

we could try and look for its match:

    String s = "(a(bc)d)(e)f"

But how do we know how many parens in between to skip over? What if we had

    String s = "(a(()()bc)d)(e)f"

Now for a key insight: let's find the first right parens (the leftmost right parens):

    String s = "(a(bc)d)(e)f"

and then go leftwards to find its match.

    String s = "(a(bc)d)(e)f"

There are no other parens in between!

What do we do when we find it? We can erase both, in effect marking the pair as matched:

    String s = "(a_bc_d)(e)f"

Since we eliminated the matched pair, we simply repeat the exact same process. If there are no more parens left at the end, it's balanced. Otherwise, we have mismatched parens.

Let's flesh this out with a method:

    static int findFirstRight (char[] letters)
    {
         // return -1 if not found.
    }

A1.3 Exercise: Write the code that should go into the method above and test it.

Now, let's outline the approach:

    static boolean checkBalanced (String s)
    {
        char[] letters = s.toCharArray ();
        int numLeft = countChar (letters, '(')
        int numRight = countChar (letters, ')')

        System.out.println ("numLeft=" + numLeft + " numRight=" + numRight);
        if (numLeft != numRight) {
            // Not balanced
	    return false;
        }
 
        int k = findFirstRight (letters);
        while (k >= 0) {
            // k is the location of the leftmost right-paren
            //** print k here

            // We now go left from here to locate its match:
            int n = findFirstLeft (letters, k-1);

            //** print n here

            if (n < 0) {
                // None found, so it's unbalanced.
                return false;
            }
            else {
                // Matched pair: left at n, right at k
                letters[n] = ' ';
                letters[k] = ' ';
            }

            //** print letters here

            // Proceed by repeating.
            k = findFirstRight (letters);
        }

    }

And that's our complete algorithm!

Yes, it's a bit more complex than what we're used to.

To understand it, first work it out by hand for a few examples.

A1.4 Exercise: In A1.4.pdf trace out, step by step, the above approach for this example string: "(((a(()()))d)(e)f)".

Next, notice that we've inserted some println's. This is essential defensive programming: add copious println's as you code so that you can catch an error early. It's much harder to catch errors after your code has become complex and gnarly. Once your program is working, go back and comment out the println's.

A1.5 Exercise: Put all the pieces together into ParensTest.java to complete the exercise.

A1.6 Audio:

Back to the assignment