TADM2E 3.1

You just need to maintain a count, like so:

<pre>

   public static boolean isBalanced(String str) {
       int count = 0;

       for (int i = 0, n = str.length(); i < n; i++) {
           switch (str.charAt(i)) {
           case '(':
               count++;
               break;
           case ')':
               count--;
               break;
           default:
               throw new IllegalArgumentException();
           }

           if (count < 0) {
               System.out.println("Imbalance at index " + i);
               return false;
           }
       }

       if (count != 0) {
           System.out.println("Imbalance at index " + (str.length() - 1));
           return false;
       }

       return true;
   }

</pre>

Another Approach to use stack in-order to solve this problem;

  A. Read the string from left to right as CHR
  B. Keep pushing CHR until CHR is not ")"
  1) Pop from stack once CHR == ")"
         if poped element is NOT "("
            return FAlse
   Repeat A

--Max 07:18, 16 June 2010 (EDT)

Back to Data Structures Problems...