TADM2E 3.1

From Algorithm Wiki
Revision as of 18:22, 11 September 2014 by Algowikiadmin (Talk | contribs)

Jump to: navigation, search

You just need to maintain a count, like so:

    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;
    }

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