Skip to content

update BalancedBrackets #1029

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Merged
merged 1 commit into from
Oct 13, 2019
Merged

update BalancedBrackets #1029

Changes from all commits
Commits
Show all changes
1 commit
Select commit
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
96 changes: 46 additions & 50 deletions DataStructures/Stacks/BalancedBrackets.java
View file
Open in desktop
Original file line number Diff line number Diff line change
@@ -1,10 +1,8 @@
package data_structures.Stacks;
package DataStructures.Stacks;

import java.util.Scanner;
import java.util.Stack;

/**
*
* The nested brackets problem is a problem that determines if a sequence of
* brackets are properly nested. A sequence of brackets s is considered properly
* nested if any of the following conditions are true: - s is empty - s has the
Expand All @@ -15,71 +13,69 @@
* returns true if S is nested and false otherwise.
*
* @author akshay sharma
* @date: 2017-10-17
* @author <a href="https://github.com/khalil2535">khalil2535<a>
*
* @author shellhub
*/
class BalancedBrackets {

/**
* Check if {@code leftBracket} and {@code rightBracket} is paired or not
*
* @param leftBracket left bracket
* @param rightBracket right bracket
* @return {@code true} if {@code leftBracket} and {@code rightBracket} is paired,
* otherwise {@code false}
*/
public static boolean isPaired(char leftBracket, char rightBracket) {
char[][] pairedBrackets = {
{'(', ')'},
{'[', ']'},
{'{', '}'},
{'<', '>'}
};
for (char[] pairedBracket : pairedBrackets) {
if (pairedBracket[0] == leftBracket && pairedBracket[1] == rightBracket) {
return true;
}
}
return false;
}

/**
* Check if {@code brackets} is balanced
*
* @param s
* @return
* @param brackets the brackets
* @return {@code true} if {@code brackets} is balanced, otherwise {@code false}
*/
static boolean is_balanced(String s) {
public static boolean isBalanced(String brackets) {
if (brackets == null) {
throw new IllegalArgumentException("brackets is null");
}
Stack<Character> bracketsStack = new Stack<>();
char[] text = s.toCharArray();
for (char x : text) {
switch (x) {
case '{':
case '<':
for (char bracket : brackets.toCharArray()) {
switch (bracket) {
case '(':
case '[':
bracketsStack.push(x);
case '{':
bracketsStack.push(bracket);
break;
case '}':
if (!bracketsStack.empty() && bracketsStack.pop() == '{') {
break;
} else {
return false;
}
case '>':
if (!bracketsStack.empty() && bracketsStack.pop() == '<') {
break;
} else {
return false;
}
case ')':
if (!bracketsStack.empty() && bracketsStack.pop() == '(') {
break;
} else {
return false;
}
case ']':
if (!bracketsStack.empty() && bracketsStack.pop() == '[') {
break;
} else {
case '}':
if (!(!bracketsStack.isEmpty() && isPaired(bracketsStack.pop(), bracket))) {
return false;
}
break;
default: /* other character is invalid */
return false;
}
}
return bracketsStack.empty();
return bracketsStack.isEmpty();
}

/**
*
* @param args
* @TODO remove main method and Test using JUnit or other methodology
*/
public static void main(String args[]) {
try (Scanner in = new Scanner(System.in)) {
System.out.println("Enter sequence of brackets: ");
String s = in.nextLine();
if (is_balanced(s)) {
System.out.println(s + " is balanced");
} else {
System.out.println(s + " ain't balanced");
}
}

public static void main(String[] args) {
assert isBalanced("[()]{}{[()()]()}");
assert !isBalanced("[(])");
}
}