Difference between revisions of "TADM2E 3.1"

Revision as of 02:47, 27 March 2015

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)

The approach below maintains a stack where the index of each opening '(' is pushed onto the stack. As each closing ')' is found, the index of the matching '(' is popped off the stack.

The string is unbalanced if there:

• is an attempt to pop an element off an empty stack. The position of the current character can be reported as the position of the first offending parenthesis.
• are any elements left on the stack. The value of the first element in the stack can be reported as the position of the first offending parenthesis.

#include <iostream>
#include <stack>
#include <string>

int main (int argc, char* argv[]) {
  if (argc != 2) {
    std::cout << "pass a string to check if it's parens are balanced" << std::endl;
    exit(1);
  }

  std::stack<int> parens;
  std::string input = argv[1];

  for (int i = 0; i < input.length(); i++) {
    char ch = input[i];
    if (ch == ')') {
      if (parens.size() == 0) {
        std::cout << "unmatched ')' at position: " << i << std::endl;
        exit(1);
      }
      parens.pop();
    }
    else if (ch == '(') {
      parens.push(i);
    }
  }
  if (parens.size() != 0) {
    while (parens.size() > 1) {
      parens.pop();
    }
    std::cout << "unmatched '(' at position: " << parens.top() << std::endl;
    exit(1);
  }
  else {
    std::cout << "parens balanced!" << std::endl;
  }
}

--Neonstalwart (talk) 22:47, 26 March 2015 (EDT)

Back to Data Structures Problems...