TADM2E 3.1 - Revision history

Matt: Undo revision 772 by FuckYou (talk)

2020-07-23T14:40:50Z

Undo revision 772 by FuckYou (talk)

FuckYou: Replaced content with "We are Anonymous"

2020-07-14T01:41:11Z

Replaced content with "We are Anonymous"

CnEY: Forgot to add signature on last edit

2015-08-28T03:15:12Z

Forgot to add signature on last edit

CnEY: Add JS count-based solution with correct index reporting

2015-08-28T03:14:34Z

Add JS count-based solution with correct index reporting

Neonstalwart: add a full example including reporting the position of the first offending parenthesis

2015-03-27T02:47:35Z

add a full example including reporting the position of the first offending parenthesis

Algowikiadmin: Recovering wiki

2014-09-11T18:22:22Z

Recovering wiki

Algowikiadmin: Recovering wiki

2014-09-11T18:13:04Z

Recovering wiki

New page

You just need to maintain a count, like so:

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

[[Data-structures-TADM2E|Back to ''Data Structures'' Problems]]...

← Older revision		Revision as of 14:40, 23 July 2020
Line 1:		Line 1:
−	We are ~~Anonymous~~	+	You just need to maintain a count, like so:
		+
		+	<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]]...

← Older revision		Revision as of 01:41, 14 July 2020
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]]...~~

@@ Line 88: / Line 88: @@
 </pre>
 --[[User:Neonstalwart|Neonstalwart]] ([[User talk:Neonstalwart|talk]]) 22:47, 26 March 2015 (EDT)
 [[Data-structures-TADM2E|Back to ''Data Structures'' Problems]]...

← Older revision		Revision as of 02:47, 27 March 2015
Line 42:		Line 42:
	--[[User:Max\|Max]] 07:18, 16 June 2010 (EDT)		--[[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)

	[[Data-structures-TADM2E\|Back to ''Data Structures'' Problems]]...		[[Data-structures-TADM2E\|Back to ''Data Structures'' Problems]]...

@@ Line 1: / Line 1: @@
 You just need to maintain a count, like so:
-&lt;pre&gt;
+<pre>
      public static boolean isBalanced(String str) {
          int count = 0;
-         for (int i = 0, n = str.length(); i &lt; n; i++) {
+         for (int i = 0, n = str.length(); i < n; i++) {
              switch (str.charAt(i)) {
              case '(':
@@ Line 17: / Line 17: @@
+             }
-             if (count &lt; 0) {
+             if (count < 0) {
-                 System.out.println(&quot;Imbalance at index &quot; + i);
+                 System.out.println("Imbalance at index " + i);
                  return false;
+             }
@@ Line 24: / Line 24: @@
          if (count != 0) {
-             System.out.println(&quot;Imbalance at index &quot; + (str.length() - 1));
+             System.out.println("Imbalance at index " + (str.length() - 1));
              return false;
+         }
@@ Line 30: / Line 30: @@
          return true;
+     }
-&lt;/pre&gt;
+</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 &quot;)&quot;
+    B. Keep pushing CHR until CHR is not ")"
-) Pop from stack once CHR == &quot;)&quot;
+) Pop from stack once CHR == ")"
-           if poped element is NOT &quot;(&quot;
+           if poped element is NOT "("
               return FAlse
      Repeat A