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