Difference between revisions of "TADM2E 3.1"

Revision as of 03:14, 28 August 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)

Max's first example above appears to incorrectly report the last character in the string as the offending index if there is a surplus of opening parentheses. The following solution (in JavaScript) takes a similar approach, but correctly reports the index of the first unmatched open parenthesis (more like Neonstalwart's solution, but without requiring a stack).

This function returns a number: -1 if balanced, otherwise the index of the first offending parenthesis.

function checkParens(str) {
	var numOpen = 0;
	var length = str.length;
	var offender;

	for (var i = 0; i < length; i++) {
		if (str[i] === '(') {
			if (!numOpen) {
				// Store index of first open paren in case it is never closed
				offender = i;
			}
			numOpen++;
		}
		else if (str[i] === ')') {
			if (!numOpen) {
				// Closing paren with none open = instant fail
				return i;
			}
			numOpen--;
		}
	}

	return numOpen === 0 ? -1 : offender;
}

Back to Data Structures Problems...