Difference between revisions of "TADM2E 3.1"

From Algorithm Wiki
Jump to: navigation, search
(Forgot to add signature on last edit)
(Replaced content with "We are Anonymous")
Line 1: Line 1:
You just need to maintain a count, like so:
+
We are Anonymous
 
+
<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
+
--[[User:Max|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.
+
<pre>
+
#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;
+
  }
+
}
+
</pre>
+
--[[User:Neonstalwart|Neonstalwart]] ([[User talk: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.
+
 
+
<pre>
+
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;
+
}
+
</pre>
+
--[[User:CnEY|CnEY]] ([[User talk:CnEY|talk]]) 23:15, 27 August 2015 (EDT)
+
 
+
[[Data-structures-TADM2E|Back to ''Data Structures'' Problems]]...
+

Revision as of 01:41, 14 July 2020

We are Anonymous