Parenthesis/Brackets Matching using Stack algorithm
27
For example if the parenthesis/brackets is matching in the following:
({})
(()){}()
()
and so on but if the parenthesis/brackets is not matching it should return false, eg:
{}
({}(
){})
(()
and so on. Can you please check this code? Thanks in advance.
public static boolean isParenthesisMatch(String str) {
Stack<Character> stack = new Stack<Character>();
char c;
for(int i=0; i < str.length(); i++) {
c = str.charAt(i);
if(c == '{')
return false;
if(c == '(')
stack.push(c);
if(c == '{') {
stack.push(c);
if(c == '}')
if(stack.empty())
return false;
else if(stack.peek() == '{')
stack.pop();
}
else if(c == ')')
if(stack.empty())
return false;
else if(stack.peek() == '(')
stack.pop();
else
return false;
}
return stack.empty();
}
public static void main(String args) {
String str = "({})";
System.out.println(Weekly12.parenthesisOtherMatching(str));
}
java stack push pop parentheses
edited Oct 31 '13 at 17:21
pinckerman
3,48352538
asked Jun 1 '13 at 15:17
Shuvo0o
1891416
|
show 15 more comments
27
For example if the parenthesis/brackets is matching in the following:
({})
(()){}()
()
and so on but if the parenthesis/brackets is not matching it should return false, eg:
{}
({}(
){})
(()
and so on. Can you please check this code? Thanks in advance.
public static boolean isParenthesisMatch(String str) {
Stack<Character> stack = new Stack<Character>();
char c;
for(int i=0; i < str.length(); i++) {
c = str.charAt(i);
if(c == '{')
return false;
if(c == '(')
stack.push(c);
if(c == '{') {
stack.push(c);
if(c == '}')
if(stack.empty())
return false;
else if(stack.peek() == '{')
stack.pop();
}
else if(c == ')')
if(stack.empty())
return false;
else if(stack.peek() == '(')
stack.pop();
else
return false;
}
return stack.empty();
}
public static void main(String args) {
String str = "({})";
System.out.println(Weekly12.parenthesisOtherMatching(str));
}
java stack push pop parentheses
edited Oct 31 '13 at 17:21
pinckerman
3,48352538
asked Jun 1 '13 at 15:17
Shuvo0o
1891416
You say "parens" but you also seem to want to check brackets...
– fge
Jun 1 '13 at 15:18
1
what's so special about java here?
– SMA
Apr 1 '15 at 16:54
7
Question. Is[ { ] }a valid matching?
– Kevin
Apr 1 '15 at 17:07
3
Without a language specification (i.e. a precise answer to the question "according to which rules are the expressions you want to parse being formed") we can't answer this. Are they a context free language? They definitely aren't regular due to the parentheses alone. Are they context-sensitive? Turing-complete? Regardless of all that, this question should be on CS.SE
– G. Bach
Apr 1 '15 at 17:45
1
Or you could write a real parser instead of abusing regex.
– cpburnz
Apr 2 '15 at 19:12
|
show 15 more comments
27
27
27
25
For example if the parenthesis/brackets is matching in the following:
({})
(()){}()
()
and so on but if the parenthesis/brackets is not matching it should return false, eg:
{}
({}(
){})
(()
and so on. Can you please check this code? Thanks in advance.
public static boolean isParenthesisMatch(String str) {
Stack<Character> stack = new Stack<Character>();
char c;
for(int i=0; i < str.length(); i++) {
c = str.charAt(i);
if(c == '{')
return false;
if(c == '(')
stack.push(c);
if(c == '{') {
stack.push(c);
if(c == '}')
if(stack.empty())
return false;
else if(stack.peek() == '{')
stack.pop();
}
else if(c == ')')
if(stack.empty())
return false;
else if(stack.peek() == '(')
stack.pop();
else
return false;
}
return stack.empty();
}
public static void main(String args) {
String str = "({})";
System.out.println(Weekly12.parenthesisOtherMatching(str));
}
java stack push pop parentheses
edited Oct 31 '13 at 17:21
pinckerman
3,48352538
asked Jun 1 '13 at 15:17
Shuvo0o
1891416
For example if the parenthesis/brackets is matching in the following:
({})
(()){}()
()
and so on but if the parenthesis/brackets is not matching it should return false, eg:
{}
({}(
){})
(()
and so on. Can you please check this code? Thanks in advance.
public static boolean isParenthesisMatch(String str) {
Stack<Character> stack = new Stack<Character>();
char c;
for(int i=0; i < str.length(); i++) {
c = str.charAt(i);
if(c == '{')
return false;
if(c == '(')
stack.push(c);
if(c == '{') {
stack.push(c);
if(c == '}')
if(stack.empty())
return false;
else if(stack.peek() == '{')
stack.pop();
}
else if(c == ')')
if(stack.empty())
return false;
else if(stack.peek() == '(')
stack.pop();
else
return false;
}
return stack.empty();
}
public static void main(String args) {
String str = "({})";
System.out.println(Weekly12.parenthesisOtherMatching(str));
}
java stack push pop parentheses
java stack push pop parentheses
edited Oct 31 '13 at 17:21
pinckerman
3,48352538
asked Jun 1 '13 at 15:17
Shuvo0o
1891416
edited Oct 31 '13 at 17:21
pinckerman
3,48352538
asked Jun 1 '13 at 15:17
Shuvo0o
1891416
edited Oct 31 '13 at 17:21
pinckerman
3,48352538
edited Oct 31 '13 at 17:21
pinckerman
3,48352538
edited Oct 31 '13 at 17:21
pinckerman
3,48352538
3,48352538
asked Jun 1 '13 at 15:17
Shuvo0o
1891416
asked Jun 1 '13 at 15:17
Shuvo0o
1891416
asked Jun 1 '13 at 15:17
Shuvo0o
1891416
1891416
You say "parens" but you also seem to want to check brackets...
– fge
Jun 1 '13 at 15:18
1
what's so special about java here?
– SMA
Apr 1 '15 at 16:54
7
Question. Is[ { ] }a valid matching?
– Kevin
Apr 1 '15 at 17:07
3
Without a language specification (i.e. a precise answer to the question "according to which rules are the expressions you want to parse being formed") we can't answer this. Are they a context free language? They definitely aren't regular due to the parentheses alone. Are they context-sensitive? Turing-complete? Regardless of all that, this question should be on CS.SE
– G. Bach
Apr 1 '15 at 17:45
1
Or you could write a real parser instead of abusing regex.
– cpburnz
Apr 2 '15 at 19:12
|
show 15 more comments
You say "parens" but you also seem to want to check brackets...
– fge
Jun 1 '13 at 15:18
1
what's so special about java here?
– SMA
Apr 1 '15 at 16:54
7
Question. Is[ { ] }a valid matching?
– Kevin
Apr 1 '15 at 17:07
3
Without a language specification (i.e. a precise answer to the question "according to which rules are the expressions you want to parse being formed") we can't answer this. Are they a context free language? They definitely aren't regular due to the parentheses alone. Are they context-sensitive? Turing-complete? Regardless of all that, this question should be on CS.SE
– G. Bach
Apr 1 '15 at 17:45
1
Or you could write a real parser instead of abusing regex.
– cpburnz
Apr 2 '15 at 19:12
You say "parens" but you also seem to want to check brackets...
– fge
Jun 1 '13 at 15:18
You say "parens" but you also seem to want to check brackets...
– fge
Jun 1 '13 at 15:18
1
1
what's so special about java here?
– SMA
Apr 1 '15 at 16:54
what's so special about java here?
– SMA
Apr 1 '15 at 16:54
7
7
Question. Is
[ { ] } a valid matching?– Kevin
Apr 1 '15 at 17:07
Question. Is
[ { ] } a valid matching?– Kevin
Apr 1 '15 at 17:07
3
3
Without a language specification (i.e. a precise answer to the question "according to which rules are the expressions you want to parse being formed") we can't answer this. Are they a context free language? They definitely aren't regular due to the parentheses alone. Are they context-sensitive? Turing-complete? Regardless of all that, this question should be on CS.SE
– G. Bach
Apr 1 '15 at 17:45
Without a language specification (i.e. a precise answer to the question "according to which rules are the expressions you want to parse being formed") we can't answer this. Are they a context free language? They definitely aren't regular due to the parentheses alone. Are they context-sensitive? Turing-complete? Regardless of all that, this question should be on CS.SE
– G. Bach
Apr 1 '15 at 17:45
1
1
Or you could write a real parser instead of abusing regex.
– cpburnz
Apr 2 '15 at 19:12
Or you could write a real parser instead of abusing regex.
– cpburnz
Apr 2 '15 at 19:12
|
show 15 more comments
25 Answers
25
active
oldest
votes
49
Your code has some confusion in its handling of the '{' and '}' characters. It should be entirely parallel to how you handle '(' and ')'.
This code, modified slightly from yours, seems to work properly:
public static boolean isParenthesisMatch(String str) {
if (str.charAt(0) == '{')
return false;
Stack<Character> stack = new Stack<Character>();
char c;
for(int i=0; i < str.length(); i++) {
c = str.charAt(i);
if(c == '(')
stack.push(c);
else if(c == '{')
stack.push(c);
else if(c == ')')
if(stack.empty())
return false;
else if(stack.peek() == '(')
stack.pop();
else
return false;
else if(c == '}')
if(stack.empty())
return false;
else if(stack.peek() == '{')
stack.pop();
else
return false;
}
return stack.empty();
}
answered Jun 1 '13 at 15:44
Don Roby
36k67798
thanks but the problem is {, {} or even {()}, {}() it should return false. In other words, the first c == { should be false.
– Shuvo0o
Jun 1 '13 at 15:56
Then add that check before the loop. I'll edit it in.
– Don Roby
Jun 1 '13 at 15:59
Perfect. Thanks!
– Shuvo0o
Jun 1 '13 at 16:00
thanks, very clear algorithm :)
– butterywombat
Oct 14 '14 at 14:29
Would it work for a whole file or only for a single line? Suppose(is in 1st line but)is in 2nd line of a file. Is it possible to check in this case?
– Sigur
Jun 7 at 21:42
add a comment |
37
This code is easier to understand:
public static boolean CheckParentesis(String str)
{
if (str.isEmpty())
return true;
Stack<Character> stack = new Stack<Character>();
for (int i = 0; i < str.length(); i++)
{
char current = str.charAt(i);
if (current == '{' || current == '(' || current == '[')
{
stack.push(current);
}
if (current == '}' || current == ')' || current == ']')
{
if (stack.isEmpty())
return false;
char last = stack.peek();
if (current == '}' && last == '{' || current == ')' && last == '(' || current == ']' && last == '[')
stack.pop();
else
return false;
}
}
return stack.isEmpty();
}
answered Oct 31 '13 at 16:42
Rafael Amsili
53654
thanks. easy enough
– Abhijit Gaikwad
Aug 12 '14 at 20:10
And it works. Thanks.
– james.garriss
Apr 27 '15 at 17:31
Thanks I converted the code to C++
– Aminos
Mar 2 '17 at 17:07
1
Great code, though it could be slightly improved upon by adding a continue statement after pushing the current character onto the stack.
– JSextonn
Aug 12 at 7:09
add a comment |
6
The algorithm:
- scan the string,pushing to a stack for every '(' found in the string
- if char ')' scanned, pop one '(' from the stack
Now, parentheses are balanced for two conditions:
- '(' can be popped from the stack for every ')' found in the string, and
- stack is empty at the end (when the entire string is processed)
edited Dec 17 '13 at 2:08
Michael Petrotta
51.4k12127171
answered Dec 17 '13 at 1:48
Kibrom Gebre
7819
Even if I add '{' and '}' conditions to this algorithm, it doesn't apply to -{(}). We must check if after everyLASTbracket/parenthesis that opens, theSAMEmust close.
– Swanidhi
Oct 15 '15 at 6:26
add a comment |
5
public static boolean isValidExpression(String expression) {
Map<Character, Character> openClosePair = new HashMap<Character, Character>();
openClosePair.put(')', '(');
openClosePair.put('}', '{');
openClosePair.put(']', '[');
Stack<Character> stack = new Stack<Character>();
for(char ch : expression.toCharArray()) {
if(openClosePair.containsKey(ch)) {
if(stack.pop() != openClosePair.get(ch)) {
return false;
}
} else if(openClosePair.values().contains(ch)) {
stack.push(ch);
}
}
return stack.isEmpty();
}
answered Mar 29 '16 at 12:20
ganesan dharmalingam
22435
1
Why should OP use your code? Could you expand your answer with an explanation?
– Zippy
Mar 29 '16 at 12:33
It returns the result immediately after found a illegal close. Uses Map which intern uses hashing technique and faster. Number of lines are less and easy to understand.
– ganesan dharmalingam
May 12 '16 at 7:39
openClosePair.values().contains(ch)be replacedopenClosePair.containsValue(ch)
– Tim
Jan 7 '17 at 23:14
your last pair is backwards change to (']','[')
– JesseBoyd
Apr 5 at 21:24
and you need to check if the stack is empty if(stack.empty() || stack.pop() != openClosedPair.get(ch)) { return false; }
– JesseBoyd
Apr 5 at 21:44
|
show 1 more comment
3
Actually, there is no need to check any cases "manually". You can just run the following algorithm:
Iterate over the given sequence. Start with an empty stack.
If the current char is an opening bracket, just push it to the stack.
If it's a closing bracket, check that the stack is not empty and the top element of the step is an appropriate opening bracket(that it is, matches this one). If it is not, report an error. Otherwise, pop the top element from the stack.
In the end, the sequence is correct iff the stack is empty.
Why is it correct? Here is a sketch of a proof: if this algorithm reported that the sequence is corrected, it had found a matching pair of all brackets. Thus, the sequence is indeed correct by definition. If it has reported an error:
If the stack was not empty in the end, the balance of opening and closing brackets is not zero. Thus, it is not a correct sequence.
If the stack was empty when we had to pop an element, the balance is off again.
If there was a wrong element on top of the stack, a pair of "wrong" brackets should match each other. It means that the sequence is not correct.
I have shown that:
If the algorithm has reported that the sequence is correct, it is correct.
If the algorithm has reported that the sequence is not correct, it is incorrect(note that I do not use the fact that there are no other cases except those that are mentioned in your question).
This two points imply that this algorithm works for all possible inputs.
answered Apr 1 '15 at 18:34
kraskevich
16.3k31938
1
The problem is not about correctly nesting parentheses alone.
– G. Bach
Apr 1 '15 at 18:52
Heads-up: your answer has been merged here from stackoverflow.com/questions/29396477/… - please adjust as needed.
– Shog9♦
Apr 3 '15 at 1:09
The implementation of the above algorithm in javascript can be found here (gist.github.com/sanketmaru/e83ce04100966bf46f6e8919a06c33ba). All possible inputs can be tested.
– Sanket
Aug 6 '17 at 16:41
add a comment |
2
public static boolean isBalanced(String s) {
Map<Character, Character> openClosePair = new HashMap<Character, Character>();
openClosePair.put('(', ')');
openClosePair.put('{', '}');
openClosePair.put('[', ']');
Stack<Character> stack = new Stack<Character>();
for (int i = 0; i < s.length(); i++) {
if (openClosePair.containsKey(s.charAt(i))) {
stack.push(s.charAt(i));
} else if ( openClosePair.containsValue(s.charAt(i))) {
if (stack.isEmpty())
return false;
if (openClosePair.get(stack.pop()) != s.charAt(i))
return false;
}
// ignore all other characters
}
return stack.isEmpty();
}
answered May 19 '16 at 11:25
deniswsrosa
522414
add a comment |
1
Algorithm is:
1)Create a stack
2)while(end of input is not reached)
i)if the character read is not a sysmbol to be balanced ,ignore it.
ii)if the character is {,[,( then push it to stack
iii)If it is a },),] then if
a)the stack is empty report an error(catch it) i.e not balanced
b)else pop the stack
iv)if element popped is not corresponding to opening sysmbol,then report error.
3) In the end,if stack is not empty report error else expression is balanced.
In Java code:
public class StackDemo {
public static void main(String args) throws Exception {
System.out.println("--Bracket checker--");
CharStackArray stack = new CharStackArray(10);
stack.balanceSymbol("[a+b{c+(e-f[p-q])}]") ;
stack.display();
}
}
class CharStackArray {
private char array;
private int top;
private int capacity;
public CharStackArray(int cap) {
capacity = cap;
array = new char[capacity];
top = -1;
}
public void push(char data) {
array[++top] = data;
}
public char pop() {
return array[top--];
}
public void display() {
for (int i = 0; i <= top; i++) {
System.out.print(array[i] + "->");
}
}
public char peek() throws Exception {
return array[top];
}
/*Call this method by passing a string expression*/
public void balanceSymbol(String str) {
try {
char arr = str.toCharArray();
for (int i = 0; i < arr.length; i++) {
if (arr[i] == '[' || arr[i] == '{' || arr[i] == '(')
push(arr[i]);
else if (arr[i] == '}' && peek() == '{')
pop();
else if (arr[i] == ']' && peek() == '[')
pop();
else if (arr[i] == ')' && peek() == '(')
pop();
}
if (isEmpty()) {
System.out.println("String is balanced");
} else {
System.out.println("String is not balanced");
}
} catch (Exception e) {
System.out.println("String not balanced");
}
}
public boolean isEmpty() {
return (top == -1);
}
}
Output:
--Bracket checker--
String is balanced
answered Jan 3 '16 at 22:45
Prateek Joshi
2,78812636
add a comment |
1
import java.util.*;
class StackDemo {
public static void main(String argh) {
boolean flag = true;
String str = "(()){}()";
int l = str.length();
flag = true;
Stack<String> st = new Stack<String>();
for (int i = 0; i < l; i++) {
String test = str.substring(i, i + 1);
if (test.equals("(")) {
st.push(test);
} else if (test.equals("{")) {
st.push(test);
} else if (test.equals("[")) {
st.push(test);
} else if (test.equals(")")) {
if (st.empty()) {
flag = false;
break;
}
if (st.peek().equals("(")) {
st.pop();
} else {
flag = false;
break;
}
} else if (test.equals("}")) {
if (st.empty()) {
flag = false;
break;
}
if (st.peek().equals("{")) {
st.pop();
} else {
flag = false;
break;
}
} else if (test.equals("]")) {
if (st.empty()) {
flag = false;
break;
}
if (st.peek().equals("[")) {
st.pop();
} else {
flag = false;
break;
}
}
}
if (flag && st.empty())
System.out.println("true");
else
System.out.println("false");
}
}
edited Jun 23 '16 at 20:46
Tony Babarino
2,21641734
answered Jun 23 '16 at 20:14
Ashish Jadhav
112
1
While this code snippet may solve the question, including an explanation really helps to improve the quality of your post. Remember that you are answering the question for readers in the future, and those people might not know the reasons for your code suggestion.
– Tony Babarino
Jun 23 '16 at 20:31
add a comment |
1
Ganesan's answer above is not correct and StackOverflow is not letting me comment or Edit his post. So below is the correct answer. Ganesan has an incorrect facing "[" and is missing the stack isEmpty() check.
The below code will return true if the braces are properly matching.
public static boolean isValidExpression(String expression) {
Map<Character, Character> openClosePair = new HashMap<Character, Character>();
openClosePair.put(')', '(');
openClosePair.put('}', '{');
openClosePair.put(']', '[');
Stack<Character> stack = new Stack<Character>();
for(char ch : expression.toCharArray()) {
if(openClosePair.containsKey(ch)) {
if(stack.isEmpty() || stack.pop() != openClosePair.get(ch)) {
return false;
}
} else if(openClosePair.values().contains(ch)) {
stack.push(ch);
}
}
return stack.isEmpty();
}
answered May 5 '17 at 15:43
Jared
7117
add a comment |
1
Optimized implementation using Stacks and Switch statement:
public class JavaStack {
public static void main(String args) {
Scanner sc = new Scanner(System.in);
Stack<Character> s = new Stack<Character>();
while (sc.hasNext()) {
String input = sc.next();
for (int i = 0; i < input.length(); i++) {
char c = input.charAt(i);
switch (c) {
case '(':
s.push(c); break;
case '[':
s.push(c); break;
case '{':
s.push(c); break;
case ')':
if (!s.isEmpty() && s.peek().equals('(')) {
s.pop();
} else {
s.push(c);
} break;
case ']':
if (!s.isEmpty() && s.peek().equals('[')) {
s.pop();
} else {
s.push(c);
} break;
case '}':
if (!s.isEmpty() && s.peek().equals('{')) {
s.pop();
} else {
s.push(c);
} break;
default:
s.push('x'); break;
}
}
if (s.empty()) {
System.out.println("true");
} else {
System.out.println("false");
s.clear();
}
}
} }
Cheers !
answered Nov 11 at 18:21
Leo
112
add a comment |
0
//basic code non strack algorithm just started learning java ignore space and time.
/// {[()]}{}
// {[( -a -> }]) -b -> replace a(]}) -> reverse a( }]))->
//Split string to substring {[()]}, next , next , next{}
public class testbrackets {
static String stringfirst;
static String stringsecond;
static int open = 0;
public static void main(String args) {
splitstring("(()){}()");
}
static void splitstring(String str){
int len = str.length();
for(int i=0;i<=len-1;i++){
stringfirst="";
stringsecond="";
System.out.println("loop starttttttt");
char a = str.charAt(i);
if(a=='{'||a=='['||a=='(')
{
open = open+1;
continue;
}
if(a=='}'||a==']'||a==')'){
if(open==0){
System.out.println(open+"started with closing brace");
return;
}
String stringfirst=str.substring(i-open, i);
System.out.println("stringfirst"+stringfirst);
String stringsecond=str.substring(i, i+open);
System.out.println("stringsecond"+stringsecond);
replace(stringfirst, stringsecond);
}
i=(i+open)-1;
open=0;
System.out.println(i);
}
}
static void replace(String stringfirst, String stringsecond){
stringfirst = stringfirst.replace('{', '}');
stringfirst = stringfirst.replace('(', ')');
stringfirst = stringfirst.replace('[', ']');
StringBuilder stringfirst1 = new StringBuilder(stringfirst);
stringfirst = stringfirst1.reverse().toString();
System.out.println("stringfirst"+stringfirst);
System.out.println("stringsecond"+stringsecond);
if(stringfirst.equals(stringsecond)){
System.out.println("pass");
}
else{
System.out.println("fail");
System.exit(0);
}
}
}
answered Apr 19 '15 at 17:54
sai tvs
1
This is quite different to the code posted by the OP. It would be very helpful to others if you could explain it a bit so we can see what your train of thought was.
– Wai Ha Lee
Apr 19 '15 at 18:00
Plus it's way too long. you should also refrain as much as possible from printing from within methods.
– Amos Bordowitz
Sep 16 '15 at 10:14
add a comment |
0
import java.util.Stack;
class Demo
{
char c;
public boolean checkParan(String word)
{
Stack<Character> sta = new Stack<Character>();
for(int i=0;i<word.length();i++)
{
c=word.charAt(i);
if(c=='(')
{
sta.push(c);
System.out.println("( Pushed into the stack");
}
else if(c=='{')
{
sta.push(c);
System.out.println("( Pushed into the stack");
}
else if(c==')')
{
if(sta.empty())
{
System.out.println("Stack is Empty");
return false;
}
else if(sta.peek()=='(')
{
sta.pop();
System.out.println(" ) is poped from the Stack");
}
else if(sta.peek()=='(' && sta.empty())
{
System.out.println("Stack is Empty");
return false;
}
}
else if(c=='}')
{
if(sta.empty())
{
System.out.println("Stack is Empty");
return false;
}
else if(sta.peek()=='{')
{
sta.pop();
System.out.println(" } is poped from the Stack");
}
}
else if(c=='(')
{
if(sta.empty())
{
System.out.println("Stack is empty only ( parenthesis in Stack ");
}
}
}
// System.out.print("The top element is : "+sta.peek());
return sta.empty();
}
}
public class ParaenthesisChehck {
/**
* @param args the command line arguments
*/
public static void main(String args) {
// TODO code application logic here
Demo d1= new Demo();
// d1.checkParan(" ");
// d1.checkParan("{}");
//d1.checkParan("()");
//d1.checkParan("{()}");
// d1.checkParan("{123}");
d1.checkParan("{{{}}");
}
}
edited Nov 20 '15 at 10:55
gstackoverflow
9,66644164349
answered Nov 13 '15 at 20:34
Pooja Gandhi
11
add a comment |
0
I tried this using javascript below is the result.
function bracesChecker(str) {
if(!str) {
return true;
}
var openingBraces = ['{', '[', '('];
var closingBraces = ['}', ']', ')'];
var stack = ;
var openIndex;
var closeIndex;
//check for opening Braces in the val
for (var i = 0, len = str.length; i < len; i++) {
openIndex = openingBraces.indexOf(str[i]);
closeIndex = closingBraces.indexOf(str[i]);
if(openIndex !== -1) {
stack.push(str[i]);
}
if(closeIndex !== -1) {
if(openingBraces[closeIndex] === stack[stack.length-1]) {
stack.pop();
} else {
return false;
}
}
}
if(stack.length === 0) {
return true;
} else {
return false;
}
}
var testStrings = [
'',
'test',
'{{()()}()}()',
'{test{[test]}}',
'{test{[test]}',
'{test{(yo)[test]}}',
'test{[test]}}',
'te()st{[test]}',
'te()st{[test'
];
testStrings.forEach(val => console.log(`${val} => ${bracesChecker(val)}`));
answered Dec 30 '15 at 8:58
Yalamber
4,068104571
add a comment |
0
I have seen answers here and almost all did well. However, I have written my own version that utilizes a Dictionary for managing the bracket pairs and a stack to monitor the order of detected braces. I have also written a blog post for this.
Here is my class
public class FormulaValidator
{
// Question: Check if a string is balanced. Every opening bracket is matched by a closing bracket in a correct position.
// { [ ( } ] )
// Example: "()" is balanced
// Example: "{ ]" is not balanced.
// Examples: "(){}" is balanced.
// "{()}" is balanced
// "{ ( [ ) ] }" is _not_ balanced
// Input: string, containing the bracket symbols only
// Output: true or false
public bool IsBalanced(string input)
{
var brackets = BuildBracketMap();
var openingBraces = new Stack<char>();
var inputCharacters = input.ToCharArray();
foreach (char character in inputCharacters)
{
if (brackets.ContainsKey(character))
{
openingBraces.Push(character);
}
if (brackets.ContainsValue(character))
{
var closingBracket = character;
var openingBracket = brackets.FirstOrDefault(x => x.Value == closingBracket).Key;
if (openingBraces.Peek() == openingBracket)
openingBraces.Pop();
else
return false;
}
}
return openingBraces.Count == 0;
}
private Dictionary<char, char> BuildBracketMap()
{
return new Dictionary<char, char>()
{
{'[', ']'},
{'(', ')'},
{'{', '}'}
};
}
}
answered Mar 23 '17 at 13:05
Allan Chua
3,73782855
add a comment |
0
If you want to have a look at my code. Just for reference
public class Default {
public static void main(String args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int numOfString = Integer.parseInt(br.readLine());
String s;
String stringBalanced = "YES";
Stack<Character> exprStack = new Stack<Character>();
while ((s = br.readLine()) != null) {
stringBalanced = "YES";
int length = s.length() - 1;
for (int i = 0; i <= length; i++) {
char tmp = s.charAt(i);
if(tmp=='[' || tmp=='{' || tmp=='('){
exprStack.push(tmp);
}else if(tmp==']' || tmp=='}' || tmp==')'){
if(!exprStack.isEmpty()){
char peekElement = exprStack.peek();
exprStack.pop();
if(tmp==']' && peekElement!='['){
stringBalanced="NO";
}else if(tmp=='}' && peekElement!='{'){
stringBalanced="NO";
}else if(tmp==')' && peekElement!='('){
stringBalanced="NO";
}
}else{
stringBalanced="NO";
break;
}
}
}
if(!exprStack.isEmpty()){
stringBalanced = "NO";
}
exprStack.clear();
System.out.println(stringBalanced);
}
}
}
answered May 18 '17 at 13:13
underdog
2,68022765
add a comment |
0
public String checkString(String value) {
Stack<Character> stack = new Stack<>();
char topStackChar = 0;
for (int i = 0; i < value.length(); i++) {
if (!stack.isEmpty()) {
topStackChar = stack.peek();
}
stack.push(value.charAt(i));
if (!stack.isEmpty() && stack.size() > 1) {
if ((topStackChar == '[' && stack.peek() == ']') ||
(topStackChar == '{' && stack.peek() == '}') ||
(topStackChar == '(' && stack.peek() == ')')) {
stack.pop();
stack.pop();
}
}
}
return stack.isEmpty() ? "YES" : "NO";
}
answered Aug 19 '17 at 14:42
unicredit
19610
add a comment |
0
Here's a solution in Python.
#!/usr/bin/env python
def brackets_match(brackets):
stack =
for char in brackets:
if char == "{" or char == "(" or char == "[":
stack.append(char)
if char == "}":
if stack[-1] == "{":
stack.pop()
else:
return False
elif char == "]":
if stack[-1] == "[":
stack.pop()
else:
return False
elif char == ")":
if stack[-1] == "(":
stack.pop()
else:
return False
if len(stack) == 0:
return True
else:
return False
if __name__ == "__main__":
print(brackets_match("This is testing {()} if brackets have match."))
answered May 29 at 12:13
Said Ali Samed
8412
add a comment |
0
Was asked to implement this algorithm at live coding interview, here's my refactored solution in C#:
Git Tests
answered Jun 22 at 16:10
Dmytro Zhluktenko
647
add a comment |
0
package com.balance.braces;
import java.util.Arrays;
import java.util.Stack;
public class BalanceBraces {
public static void main(String args) {
String values = { "()]", "[()]" };
String rsult = match(values);
Arrays.stream(rsult).forEach(str -> System.out.println(str));
}
static String match(String values) {
String returnString = new String[values.length];
for (int i = 0; i < values.length; i++) {
String value = values[i];
if (value.length() % 2 != 0) {
returnString[i] = "NO";
continue;
} else {
Stack<Character> buffer = new Stack<Character>();
for (char ch : value.toCharArray()) {
if (buffer.isEmpty()) {
buffer.add(ch);
} else {
if (isMatchedBrace(buffer.peek(), ch)) {
buffer.pop();
} else {
buffer.push(ch);
}
}
if (buffer.isEmpty()) {
returnString[i] = "YES";
} else {
returnString[i] = "FALSE";
}
}
}
}
return returnString;
}
static boolean isMatchedBrace(char start, char endmatch) {
if (start == '{')
return endmatch == '}';
if (start == '(')
return endmatch == ')';
if (start == '[')
return endmatch == ']';
return false;
}
}
edited Aug 2 at 12:12
Fredrik Widerberg
2,687102340
answered Aug 2 at 11:51
Ritesh Nailwal
11
add a comment |
0
Check balanced parenthesis or brackets with stack--
var excp = "{{()}[{a+b+b}][{(c+d){}}]}";
var stk = ;
function bracket_balance(){
for(var i=0;i<excp.length;i++){
if(excp[i]=='[' || excp[i]=='(' || excp[i]=='{'){
stk.push(excp[i]);
}else if(excp[i]== ']' && stk.pop() != '['){
return false;
}else if(excp[i]== '}' && stk.pop() != '{'){
return false;
}else if(excp[i]== ')' && stk.pop() != '('){
return false;
}
}
return true;
}
console.log(bracket_balance());
//Parenthesis are balance then return true else false
answered Nov 25 at 8:56
suryadev
732
add a comment |
0
You're doing some extra checks that aren't needed. Doesn't make any diff to functionality, but a cleaner way to write your code would be:
public static boolean isParenthesisMatch(String str) {
Stack<Character> stack = new Stack<Character>();
char c;
for (int i = 0; i < str.length(); i++) {
c = str.charAt(i);
if (c == '(' || c == '{')
stack.push(c);
else if (stack.empty())
return false;
else if (c == ')') {
if (stack.pop() != '(')
return false;
} else if (c == '}') {
if (stack.pop() != '{')
return false;
}
}
return stack.empty();
}
There is no reason to peek at a paranthesis before removing it from the stack. I'd also consider wrapping instruction blocks in parantheses to improve readability.
answered Dec 23 at 14:36
tfp95
81
add a comment |
-1
import java.util.*;
public class Parenthesis
{
public static void main(String...okok)
{
Scanner sc= new Scanner(System.in);
String str=sc.next();
System.out.println(isValid(str));
}
public static int isValid(String a) {
if(a.length()%2!=0)
{
return 0;
}
else if(a.length()==0)
{
return 1;
}
else
{
char c=a.toCharArray();
Stack<Character> stk = new Stack<Character>();
for(int i=0;i<c.length;i++)
{
if(c[i]=='(' || c[i]=='[' || c[i]=='{')
{
stk.push(c[i]);
}
else
{
if(stk.isEmpty())
{
return 0;
//break;
}
else
{
char cc=c[i];
if(cc==')' && stk.peek()=='(' )
{
stk.pop();
}
else if(cc==']' && stk.peek()=='[' )
{
stk.pop();
}
else if(cc=='}' && stk.peek()=='{' )
{
stk.pop();
}
}
}
}
if(stk.isEmpty())
{
return 1;
}else
{
return 0;
}
}
}
}
edited Dec 4 '15 at 5:26
Haris
10.5k62851
answered Dec 4 '15 at 4:20
Prabhu
11
add a comment |
-1
import java.util.*;
public class MatchBrackets {
public static void main(String argh) {
String input = "{()}";
System.out.println (input);
char openChars = {'[','{','('};
char closeChars = {']','}',')'};
Stack<Character> stack = new Stack<Character>();
for (int i = 0; i < input.length(); i++) {
String x = "" +input.charAt(i);
if (String.valueOf(openChars).indexOf(x) != -1)
{
stack.push(input.charAt(i));
}
else
{
Character lastOpener = stack.peek();
int idx1 = String.valueOf(openChars).indexOf(lastOpener.toString());
int idx2 = String.valueOf(closeChars).indexOf(x);
if (idx1 != idx2)
{
System.out.println("false");
return;
}
else
{
stack.pop();
}
}
}
if (stack.size() == 0)
System.out.println("true");
else
System.out.println("false");
}
}
edited Feb 25 '16 at 18:48
gengisdave
1,40741517
answered Feb 25 '16 at 17:53
Pravin Lobo
1
add a comment |
-1
public static bool IsBalanced(string input)
{
Dictionary<char, char> bracketPairs = new Dictionary<char, char>() {
{ '(', ')' },
{ '{', '}' },
{ '[', ']' },
{ '<', '>' }
};
Stack<char> brackets = new Stack<char>();
try
{
// Iterate through each character in the input string
foreach (char c in input)
{
// check if the character is one of the 'opening' brackets
if (bracketPairs.Keys.Contains(c))
{
// if yes, push to stack
brackets.Push(c);
}
else
// check if the character is one of the 'closing' brackets
if (bracketPairs.Values.Contains(c))
{
// check if the closing bracket matches the 'latest' 'opening' bracket
if (c == bracketPairs[brackets.First()])
{
brackets.Pop();
}
else
// if not, its an unbalanced string
return false;
}
else
// continue looking
continue;
}
}
catch
{
// an exception will be caught in case a closing bracket is found,
// before any opening bracket.
// that implies, the string is not balanced. Return false
return false;
}
// Ensure all brackets are closed
return brackets.Count() == 0 ? true : false;
}
answered Jun 8 '17 at 5:28
Muhammad Kashif
1
add a comment |
-1
in java you don't want to compare the string or char by == signs. you would use equals method. equalsIgnoreCase or something of the like. if you use == it must point to the same memory location. In the method below I attempted to use ints to get around this. using ints here from the string index since every opening brace has a closing brace. I wanted to use location match instead of a comparison match. But i think with this you have to be intentional in where you place the characters of the string. Lets also consider that Yes = true and No = false for simplicity. This answer assumes that you passed an array of strings to inspect and required an array of if yes (they matched) or No (they didn't)
import java.util.Stack;
public static void main(String args) {
//String arrayOfBraces = new String{"{}","([{}])","{}{()}","{}","}]{}","{[)]()}"};
// Example: "()" is balanced
// Example: "{ ]" is not balanced.
// Examples: "(){}" is balanced.
// "{()}" is balanced
// "{([)]}" is _not_ balanced
String arrayOfBraces = new String{"{}","([{}])","{}{()}","(){}","}]{}","{[)]()}","{[)]()}","{([)]}"};
String answers = new String[arrayOfBraces.length];
String openers = "([{";
String closers = ")]}";
String stringToInspect = "";
Stack<String> stack = new Stack<String>();
for (int i = 0; i < arrayOfBraces.length; i++) {
stringToInspect = arrayOfBraces[i];
for (int j = 0; j < stringToInspect.length(); j++) {
if(stack.isEmpty()){
if (openers.indexOf(stringToInspect.charAt(j))>=0) {
stack.push(""+stringToInspect.charAt(j));
}
else{
answers[i]= "NO";
j=stringToInspect.length();
}
}
else if(openers.indexOf(stringToInspect.charAt(j))>=0){
stack.push(""+stringToInspect.charAt(j));
}
else{
String comparator = stack.pop();
int compLoc = openers.indexOf(comparator);
int thisLoc = closers.indexOf(stringToInspect.charAt(j));
if (compLoc != thisLoc) {
answers[i]= "NO";
j=stringToInspect.length();
}
else{
if(stack.empty() && (j== stringToInspect.length()-1)){
answers[i]= "YES";
}
}
}
}
}
System.out.println(answers.length);
for (int j = 0; j < answers.length; j++) {
System.out.println(answers[j]);
}
}
answered Sep 11 at 20:07
TimeTrax
19527
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
StackExchange.using("externalEditor", function () {
StackExchange.using("snippets", function () {
StackExchange.snippets.init();
});
});
}, "code-snippets");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "1"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
draft saved
draft discarded
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f16874176%2fparenthesis-brackets-matching-using-stack-algorithm%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
25 Answers
25
active
oldest
votes
25 Answers
25
active
oldest
votes
active
oldest
votes
active
oldest
votes
49
Your code has some confusion in its handling of the '{' and '}' characters. It should be entirely parallel to how you handle '(' and ')'.
This code, modified slightly from yours, seems to work properly:
public static boolean isParenthesisMatch(String str) {
if (str.charAt(0) == '{')
return false;
Stack<Character> stack = new Stack<Character>();
char c;
for(int i=0; i < str.length(); i++) {
c = str.charAt(i);
if(c == '(')
stack.push(c);
else if(c == '{')
stack.push(c);
else if(c == ')')
if(stack.empty())
return false;
else if(stack.peek() == '(')
stack.pop();
else
return false;
else if(c == '}')
if(stack.empty())
return false;
else if(stack.peek() == '{')
stack.pop();
else
return false;
}
return stack.empty();
}
answered Jun 1 '13 at 15:44
Don Roby
36k67798
thanks but the problem is {, {} or even {()}, {}() it should return false. In other words, the first c == { should be false.
– Shuvo0o
Jun 1 '13 at 15:56
Then add that check before the loop. I'll edit it in.
– Don Roby
Jun 1 '13 at 15:59
Perfect. Thanks!
– Shuvo0o
Jun 1 '13 at 16:00
thanks, very clear algorithm :)
– butterywombat
Oct 14 '14 at 14:29
Would it work for a whole file or only for a single line? Suppose(is in 1st line but)is in 2nd line of a file. Is it possible to check in this case?
– Sigur
Jun 7 at 21:42
add a comment |
49
Your code has some confusion in its handling of the '{' and '}' characters. It should be entirely parallel to how you handle '(' and ')'.
This code, modified slightly from yours, seems to work properly:
public static boolean isParenthesisMatch(String str) {
if (str.charAt(0) == '{')
return false;
Stack<Character> stack = new Stack<Character>();
char c;
for(int i=0; i < str.length(); i++) {
c = str.charAt(i);
if(c == '(')
stack.push(c);
else if(c == '{')
stack.push(c);
else if(c == ')')
if(stack.empty())
return false;
else if(stack.peek() == '(')
stack.pop();
else
return false;
else if(c == '}')
if(stack.empty())
return false;
else if(stack.peek() == '{')
stack.pop();
else
return false;
}
return stack.empty();
}
answered Jun 1 '13 at 15:44
Don Roby
36k67798
thanks but the problem is {, {} or even {()}, {}() it should return false. In other words, the first c == { should be false.
– Shuvo0o
Jun 1 '13 at 15:56
Then add that check before the loop. I'll edit it in.
– Don Roby
Jun 1 '13 at 15:59
Perfect. Thanks!
– Shuvo0o
Jun 1 '13 at 16:00
thanks, very clear algorithm :)
– butterywombat
Oct 14 '14 at 14:29
Would it work for a whole file or only for a single line? Suppose(is in 1st line but)is in 2nd line of a file. Is it possible to check in this case?
– Sigur
Jun 7 at 21:42
add a comment |
49
49
49
Your code has some confusion in its handling of the '{' and '}' characters. It should be entirely parallel to how you handle '(' and ')'.
This code, modified slightly from yours, seems to work properly:
public static boolean isParenthesisMatch(String str) {
if (str.charAt(0) == '{')
return false;
Stack<Character> stack = new Stack<Character>();
char c;
for(int i=0; i < str.length(); i++) {
c = str.charAt(i);
if(c == '(')
stack.push(c);
else if(c == '{')
stack.push(c);
else if(c == ')')
if(stack.empty())
return false;
else if(stack.peek() == '(')
stack.pop();
else
return false;
else if(c == '}')
if(stack.empty())
return false;
else if(stack.peek() == '{')
stack.pop();
else
return false;
}
return stack.empty();
}
answered Jun 1 '13 at 15:44
Don Roby
36k67798
Your code has some confusion in its handling of the '{' and '}' characters. It should be entirely parallel to how you handle '(' and ')'.
This code, modified slightly from yours, seems to work properly:
public static boolean isParenthesisMatch(String str) {
if (str.charAt(0) == '{')
return false;
Stack<Character> stack = new Stack<Character>();
char c;
for(int i=0; i < str.length(); i++) {
c = str.charAt(i);
if(c == '(')
stack.push(c);
else if(c == '{')
stack.push(c);
else if(c == ')')
if(stack.empty())
return false;
else if(stack.peek() == '(')
stack.pop();
else
return false;
else if(c == '}')
if(stack.empty())
return false;
else if(stack.peek() == '{')
stack.pop();
else
return false;
}
return stack.empty();
}
answered Jun 1 '13 at 15:44
Don Roby
36k67798
edited Jun 1 '13 at 16:02
answered Jun 1 '13 at 15:44
Don Roby
36k67798
answered Jun 1 '13 at 15:44
Don Roby
36k67798
answered Jun 1 '13 at 15:44
Don Roby
36k67798
36k67798
thanks but the problem is {, {} or even {()}, {}() it should return false. In other words, the first c == { should be false.
– Shuvo0o
Jun 1 '13 at 15:56
Then add that check before the loop. I'll edit it in.
– Don Roby
Jun 1 '13 at 15:59
Perfect. Thanks!
– Shuvo0o
Jun 1 '13 at 16:00
thanks, very clear algorithm :)
– butterywombat
Oct 14 '14 at 14:29
Would it work for a whole file or only for a single line? Suppose(is in 1st line but)is in 2nd line of a file. Is it possible to check in this case?
– Sigur
Jun 7 at 21:42
add a comment |
thanks but the problem is {, {} or even {()}, {}() it should return false. In other words, the first c == { should be false.
– Shuvo0o
Jun 1 '13 at 15:56
Then add that check before the loop. I'll edit it in.
– Don Roby
Jun 1 '13 at 15:59
Perfect. Thanks!
– Shuvo0o
Jun 1 '13 at 16:00
thanks, very clear algorithm :)
– butterywombat
Oct 14 '14 at 14:29
Would it work for a whole file or only for a single line? Suppose(is in 1st line but)is in 2nd line of a file. Is it possible to check in this case?
– Sigur
Jun 7 at 21:42
thanks but the problem is {, {} or even {()}, {}() it should return false. In other words, the first c == { should be false.
– Shuvo0o
Jun 1 '13 at 15:56
thanks but the problem is {, {} or even {()}, {}() it should return false. In other words, the first c == { should be false.
– Shuvo0o
Jun 1 '13 at 15:56
Then add that check before the loop. I'll edit it in.
– Don Roby
Jun 1 '13 at 15:59
Then add that check before the loop. I'll edit it in.
– Don Roby
Jun 1 '13 at 15:59
Perfect. Thanks!
– Shuvo0o
Jun 1 '13 at 16:00
Perfect. Thanks!
– Shuvo0o
Jun 1 '13 at 16:00
thanks, very clear algorithm :)
– butterywombat
Oct 14 '14 at 14:29
thanks, very clear algorithm :)
– butterywombat
Oct 14 '14 at 14:29
Would it work for a whole file or only for a single line? Suppose
( is in 1st line but ) is in 2nd line of a file. Is it possible to check in this case?– Sigur
Jun 7 at 21:42
Would it work for a whole file or only for a single line? Suppose
( is in 1st line but ) is in 2nd line of a file. Is it possible to check in this case?– Sigur
Jun 7 at 21:42
add a comment |
37
This code is easier to understand:
public static boolean CheckParentesis(String str)
{
if (str.isEmpty())
return true;
Stack<Character> stack = new Stack<Character>();
for (int i = 0; i < str.length(); i++)
{
char current = str.charAt(i);
if (current == '{' || current == '(' || current == '[')
{
stack.push(current);
}
if (current == '}' || current == ')' || current == ']')
{
if (stack.isEmpty())
return false;
char last = stack.peek();
if (current == '}' && last == '{' || current == ')' && last == '(' || current == ']' && last == '[')
stack.pop();
else
return false;
}
}
return stack.isEmpty();
}
answered Oct 31 '13 at 16:42
Rafael Amsili
53654
thanks. easy enough
– Abhijit Gaikwad
Aug 12 '14 at 20:10
And it works. Thanks.
– james.garriss
Apr 27 '15 at 17:31
Thanks I converted the code to C++
– Aminos
Mar 2 '17 at 17:07
1
Great code, though it could be slightly improved upon by adding a continue statement after pushing the current character onto the stack.
– JSextonn
Aug 12 at 7:09
add a comment |
37
This code is easier to understand:
public static boolean CheckParentesis(String str)
{
if (str.isEmpty())
return true;
Stack<Character> stack = new Stack<Character>();
for (int i = 0; i < str.length(); i++)
{
char current = str.charAt(i);
if (current == '{' || current == '(' || current == '[')
{
stack.push(current);
}
if (current == '}' || current == ')' || current == ']')
{
if (stack.isEmpty())
return false;
char last = stack.peek();
if (current == '}' && last == '{' || current == ')' && last == '(' || current == ']' && last == '[')
stack.pop();
else
return false;
}
}
return stack.isEmpty();
}
answered Oct 31 '13 at 16:42
Rafael Amsili
53654
thanks. easy enough
– Abhijit Gaikwad
Aug 12 '14 at 20:10
And it works. Thanks.
– james.garriss
Apr 27 '15 at 17:31
Thanks I converted the code to C++
– Aminos
Mar 2 '17 at 17:07
1
Great code, though it could be slightly improved upon by adding a continue statement after pushing the current character onto the stack.
– JSextonn
Aug 12 at 7:09
add a comment |
37
37
37
This code is easier to understand:
public static boolean CheckParentesis(String str)
{
if (str.isEmpty())
return true;
Stack<Character> stack = new Stack<Character>();
for (int i = 0; i < str.length(); i++)
{
char current = str.charAt(i);
if (current == '{' || current == '(' || current == '[')
{
stack.push(current);
}
if (current == '}' || current == ')' || current == ']')
{
if (stack.isEmpty())
return false;
char last = stack.peek();
if (current == '}' && last == '{' || current == ')' && last == '(' || current == ']' && last == '[')
stack.pop();
else
return false;
}
}
return stack.isEmpty();
}
answered Oct 31 '13 at 16:42
Rafael Amsili
53654
This code is easier to understand:
public static boolean CheckParentesis(String str)
{
if (str.isEmpty())
return true;
Stack<Character> stack = new Stack<Character>();
for (int i = 0; i < str.length(); i++)
{
char current = str.charAt(i);
if (current == '{' || current == '(' || current == '[')
{
stack.push(current);
}
if (current == '}' || current == ')' || current == ']')
{
if (stack.isEmpty())
return false;
char last = stack.peek();
if (current == '}' && last == '{' || current == ')' && last == '(' || current == ']' && last == '[')
stack.pop();
else
return false;
}
}
return stack.isEmpty();
}
answered Oct 31 '13 at 16:42
Rafael Amsili
53654
answered Oct 31 '13 at 16:42
Rafael Amsili
53654
answered Oct 31 '13 at 16:42
Rafael Amsili
53654
answered Oct 31 '13 at 16:42
Rafael Amsili
53654
53654
thanks. easy enough
– Abhijit Gaikwad
Aug 12 '14 at 20:10
And it works. Thanks.
– james.garriss
Apr 27 '15 at 17:31
Thanks I converted the code to C++
– Aminos
Mar 2 '17 at 17:07
1
Great code, though it could be slightly improved upon by adding a continue statement after pushing the current character onto the stack.
– JSextonn
Aug 12 at 7:09
add a comment |
thanks. easy enough
– Abhijit Gaikwad
Aug 12 '14 at 20:10
And it works. Thanks.
– james.garriss
Apr 27 '15 at 17:31
Thanks I converted the code to C++
– Aminos
Mar 2 '17 at 17:07
1
Great code, though it could be slightly improved upon by adding a continue statement after pushing the current character onto the stack.
– JSextonn
Aug 12 at 7:09
thanks. easy enough
– Abhijit Gaikwad
Aug 12 '14 at 20:10
thanks. easy enough
– Abhijit Gaikwad
Aug 12 '14 at 20:10
And it works. Thanks.
– james.garriss
Apr 27 '15 at 17:31
And it works. Thanks.
– james.garriss
Apr 27 '15 at 17:31
Thanks I converted the code to C++
– Aminos
Mar 2 '17 at 17:07
Thanks I converted the code to C++
– Aminos
Mar 2 '17 at 17:07
1
1
Great code, though it could be slightly improved upon by adding a continue statement after pushing the current character onto the stack.
– JSextonn
Aug 12 at 7:09
Great code, though it could be slightly improved upon by adding a continue statement after pushing the current character onto the stack.
– JSextonn
Aug 12 at 7:09
add a comment |
6
The algorithm:
- scan the string,pushing to a stack for every '(' found in the string
- if char ')' scanned, pop one '(' from the stack
Now, parentheses are balanced for two conditions:
- '(' can be popped from the stack for every ')' found in the string, and
- stack is empty at the end (when the entire string is processed)
edited Dec 17 '13 at 2:08
Michael Petrotta
51.4k12127171
answered Dec 17 '13 at 1:48
Kibrom Gebre
7819
Even if I add '{' and '}' conditions to this algorithm, it doesn't apply to -{(}). We must check if after everyLASTbracket/parenthesis that opens, theSAMEmust close.
– Swanidhi
Oct 15 '15 at 6:26
add a comment |
6
The algorithm:
- scan the string,pushing to a stack for every '(' found in the string
- if char ')' scanned, pop one '(' from the stack
Now, parentheses are balanced for two conditions:
- '(' can be popped from the stack for every ')' found in the string, and
- stack is empty at the end (when the entire string is processed)
edited Dec 17 '13 at 2:08
Michael Petrotta
51.4k12127171
answered Dec 17 '13 at 1:48
Kibrom Gebre
7819
Even if I add '{' and '}' conditions to this algorithm, it doesn't apply to -{(}). We must check if after everyLASTbracket/parenthesis that opens, theSAMEmust close.
– Swanidhi
Oct 15 '15 at 6:26
add a comment |
6
6
6
The algorithm:
- scan the string,pushing to a stack for every '(' found in the string
- if char ')' scanned, pop one '(' from the stack
Now, parentheses are balanced for two conditions:
- '(' can be popped from the stack for every ')' found in the string, and
- stack is empty at the end (when the entire string is processed)
edited Dec 17 '13 at 2:08
Michael Petrotta
51.4k12127171
answered Dec 17 '13 at 1:48
Kibrom Gebre
7819
The algorithm:
- scan the string,pushing to a stack for every '(' found in the string
- if char ')' scanned, pop one '(' from the stack
Now, parentheses are balanced for two conditions:
- '(' can be popped from the stack for every ')' found in the string, and
- stack is empty at the end (when the entire string is processed)
edited Dec 17 '13 at 2:08
Michael Petrotta
51.4k12127171
answered Dec 17 '13 at 1:48
Kibrom Gebre
7819
edited Dec 17 '13 at 2:08
Michael Petrotta
51.4k12127171
edited Dec 17 '13 at 2:08
Michael Petrotta
51.4k12127171
edited Dec 17 '13 at 2:08
Michael Petrotta
51.4k12127171
51.4k12127171
answered Dec 17 '13 at 1:48
Kibrom Gebre
7819
answered Dec 17 '13 at 1:48
Kibrom Gebre
7819
answered Dec 17 '13 at 1:48
Kibrom Gebre
7819
7819
Even if I add '{' and '}' conditions to this algorithm, it doesn't apply to -{(}). We must check if after everyLASTbracket/parenthesis that opens, theSAMEmust close.
– Swanidhi
Oct 15 '15 at 6:26
add a comment |
Even if I add '{' and '}' conditions to this algorithm, it doesn't apply to -{(}). We must check if after everyLASTbracket/parenthesis that opens, theSAMEmust close.
– Swanidhi
Oct 15 '15 at 6:26
Even if I add '{' and '}' conditions to this algorithm, it doesn't apply to -
{(}). We must check if after every LAST bracket/parenthesis that opens, the SAME must close.– Swanidhi
Oct 15 '15 at 6:26
Even if I add '{' and '}' conditions to this algorithm, it doesn't apply to -
{(}). We must check if after every LAST bracket/parenthesis that opens, the SAME must close.– Swanidhi
Oct 15 '15 at 6:26
add a comment |
5
public static boolean isValidExpression(String expression) {
Map<Character, Character> openClosePair = new HashMap<Character, Character>();
openClosePair.put(')', '(');
openClosePair.put('}', '{');
openClosePair.put(']', '[');
Stack<Character> stack = new Stack<Character>();
for(char ch : expression.toCharArray()) {
if(openClosePair.containsKey(ch)) {
if(stack.pop() != openClosePair.get(ch)) {
return false;
}
} else if(openClosePair.values().contains(ch)) {
stack.push(ch);
}
}
return stack.isEmpty();
}
answered Mar 29 '16 at 12:20
ganesan dharmalingam
22435
1
Why should OP use your code? Could you expand your answer with an explanation?
– Zippy
Mar 29 '16 at 12:33
It returns the result immediately after found a illegal close. Uses Map which intern uses hashing technique and faster. Number of lines are less and easy to understand.
– ganesan dharmalingam
May 12 '16 at 7:39
openClosePair.values().contains(ch)be replacedopenClosePair.containsValue(ch)
– Tim
Jan 7 '17 at 23:14
your last pair is backwards change to (']','[')
– JesseBoyd
Apr 5 at 21:24
and you need to check if the stack is empty if(stack.empty() || stack.pop() != openClosedPair.get(ch)) { return false; }
– JesseBoyd
Apr 5 at 21:44
|
show 1 more comment
5
public static boolean isValidExpression(String expression) {
Map<Character, Character> openClosePair = new HashMap<Character, Character>();
openClosePair.put(')', '(');
openClosePair.put('}', '{');
openClosePair.put(']', '[');
Stack<Character> stack = new Stack<Character>();
for(char ch : expression.toCharArray()) {
if(openClosePair.containsKey(ch)) {
if(stack.pop() != openClosePair.get(ch)) {
return false;
}
} else if(openClosePair.values().contains(ch)) {
stack.push(ch);
}
}
return stack.isEmpty();
}
answered Mar 29 '16 at 12:20
ganesan dharmalingam
22435
1
Why should OP use your code? Could you expand your answer with an explanation?
– Zippy
Mar 29 '16 at 12:33
It returns the result immediately after found a illegal close. Uses Map which intern uses hashing technique and faster. Number of lines are less and easy to understand.
– ganesan dharmalingam
May 12 '16 at 7:39
openClosePair.values().contains(ch)be replacedopenClosePair.containsValue(ch)
– Tim
Jan 7 '17 at 23:14
your last pair is backwards change to (']','[')
– JesseBoyd
Apr 5 at 21:24
and you need to check if the stack is empty if(stack.empty() || stack.pop() != openClosedPair.get(ch)) { return false; }
– JesseBoyd
Apr 5 at 21:44
|
show 1 more comment
5
5
5
public static boolean isValidExpression(String expression) {
Map<Character, Character> openClosePair = new HashMap<Character, Character>();
openClosePair.put(')', '(');
openClosePair.put('}', '{');
openClosePair.put(']', '[');
Stack<Character> stack = new Stack<Character>();
for(char ch : expression.toCharArray()) {
if(openClosePair.containsKey(ch)) {
if(stack.pop() != openClosePair.get(ch)) {
return false;
}
} else if(openClosePair.values().contains(ch)) {
stack.push(ch);
}
}
return stack.isEmpty();
}
answered Mar 29 '16 at 12:20
ganesan dharmalingam
22435
public static boolean isValidExpression(String expression) {
Map<Character, Character> openClosePair = new HashMap<Character, Character>();
openClosePair.put(')', '(');
openClosePair.put('}', '{');
openClosePair.put(']', '[');
Stack<Character> stack = new Stack<Character>();
for(char ch : expression.toCharArray()) {
if(openClosePair.containsKey(ch)) {
if(stack.pop() != openClosePair.get(ch)) {
return false;
}
} else if(openClosePair.values().contains(ch)) {
stack.push(ch);
}
}
return stack.isEmpty();
}
answered Mar 29 '16 at 12:20
ganesan dharmalingam
22435
edited Jul 29 at 13:11
answered Mar 29 '16 at 12:20
ganesan dharmalingam
22435
answered Mar 29 '16 at 12:20
ganesan dharmalingam
22435
answered Mar 29 '16 at 12:20
ganesan dharmalingam
22435
22435
1
Why should OP use your code? Could you expand your answer with an explanation?
– Zippy
Mar 29 '16 at 12:33
It returns the result immediately after found a illegal close. Uses Map which intern uses hashing technique and faster. Number of lines are less and easy to understand.
– ganesan dharmalingam
May 12 '16 at 7:39
openClosePair.values().contains(ch)be replacedopenClosePair.containsValue(ch)
– Tim
Jan 7 '17 at 23:14
your last pair is backwards change to (']','[')
– JesseBoyd
Apr 5 at 21:24
and you need to check if the stack is empty if(stack.empty() || stack.pop() != openClosedPair.get(ch)) { return false; }
– JesseBoyd
Apr 5 at 21:44
|
show 1 more comment
1
Why should OP use your code? Could you expand your answer with an explanation?
– Zippy
Mar 29 '16 at 12:33
It returns the result immediately after found a illegal close. Uses Map which intern uses hashing technique and faster. Number of lines are less and easy to understand.
– ganesan dharmalingam
May 12 '16 at 7:39
openClosePair.values().contains(ch)be replacedopenClosePair.containsValue(ch)
– Tim
Jan 7 '17 at 23:14
your last pair is backwards change to (']','[')
– JesseBoyd
Apr 5 at 21:24
and you need to check if the stack is empty if(stack.empty() || stack.pop() != openClosedPair.get(ch)) { return false; }
– JesseBoyd
Apr 5 at 21:44
1
1
Why should OP use your code? Could you expand your answer with an explanation?
– Zippy
Mar 29 '16 at 12:33
Why should OP use your code? Could you expand your answer with an explanation?
– Zippy
Mar 29 '16 at 12:33
It returns the result immediately after found a illegal close. Uses Map which intern uses hashing technique and faster. Number of lines are less and easy to understand.
– ganesan dharmalingam
May 12 '16 at 7:39
It returns the result immediately after found a illegal close. Uses Map which intern uses hashing technique and faster. Number of lines are less and easy to understand.
– ganesan dharmalingam
May 12 '16 at 7:39
openClosePair.values().contains(ch) be replaced openClosePair.containsValue(ch)– Tim
Jan 7 '17 at 23:14
openClosePair.values().contains(ch) be replaced openClosePair.containsValue(ch)– Tim
Jan 7 '17 at 23:14
your last pair is backwards change to (']','[')
– JesseBoyd
Apr 5 at 21:24
your last pair is backwards change to (']','[')
– JesseBoyd
Apr 5 at 21:24
and you need to check if the stack is empty if(stack.empty() || stack.pop() != openClosedPair.get(ch)) { return false; }
– JesseBoyd
Apr 5 at 21:44
and you need to check if the stack is empty if(stack.empty() || stack.pop() != openClosedPair.get(ch)) { return false; }
– JesseBoyd
Apr 5 at 21:44
|
show 1 more comment
3
Actually, there is no need to check any cases "manually". You can just run the following algorithm:
Iterate over the given sequence. Start with an empty stack.
If the current char is an opening bracket, just push it to the stack.
If it's a closing bracket, check that the stack is not empty and the top element of the step is an appropriate opening bracket(that it is, matches this one). If it is not, report an error. Otherwise, pop the top element from the stack.
In the end, the sequence is correct iff the stack is empty.
Why is it correct? Here is a sketch of a proof: if this algorithm reported that the sequence is corrected, it had found a matching pair of all brackets. Thus, the sequence is indeed correct by definition. If it has reported an error:
If the stack was not empty in the end, the balance of opening and closing brackets is not zero. Thus, it is not a correct sequence.
If the stack was empty when we had to pop an element, the balance is off again.
If there was a wrong element on top of the stack, a pair of "wrong" brackets should match each other. It means that the sequence is not correct.
I have shown that:
If the algorithm has reported that the sequence is correct, it is correct.
If the algorithm has reported that the sequence is not correct, it is incorrect(note that I do not use the fact that there are no other cases except those that are mentioned in your question).
This two points imply that this algorithm works for all possible inputs.
answered Apr 1 '15 at 18:34
kraskevich
16.3k31938
1
The problem is not about correctly nesting parentheses alone.
– G. Bach
Apr 1 '15 at 18:52
Heads-up: your answer has been merged here from stackoverflow.com/questions/29396477/… - please adjust as needed.
– Shog9♦
Apr 3 '15 at 1:09
The implementation of the above algorithm in javascript can be found here (gist.github.com/sanketmaru/e83ce04100966bf46f6e8919a06c33ba). All possible inputs can be tested.
– Sanket
Aug 6 '17 at 16:41
add a comment |
3
Actually, there is no need to check any cases "manually". You can just run the following algorithm:
Iterate over the given sequence. Start with an empty stack.
If the current char is an opening bracket, just push it to the stack.
If it's a closing bracket, check that the stack is not empty and the top element of the step is an appropriate opening bracket(that it is, matches this one). If it is not, report an error. Otherwise, pop the top element from the stack.
In the end, the sequence is correct iff the stack is empty.
Why is it correct? Here is a sketch of a proof: if this algorithm reported that the sequence is corrected, it had found a matching pair of all brackets. Thus, the sequence is indeed correct by definition. If it has reported an error:
If the stack was not empty in the end, the balance of opening and closing brackets is not zero. Thus, it is not a correct sequence.
If the stack was empty when we had to pop an element, the balance is off again.
If there was a wrong element on top of the stack, a pair of "wrong" brackets should match each other. It means that the sequence is not correct.
I have shown that:
If the algorithm has reported that the sequence is correct, it is correct.
If the algorithm has reported that the sequence is not correct, it is incorrect(note that I do not use the fact that there are no other cases except those that are mentioned in your question).
This two points imply that this algorithm works for all possible inputs.
answered Apr 1 '15 at 18:34
kraskevich
16.3k31938
1
The problem is not about correctly nesting parentheses alone.
– G. Bach
Apr 1 '15 at 18:52
Heads-up: your answer has been merged here from stackoverflow.com/questions/29396477/… - please adjust as needed.
– Shog9♦
Apr 3 '15 at 1:09
The implementation of the above algorithm in javascript can be found here (gist.github.com/sanketmaru/e83ce04100966bf46f6e8919a06c33ba). All possible inputs can be tested.
– Sanket
Aug 6 '17 at 16:41
add a comment |
3
3
3
Actually, there is no need to check any cases "manually". You can just run the following algorithm:
Iterate over the given sequence. Start with an empty stack.
If the current char is an opening bracket, just push it to the stack.
If it's a closing bracket, check that the stack is not empty and the top element of the step is an appropriate opening bracket(that it is, matches this one). If it is not, report an error. Otherwise, pop the top element from the stack.
In the end, the sequence is correct iff the stack is empty.
Why is it correct? Here is a sketch of a proof: if this algorithm reported that the sequence is corrected, it had found a matching pair of all brackets. Thus, the sequence is indeed correct by definition. If it has reported an error:
If the stack was not empty in the end, the balance of opening and closing brackets is not zero. Thus, it is not a correct sequence.
If the stack was empty when we had to pop an element, the balance is off again.
If there was a wrong element on top of the stack, a pair of "wrong" brackets should match each other. It means that the sequence is not correct.
I have shown that:
If the algorithm has reported that the sequence is correct, it is correct.
If the algorithm has reported that the sequence is not correct, it is incorrect(note that I do not use the fact that there are no other cases except those that are mentioned in your question).
This two points imply that this algorithm works for all possible inputs.
answered Apr 1 '15 at 18:34
kraskevich
16.3k31938
Actually, there is no need to check any cases "manually". You can just run the following algorithm:
Iterate over the given sequence. Start with an empty stack.
If the current char is an opening bracket, just push it to the stack.
If it's a closing bracket, check that the stack is not empty and the top element of the step is an appropriate opening bracket(that it is, matches this one). If it is not, report an error. Otherwise, pop the top element from the stack.
In the end, the sequence is correct iff the stack is empty.
Why is it correct? Here is a sketch of a proof: if this algorithm reported that the sequence is corrected, it had found a matching pair of all brackets. Thus, the sequence is indeed correct by definition. If it has reported an error:
If the stack was not empty in the end, the balance of opening and closing brackets is not zero. Thus, it is not a correct sequence.
If the stack was empty when we had to pop an element, the balance is off again.
If there was a wrong element on top of the stack, a pair of "wrong" brackets should match each other. It means that the sequence is not correct.
I have shown that:
If the algorithm has reported that the sequence is correct, it is correct.
If the algorithm has reported that the sequence is not correct, it is incorrect(note that I do not use the fact that there are no other cases except those that are mentioned in your question).
This two points imply that this algorithm works for all possible inputs.
answered Apr 1 '15 at 18:34
kraskevich
16.3k31938
answered Apr 1 '15 at 18:34
kraskevich
16.3k31938
answered Apr 1 '15 at 18:34
kraskevich
16.3k31938
answered Apr 1 '15 at 18:34
kraskevich
16.3k31938
16.3k31938
1
The problem is not about correctly nesting parentheses alone.
– G. Bach
Apr 1 '15 at 18:52
Heads-up: your answer has been merged here from stackoverflow.com/questions/29396477/… - please adjust as needed.
– Shog9♦
Apr 3 '15 at 1:09
The implementation of the above algorithm in javascript can be found here (gist.github.com/sanketmaru/e83ce04100966bf46f6e8919a06c33ba). All possible inputs can be tested.
– Sanket
Aug 6 '17 at 16:41
add a comment |
1
The problem is not about correctly nesting parentheses alone.
– G. Bach
Apr 1 '15 at 18:52
Heads-up: your answer has been merged here from stackoverflow.com/questions/29396477/… - please adjust as needed.
– Shog9♦
Apr 3 '15 at 1:09
The implementation of the above algorithm in javascript can be found here (gist.github.com/sanketmaru/e83ce04100966bf46f6e8919a06c33ba). All possible inputs can be tested.
– Sanket
Aug 6 '17 at 16:41
1
1
The problem is not about correctly nesting parentheses alone.
– G. Bach
Apr 1 '15 at 18:52
The problem is not about correctly nesting parentheses alone.
– G. Bach
Apr 1 '15 at 18:52
Heads-up: your answer has been merged here from stackoverflow.com/questions/29396477/… - please adjust as needed.
– Shog9♦
Apr 3 '15 at 1:09
Heads-up: your answer has been merged here from stackoverflow.com/questions/29396477/… - please adjust as needed.
– Shog9♦
Apr 3 '15 at 1:09
The implementation of the above algorithm in javascript can be found here (gist.github.com/sanketmaru/e83ce04100966bf46f6e8919a06c33ba). All possible inputs can be tested.
– Sanket
Aug 6 '17 at 16:41
The implementation of the above algorithm in javascript can be found here (gist.github.com/sanketmaru/e83ce04100966bf46f6e8919a06c33ba). All possible inputs can be tested.
– Sanket
Aug 6 '17 at 16:41
add a comment |
2
public static boolean isBalanced(String s) {
Map<Character, Character> openClosePair = new HashMap<Character, Character>();
openClosePair.put('(', ')');
openClosePair.put('{', '}');
openClosePair.put('[', ']');
Stack<Character> stack = new Stack<Character>();
for (int i = 0; i < s.length(); i++) {
if (openClosePair.containsKey(s.charAt(i))) {
stack.push(s.charAt(i));
} else if ( openClosePair.containsValue(s.charAt(i))) {
if (stack.isEmpty())
return false;
if (openClosePair.get(stack.pop()) != s.charAt(i))
return false;
}
// ignore all other characters
}
return stack.isEmpty();
}
answered May 19 '16 at 11:25
deniswsrosa
522414
add a comment |
2
public static boolean isBalanced(String s) {
Map<Character, Character> openClosePair = new HashMap<Character, Character>();
openClosePair.put('(', ')');
openClosePair.put('{', '}');
openClosePair.put('[', ']');
Stack<Character> stack = new Stack<Character>();
for (int i = 0; i < s.length(); i++) {
if (openClosePair.containsKey(s.charAt(i))) {
stack.push(s.charAt(i));
} else if ( openClosePair.containsValue(s.charAt(i))) {
if (stack.isEmpty())
return false;
if (openClosePair.get(stack.pop()) != s.charAt(i))
return false;
}
// ignore all other characters
}
return stack.isEmpty();
}
answered May 19 '16 at 11:25
deniswsrosa
522414
add a comment |
2
2
2
public static boolean isBalanced(String s) {
Map<Character, Character> openClosePair = new HashMap<Character, Character>();
openClosePair.put('(', ')');
openClosePair.put('{', '}');
openClosePair.put('[', ']');
Stack<Character> stack = new Stack<Character>();
for (int i = 0; i < s.length(); i++) {
if (openClosePair.containsKey(s.charAt(i))) {
stack.push(s.charAt(i));
} else if ( openClosePair.containsValue(s.charAt(i))) {
if (stack.isEmpty())
return false;
if (openClosePair.get(stack.pop()) != s.charAt(i))
return false;
}
// ignore all other characters
}
return stack.isEmpty();
}
answered May 19 '16 at 11:25
deniswsrosa
522414
public static boolean isBalanced(String s) {
Map<Character, Character> openClosePair = new HashMap<Character, Character>();
openClosePair.put('(', ')');
openClosePair.put('{', '}');
openClosePair.put('[', ']');
Stack<Character> stack = new Stack<Character>();
for (int i = 0; i < s.length(); i++) {
if (openClosePair.containsKey(s.charAt(i))) {
stack.push(s.charAt(i));
} else if ( openClosePair.containsValue(s.charAt(i))) {
if (stack.isEmpty())
return false;
if (openClosePair.get(stack.pop()) != s.charAt(i))
return false;
}
// ignore all other characters
}
return stack.isEmpty();
}
answered May 19 '16 at 11:25
deniswsrosa
522414
answered May 19 '16 at 11:25
deniswsrosa
522414
answered May 19 '16 at 11:25
deniswsrosa
522414
answered May 19 '16 at 11:25
deniswsrosa
522414
522414
add a comment |
add a comment |
1
Algorithm is:
1)Create a stack
2)while(end of input is not reached)
i)if the character read is not a sysmbol to be balanced ,ignore it.
ii)if the character is {,[,( then push it to stack
iii)If it is a },),] then if
a)the stack is empty report an error(catch it) i.e not balanced
b)else pop the stack
iv)if element popped is not corresponding to opening sysmbol,then report error.
3) In the end,if stack is not empty report error else expression is balanced.
In Java code:
public class StackDemo {
public static void main(String args) throws Exception {
System.out.println("--Bracket checker--");
CharStackArray stack = new CharStackArray(10);
stack.balanceSymbol("[a+b{c+(e-f[p-q])}]") ;
stack.display();
}
}
class CharStackArray {
private char array;
private int top;
private int capacity;
public CharStackArray(int cap) {
capacity = cap;
array = new char[capacity];
top = -1;
}
public void push(char data) {
array[++top] = data;
}
public char pop() {
return array[top--];
}
public void display() {
for (int i = 0; i <= top; i++) {
System.out.print(array[i] + "->");
}
}
public char peek() throws Exception {
return array[top];
}
/*Call this method by passing a string expression*/
public void balanceSymbol(String str) {
try {
char arr = str.toCharArray();
for (int i = 0; i < arr.length; i++) {
if (arr[i] == '[' || arr[i] == '{' || arr[i] == '(')
push(arr[i]);
else if (arr[i] == '}' && peek() == '{')
pop();
else if (arr[i] == ']' && peek() == '[')
pop();
else if (arr[i] == ')' && peek() == '(')
pop();
}
if (isEmpty()) {
System.out.println("String is balanced");
} else {
System.out.println("String is not balanced");
}
} catch (Exception e) {
System.out.println("String not balanced");
}
}
public boolean isEmpty() {
return (top == -1);
}
}
Output:
--Bracket checker--
String is balanced
answered Jan 3 '16 at 22:45
Prateek Joshi
2,78812636
add a comment |
1
Algorithm is:
1)Create a stack
2)while(end of input is not reached)
i)if the character read is not a sysmbol to be balanced ,ignore it.
ii)if the character is {,[,( then push it to stack
iii)If it is a },),] then if
a)the stack is empty report an error(catch it) i.e not balanced
b)else pop the stack
iv)if element popped is not corresponding to opening sysmbol,then report error.
3) In the end,if stack is not empty report error else expression is balanced.
In Java code:
public class StackDemo {
public static void main(String args) throws Exception {
System.out.println("--Bracket checker--");
CharStackArray stack = new CharStackArray(10);
stack.balanceSymbol("[a+b{c+(e-f[p-q])}]") ;
stack.display();
}
}
class CharStackArray {
private char array;
private int top;
private int capacity;
public CharStackArray(int cap) {
capacity = cap;
array = new char[capacity];
top = -1;
}
public void push(char data) {
array[++top] = data;
}
public char pop() {
return array[top--];
}
public void display() {
for (int i = 0; i <= top; i++) {
System.out.print(array[i] + "->");
}
}
public char peek() throws Exception {
return array[top];
}
/*Call this method by passing a string expression*/
public void balanceSymbol(String str) {
try {
char arr = str.toCharArray();
for (int i = 0; i < arr.length; i++) {
if (arr[i] == '[' || arr[i] == '{' || arr[i] == '(')
push(arr[i]);
else if (arr[i] == '}' && peek() == '{')
pop();
else if (arr[i] == ']' && peek() == '[')
pop();
else if (arr[i] == ')' && peek() == '(')
pop();
}
if (isEmpty()) {
System.out.println("String is balanced");
} else {
System.out.println("String is not balanced");
}
} catch (Exception e) {
System.out.println("String not balanced");
}
}
public boolean isEmpty() {
return (top == -1);
}
}
Output:
--Bracket checker--
String is balanced
answered Jan 3 '16 at 22:45
Prateek Joshi
2,78812636
add a comment |
1
1
1
Algorithm is:
1)Create a stack
2)while(end of input is not reached)
i)if the character read is not a sysmbol to be balanced ,ignore it.
ii)if the character is {,[,( then push it to stack
iii)If it is a },),] then if
a)the stack is empty report an error(catch it) i.e not balanced
b)else pop the stack
iv)if element popped is not corresponding to opening sysmbol,then report error.
3) In the end,if stack is not empty report error else expression is balanced.
In Java code:
public class StackDemo {
public static void main(String args) throws Exception {
System.out.println("--Bracket checker--");
CharStackArray stack = new CharStackArray(10);
stack.balanceSymbol("[a+b{c+(e-f[p-q])}]") ;
stack.display();
}
}
class CharStackArray {
private char array;
private int top;
private int capacity;
public CharStackArray(int cap) {
capacity = cap;
array = new char[capacity];
top = -1;
}
public void push(char data) {
array[++top] = data;
}
public char pop() {
return array[top--];
}
public void display() {
for (int i = 0; i <= top; i++) {
System.out.print(array[i] + "->");
}
}
public char peek() throws Exception {
return array[top];
}
/*Call this method by passing a string expression*/
public void balanceSymbol(String str) {
try {
char arr = str.toCharArray();
for (int i = 0; i < arr.length; i++) {
if (arr[i] == '[' || arr[i] == '{' || arr[i] == '(')
push(arr[i]);
else if (arr[i] == '}' && peek() == '{')
pop();
else if (arr[i] == ']' && peek() == '[')
pop();
else if (arr[i] == ')' && peek() == '(')
pop();
}
if (isEmpty()) {
System.out.println("String is balanced");
} else {
System.out.println("String is not balanced");
}
} catch (Exception e) {
System.out.println("String not balanced");
}
}
public boolean isEmpty() {
return (top == -1);
}
}
Output:
--Bracket checker--
String is balanced
answered Jan 3 '16 at 22:45
Prateek Joshi
2,78812636
Algorithm is:
1)Create a stack
2)while(end of input is not reached)
i)if the character read is not a sysmbol to be balanced ,ignore it.
ii)if the character is {,[,( then push it to stack
iii)If it is a },),] then if
a)the stack is empty report an error(catch it) i.e not balanced
b)else pop the stack
iv)if element popped is not corresponding to opening sysmbol,then report error.
3) In the end,if stack is not empty report error else expression is balanced.
In Java code:
public class StackDemo {
public static void main(String args) throws Exception {
System.out.println("--Bracket checker--");
CharStackArray stack = new CharStackArray(10);
stack.balanceSymbol("[a+b{c+(e-f[p-q])}]") ;
stack.display();
}
}
class CharStackArray {
private char array;
private int top;
private int capacity;
public CharStackArray(int cap) {
capacity = cap;
array = new char[capacity];
top = -1;
}
public void push(char data) {
array[++top] = data;
}
public char pop() {
return array[top--];
}
public void display() {
for (int i = 0; i <= top; i++) {
System.out.print(array[i] + "->");
}
}
public char peek() throws Exception {
return array[top];
}
/*Call this method by passing a string expression*/
public void balanceSymbol(String str) {
try {
char arr = str.toCharArray();
for (int i = 0; i < arr.length; i++) {
if (arr[i] == '[' || arr[i] == '{' || arr[i] == '(')
push(arr[i]);
else if (arr[i] == '}' && peek() == '{')
pop();
else if (arr[i] == ']' && peek() == '[')
pop();
else if (arr[i] == ')' && peek() == '(')
pop();
}
if (isEmpty()) {
System.out.println("String is balanced");
} else {
System.out.println("String is not balanced");
}
} catch (Exception e) {
System.out.println("String not balanced");
}
}
public boolean isEmpty() {
return (top == -1);
}
}
Output:
--Bracket checker--
String is balanced
answered Jan 3 '16 at 22:45
Prateek Joshi
2,78812636
answered Jan 3 '16 at 22:45
Prateek Joshi
2,78812636
answered Jan 3 '16 at 22:45
Prateek Joshi
2,78812636
answered Jan 3 '16 at 22:45
Prateek Joshi
2,78812636
2,78812636
add a comment |
add a comment |
1
import java.util.*;
class StackDemo {
public static void main(String argh) {
boolean flag = true;
String str = "(()){}()";
int l = str.length();
flag = true;
Stack<String> st = new Stack<String>();
for (int i = 0; i < l; i++) {
String test = str.substring(i, i + 1);
if (test.equals("(")) {
st.push(test);
} else if (test.equals("{")) {
st.push(test);
} else if (test.equals("[")) {
st.push(test);
} else if (test.equals(")")) {
if (st.empty()) {
flag = false;
break;
}
if (st.peek().equals("(")) {
st.pop();
} else {
flag = false;
break;
}
} else if (test.equals("}")) {
if (st.empty()) {
flag = false;
break;
}
if (st.peek().equals("{")) {
st.pop();
} else {
flag = false;
break;
}
} else if (test.equals("]")) {
if (st.empty()) {
flag = false;
break;
}
if (st.peek().equals("[")) {
st.pop();
} else {
flag = false;
break;
}
}
}
if (flag && st.empty())
System.out.println("true");
else
System.out.println("false");
}
}
edited Jun 23 '16 at 20:46
Tony Babarino
2,21641734
answered Jun 23 '16 at 20:14
Ashish Jadhav
112
1
While this code snippet may solve the question, including an explanation really helps to improve the quality of your post. Remember that you are answering the question for readers in the future, and those people might not know the reasons for your code suggestion.
– Tony Babarino
Jun 23 '16 at 20:31
add a comment |
1
import java.util.*;
class StackDemo {
public static void main(String argh) {
boolean flag = true;
String str = "(()){}()";
int l = str.length();
flag = true;
Stack<String> st = new Stack<String>();
for (int i = 0; i < l; i++) {
String test = str.substring(i, i + 1);
if (test.equals("(")) {
st.push(test);
} else if (test.equals("{")) {
st.push(test);
} else if (test.equals("[")) {
st.push(test);
} else if (test.equals(")")) {
if (st.empty()) {
flag = false;
break;
}
if (st.peek().equals("(")) {
st.pop();
} else {
flag = false;
break;
}
} else if (test.equals("}")) {
if (st.empty()) {
flag = false;
break;
}
if (st.peek().equals("{")) {
st.pop();
} else {
flag = false;
break;
}
} else if (test.equals("]")) {
if (st.empty()) {
flag = false;
break;
}
if (st.peek().equals("[")) {
st.pop();
} else {
flag = false;
break;
}
}
}
if (flag && st.empty())
System.out.println("true");
else
System.out.println("false");
}
}
edited Jun 23 '16 at 20:46
Tony Babarino
2,21641734
answered Jun 23 '16 at 20:14
Ashish Jadhav
112
1
While this code snippet may solve the question, including an explanation really helps to improve the quality of your post. Remember that you are answering the question for readers in the future, and those people might not know the reasons for your code suggestion.
– Tony Babarino
Jun 23 '16 at 20:31
add a comment |
1
1
1
import java.util.*;
class StackDemo {
public static void main(String argh) {
boolean flag = true;
String str = "(()){}()";
int l = str.length();
flag = true;
Stack<String> st = new Stack<String>();
for (int i = 0; i < l; i++) {
String test = str.substring(i, i + 1);
if (test.equals("(")) {
st.push(test);
} else if (test.equals("{")) {
st.push(test);
} else if (test.equals("[")) {
st.push(test);
} else if (test.equals(")")) {
if (st.empty()) {
flag = false;
break;
}
if (st.peek().equals("(")) {
st.pop();
} else {
flag = false;
break;
}
} else if (test.equals("}")) {
if (st.empty()) {
flag = false;
break;
}
if (st.peek().equals("{")) {
st.pop();
} else {
flag = false;
break;
}
} else if (test.equals("]")) {
if (st.empty()) {
flag = false;
break;
}
if (st.peek().equals("[")) {
st.pop();
} else {
flag = false;
break;
}
}
}
if (flag && st.empty())
System.out.println("true");
else
System.out.println("false");
}
}
edited Jun 23 '16 at 20:46
Tony Babarino
2,21641734
answered Jun 23 '16 at 20:14
Ashish Jadhav
112
import java.util.*;
class StackDemo {
public static void main(String argh) {
boolean flag = true;
String str = "(()){}()";
int l = str.length();
flag = true;
Stack<String> st = new Stack<String>();
for (int i = 0; i < l; i++) {
String test = str.substring(i, i + 1);
if (test.equals("(")) {
st.push(test);
} else if (test.equals("{")) {
st.push(test);
} else if (test.equals("[")) {
st.push(test);
} else if (test.equals(")")) {
if (st.empty()) {
flag = false;
break;
}
if (st.peek().equals("(")) {
st.pop();
} else {
flag = false;
break;
}
} else if (test.equals("}")) {
if (st.empty()) {
flag = false;
break;
}
if (st.peek().equals("{")) {
st.pop();
} else {
flag = false;
break;
}
} else if (test.equals("]")) {
if (st.empty()) {
flag = false;
break;
}
if (st.peek().equals("[")) {
st.pop();
} else {
flag = false;
break;
}
}
}
if (flag && st.empty())
System.out.println("true");
else
System.out.println("false");
}
}
edited Jun 23 '16 at 20:46
Tony Babarino
2,21641734
answered Jun 23 '16 at 20:14
Ashish Jadhav
112
edited Jun 23 '16 at 20:46
Tony Babarino
2,21641734
edited Jun 23 '16 at 20:46
Tony Babarino
2,21641734
edited Jun 23 '16 at 20:46
Tony Babarino
2,21641734
2,21641734
answered Jun 23 '16 at 20:14
Ashish Jadhav
112
answered Jun 23 '16 at 20:14
Ashish Jadhav
112
answered Jun 23 '16 at 20:14
Ashish Jadhav
112
112
1
While this code snippet may solve the question, including an explanation really helps to improve the quality of your post. Remember that you are answering the question for readers in the future, and those people might not know the reasons for your code suggestion.
– Tony Babarino
Jun 23 '16 at 20:31
add a comment |
1
While this code snippet may solve the question, including an explanation really helps to improve the quality of your post. Remember that you are answering the question for readers in the future, and those people might not know the reasons for your code suggestion.
– Tony Babarino
Jun 23 '16 at 20:31
1
1
While this code snippet may solve the question, including an explanation really helps to improve the quality of your post. Remember that you are answering the question for readers in the future, and those people might not know the reasons for your code suggestion.
– Tony Babarino
Jun 23 '16 at 20:31
While this code snippet may solve the question, including an explanation really helps to improve the quality of your post. Remember that you are answering the question for readers in the future, and those people might not know the reasons for your code suggestion.
– Tony Babarino
Jun 23 '16 at 20:31
add a comment |
1
Ganesan's answer above is not correct and StackOverflow is not letting me comment or Edit his post. So below is the correct answer. Ganesan has an incorrect facing "[" and is missing the stack isEmpty() check.
The below code will return true if the braces are properly matching.
public static boolean isValidExpression(String expression) {
Map<Character, Character> openClosePair = new HashMap<Character, Character>();
openClosePair.put(')', '(');
openClosePair.put('}', '{');
openClosePair.put(']', '[');
Stack<Character> stack = new Stack<Character>();
for(char ch : expression.toCharArray()) {
if(openClosePair.containsKey(ch)) {
if(stack.isEmpty() || stack.pop() != openClosePair.get(ch)) {
return false;
}
} else if(openClosePair.values().contains(ch)) {
stack.push(ch);
}
}
return stack.isEmpty();
}
answered May 5 '17 at 15:43
Jared
7117
add a comment |
1
Ganesan's answer above is not correct and StackOverflow is not letting me comment or Edit his post. So below is the correct answer. Ganesan has an incorrect facing "[" and is missing the stack isEmpty() check.
The below code will return true if the braces are properly matching.
public static boolean isValidExpression(String expression) {
Map<Character, Character> openClosePair = new HashMap<Character, Character>();
openClosePair.put(')', '(');
openClosePair.put('}', '{');
openClosePair.put(']', '[');
Stack<Character> stack = new Stack<Character>();
for(char ch : expression.toCharArray()) {
if(openClosePair.containsKey(ch)) {
if(stack.isEmpty() || stack.pop() != openClosePair.get(ch)) {
return false;
}
} else if(openClosePair.values().contains(ch)) {
stack.push(ch);
}
}
return stack.isEmpty();
}
answered May 5 '17 at 15:43
Jared
7117
add a comment |
1
1
1
Ganesan's answer above is not correct and StackOverflow is not letting me comment or Edit his post. So below is the correct answer. Ganesan has an incorrect facing "[" and is missing the stack isEmpty() check.
The below code will return true if the braces are properly matching.
public static boolean isValidExpression(String expression) {
Map<Character, Character> openClosePair = new HashMap<Character, Character>();
openClosePair.put(')', '(');
openClosePair.put('}', '{');
openClosePair.put(']', '[');
Stack<Character> stack = new Stack<Character>();
for(char ch : expression.toCharArray()) {
if(openClosePair.containsKey(ch)) {
if(stack.isEmpty() || stack.pop() != openClosePair.get(ch)) {
return false;
}
} else if(openClosePair.values().contains(ch)) {
stack.push(ch);
}
}
return stack.isEmpty();
}
answered May 5 '17 at 15:43
Jared
7117
Ganesan's answer above is not correct and StackOverflow is not letting me comment or Edit his post. So below is the correct answer. Ganesan has an incorrect facing "[" and is missing the stack isEmpty() check.
The below code will return true if the braces are properly matching.
public static boolean isValidExpression(String expression) {
Map<Character, Character> openClosePair = new HashMap<Character, Character>();
openClosePair.put(')', '(');
openClosePair.put('}', '{');
openClosePair.put(']', '[');
Stack<Character> stack = new Stack<Character>();
for(char ch : expression.toCharArray()) {
if(openClosePair.containsKey(ch)) {
if(stack.isEmpty() || stack.pop() != openClosePair.get(ch)) {
return false;
}
} else if(openClosePair.values().contains(ch)) {
stack.push(ch);
}
}
return stack.isEmpty();
}
answered May 5 '17 at 15:43
Jared
7117
answered May 5 '17 at 15:43
Jared
7117
answered May 5 '17 at 15:43
Jared
7117
answered May 5 '17 at 15:43
Jared
7117
7117
add a comment |
add a comment |
1
Optimized implementation using Stacks and Switch statement:
public class JavaStack {
public static void main(String args) {
Scanner sc = new Scanner(System.in);
Stack<Character> s = new Stack<Character>();
while (sc.hasNext()) {
String input = sc.next();
for (int i = 0; i < input.length(); i++) {
char c = input.charAt(i);
switch (c) {
case '(':
s.push(c); break;
case '[':
s.push(c); break;
case '{':
s.push(c); break;
case ')':
if (!s.isEmpty() && s.peek().equals('(')) {
s.pop();
} else {
s.push(c);
} break;
case ']':
if (!s.isEmpty() && s.peek().equals('[')) {
s.pop();
} else {
s.push(c);
} break;
case '}':
if (!s.isEmpty() && s.peek().equals('{')) {
s.pop();
} else {
s.push(c);
} break;
default:
s.push('x'); break;
}
}
if (s.empty()) {
System.out.println("true");
} else {
System.out.println("false");
s.clear();
}
}
} }
Cheers !
answered Nov 11 at 18:21
Leo
112
add a comment |
1
Optimized implementation using Stacks and Switch statement:
public class JavaStack {
public static void main(String args) {
Scanner sc = new Scanner(System.in);
Stack<Character> s = new Stack<Character>();
while (sc.hasNext()) {
String input = sc.next();
for (int i = 0; i < input.length(); i++) {
char c = input.charAt(i);
switch (c) {
case '(':
s.push(c); break;
case '[':
s.push(c); break;
case '{':
s.push(c); break;
case ')':
if (!s.isEmpty() && s.peek().equals('(')) {
s.pop();
} else {
s.push(c);
} break;
case ']':
if (!s.isEmpty() && s.peek().equals('[')) {
s.pop();
} else {
s.push(c);
} break;
case '}':
if (!s.isEmpty() && s.peek().equals('{')) {
s.pop();
} else {
s.push(c);
} break;
default:
s.push('x'); break;
}
}
if (s.empty()) {
System.out.println("true");
} else {
System.out.println("false");
s.clear();
}
}
} }
Cheers !
answered Nov 11 at 18:21
Leo
112
add a comment |
1
1
1
Optimized implementation using Stacks and Switch statement:
public class JavaStack {
public static void main(String args) {
Scanner sc = new Scanner(System.in);
Stack<Character> s = new Stack<Character>();
while (sc.hasNext()) {
String input = sc.next();
for (int i = 0; i < input.length(); i++) {
char c = input.charAt(i);
switch (c) {
case '(':
s.push(c); break;
case '[':
s.push(c); break;
case '{':
s.push(c); break;
case ')':
if (!s.isEmpty() && s.peek().equals('(')) {
s.pop();
} else {
s.push(c);
} break;
case ']':
if (!s.isEmpty() && s.peek().equals('[')) {
s.pop();
} else {
s.push(c);
} break;
case '}':
if (!s.isEmpty() && s.peek().equals('{')) {
s.pop();
} else {
s.push(c);
} break;
default:
s.push('x'); break;
}
}
if (s.empty()) {
System.out.println("true");
} else {
System.out.println("false");
s.clear();
}
}
} }
Cheers !
answered Nov 11 at 18:21
Leo
112
Optimized implementation using Stacks and Switch statement:
public class JavaStack {
public static void main(String args) {
Scanner sc = new Scanner(System.in);
Stack<Character> s = new Stack<Character>();
while (sc.hasNext()) {
String input = sc.next();
for (int i = 0; i < input.length(); i++) {
char c = input.charAt(i);
switch (c) {
case '(':
s.push(c); break;
case '[':
s.push(c); break;
case '{':
s.push(c); break;
case ')':
if (!s.isEmpty() && s.peek().equals('(')) {
s.pop();
} else {
s.push(c);
} break;
case ']':
if (!s.isEmpty() && s.peek().equals('[')) {
s.pop();
} else {
s.push(c);
} break;
case '}':
if (!s.isEmpty() && s.peek().equals('{')) {
s.pop();
} else {
s.push(c);
} break;
default:
s.push('x'); break;
}
}
if (s.empty()) {
System.out.println("true");
} else {
System.out.println("false");
s.clear();
}
}
} }
Cheers !
answered Nov 11 at 18:21
Leo
112
edited Nov 11 at 18:58
answered Nov 11 at 18:21
Leo
112
answered Nov 11 at 18:21
Leo
112
answered Nov 11 at 18:21
Leo
112
112
add a comment |
add a comment |
0
//basic code non strack algorithm just started learning java ignore space and time.
/// {[()]}{}
// {[( -a -> }]) -b -> replace a(]}) -> reverse a( }]))->
//Split string to substring {[()]}, next , next , next{}
public class testbrackets {
static String stringfirst;
static String stringsecond;
static int open = 0;
public static void main(String args) {
splitstring("(()){}()");
}
static void splitstring(String str){
int len = str.length();
for(int i=0;i<=len-1;i++){
stringfirst="";
stringsecond="";
System.out.println("loop starttttttt");
char a = str.charAt(i);
if(a=='{'||a=='['||a=='(')
{
open = open+1;
continue;
}
if(a=='}'||a==']'||a==')'){
if(open==0){
System.out.println(open+"started with closing brace");
return;
}
String stringfirst=str.substring(i-open, i);
System.out.println("stringfirst"+stringfirst);
String stringsecond=str.substring(i, i+open);
System.out.println("stringsecond"+stringsecond);
replace(stringfirst, stringsecond);
}
i=(i+open)-1;
open=0;
System.out.println(i);
}
}
static void replace(String stringfirst, String stringsecond){
stringfirst = stringfirst.replace('{', '}');
stringfirst = stringfirst.replace('(', ')');
stringfirst = stringfirst.replace('[', ']');
StringBuilder stringfirst1 = new StringBuilder(stringfirst);
stringfirst = stringfirst1.reverse().toString();
System.out.println("stringfirst"+stringfirst);
System.out.println("stringsecond"+stringsecond);
if(stringfirst.equals(stringsecond)){
System.out.println("pass");
}
else{
System.out.println("fail");
System.exit(0);
}
}
}
answered Apr 19 '15 at 17:54
sai tvs
1
This is quite different to the code posted by the OP. It would be very helpful to others if you could explain it a bit so we can see what your train of thought was.
– Wai Ha Lee
Apr 19 '15 at 18:00
Plus it's way too long. you should also refrain as much as possible from printing from within methods.
– Amos Bordowitz
Sep 16 '15 at 10:14
add a comment |
0
//basic code non strack algorithm just started learning java ignore space and time.
/// {[()]}{}
// {[( -a -> }]) -b -> replace a(]}) -> reverse a( }]))->
//Split string to substring {[()]}, next , next , next{}
public class testbrackets {
static String stringfirst;
static String stringsecond;
static int open = 0;
public static void main(String args) {
splitstring("(()){}()");
}
static void splitstring(String str){
int len = str.length();
for(int i=0;i<=len-1;i++){
stringfirst="";
stringsecond="";
System.out.println("loop starttttttt");
char a = str.charAt(i);
if(a=='{'||a=='['||a=='(')
{
open = open+1;
continue;
}
if(a=='}'||a==']'||a==')'){
if(open==0){
System.out.println(open+"started with closing brace");
return;
}
String stringfirst=str.substring(i-open, i);
System.out.println("stringfirst"+stringfirst);
String stringsecond=str.substring(i, i+open);
System.out.println("stringsecond"+stringsecond);
replace(stringfirst, stringsecond);
}
i=(i+open)-1;
open=0;
System.out.println(i);
}
}
static void replace(String stringfirst, String stringsecond){
stringfirst = stringfirst.replace('{', '}');
stringfirst = stringfirst.replace('(', ')');
stringfirst = stringfirst.replace('[', ']');
StringBuilder stringfirst1 = new StringBuilder(stringfirst);
stringfirst = stringfirst1.reverse().toString();
System.out.println("stringfirst"+stringfirst);
System.out.println("stringsecond"+stringsecond);
if(stringfirst.equals(stringsecond)){
System.out.println("pass");
}
else{
System.out.println("fail");
System.exit(0);
}
}
}
answered Apr 19 '15 at 17:54
sai tvs
1
This is quite different to the code posted by the OP. It would be very helpful to others if you could explain it a bit so we can see what your train of thought was.
– Wai Ha Lee
Apr 19 '15 at 18:00
Plus it's way too long. you should also refrain as much as possible from printing from within methods.
– Amos Bordowitz
Sep 16 '15 at 10:14
add a comment |
0
0
0
//basic code non strack algorithm just started learning java ignore space and time.
/// {[()]}{}
// {[( -a -> }]) -b -> replace a(]}) -> reverse a( }]))->
//Split string to substring {[()]}, next , next , next{}
public class testbrackets {
static String stringfirst;
static String stringsecond;
static int open = 0;
public static void main(String args) {
splitstring("(()){}()");
}
static void splitstring(String str){
int len = str.length();
for(int i=0;i<=len-1;i++){
stringfirst="";
stringsecond="";
System.out.println("loop starttttttt");
char a = str.charAt(i);
if(a=='{'||a=='['||a=='(')
{
open = open+1;
continue;
}
if(a=='}'||a==']'||a==')'){
if(open==0){
System.out.println(open+"started with closing brace");
return;
}
String stringfirst=str.substring(i-open, i);
System.out.println("stringfirst"+stringfirst);
String stringsecond=str.substring(i, i+open);
System.out.println("stringsecond"+stringsecond);
replace(stringfirst, stringsecond);
}
i=(i+open)-1;
open=0;
System.out.println(i);
}
}
static void replace(String stringfirst, String stringsecond){
stringfirst = stringfirst.replace('{', '}');
stringfirst = stringfirst.replace('(', ')');
stringfirst = stringfirst.replace('[', ']');
StringBuilder stringfirst1 = new StringBuilder(stringfirst);
stringfirst = stringfirst1.reverse().toString();
System.out.println("stringfirst"+stringfirst);
System.out.println("stringsecond"+stringsecond);
if(stringfirst.equals(stringsecond)){
System.out.println("pass");
}
else{
System.out.println("fail");
System.exit(0);
}
}
}
answered Apr 19 '15 at 17:54
sai tvs
1
//basic code non strack algorithm just started learning java ignore space and time.
/// {[()]}{}
// {[( -a -> }]) -b -> replace a(]}) -> reverse a( }]))->
//Split string to substring {[()]}, next , next , next{}
public class testbrackets {
static String stringfirst;
static String stringsecond;
static int open = 0;
public static void main(String args) {
splitstring("(()){}()");
}
static void splitstring(String str){
int len = str.length();
for(int i=0;i<=len-1;i++){
stringfirst="";
stringsecond="";
System.out.println("loop starttttttt");
char a = str.charAt(i);
if(a=='{'||a=='['||a=='(')
{
open = open+1;
continue;
}
if(a=='}'||a==']'||a==')'){
if(open==0){
System.out.println(open+"started with closing brace");
return;
}
String stringfirst=str.substring(i-open, i);
System.out.println("stringfirst"+stringfirst);
String stringsecond=str.substring(i, i+open);
System.out.println("stringsecond"+stringsecond);
replace(stringfirst, stringsecond);
}
i=(i+open)-1;
open=0;
System.out.println(i);
}
}
static void replace(String stringfirst, String stringsecond){
stringfirst = stringfirst.replace('{', '}');
stringfirst = stringfirst.replace('(', ')');
stringfirst = stringfirst.replace('[', ']');
StringBuilder stringfirst1 = new StringBuilder(stringfirst);
stringfirst = stringfirst1.reverse().toString();
System.out.println("stringfirst"+stringfirst);
System.out.println("stringsecond"+stringsecond);
if(stringfirst.equals(stringsecond)){
System.out.println("pass");
}
else{
System.out.println("fail");
System.exit(0);
}
}
}
answered Apr 19 '15 at 17:54
sai tvs
1
answered Apr 19 '15 at 17:54
sai tvs
1
answered Apr 19 '15 at 17:54
sai tvs
1
answered Apr 19 '15 at 17:54
sai tvs
1
1
This is quite different to the code posted by the OP. It would be very helpful to others if you could explain it a bit so we can see what your train of thought was.
– Wai Ha Lee
Apr 19 '15 at 18:00
Plus it's way too long. you should also refrain as much as possible from printing from within methods.
– Amos Bordowitz
Sep 16 '15 at 10:14
add a comment |
This is quite different to the code posted by the OP. It would be very helpful to others if you could explain it a bit so we can see what your train of thought was.
– Wai Ha Lee
Apr 19 '15 at 18:00
Plus it's way too long. you should also refrain as much as possible from printing from within methods.
– Amos Bordowitz
Sep 16 '15 at 10:14
This is quite different to the code posted by the OP. It would be very helpful to others if you could explain it a bit so we can see what your train of thought was.
– Wai Ha Lee
Apr 19 '15 at 18:00
This is quite different to the code posted by the OP. It would be very helpful to others if you could explain it a bit so we can see what your train of thought was.
– Wai Ha Lee
Apr 19 '15 at 18:00
Plus it's way too long. you should also refrain as much as possible from printing from within methods.
– Amos Bordowitz
Sep 16 '15 at 10:14
Plus it's way too long. you should also refrain as much as possible from printing from within methods.
– Amos Bordowitz
Sep 16 '15 at 10:14
add a comment |
0
import java.util.Stack;
class Demo
{
char c;
public boolean checkParan(String word)
{
Stack<Character> sta = new Stack<Character>();
for(int i=0;i<word.length();i++)
{
c=word.charAt(i);
if(c=='(')
{
sta.push(c);
System.out.println("( Pushed into the stack");
}
else if(c=='{')
{
sta.push(c);
System.out.println("( Pushed into the stack");
}
else if(c==')')
{
if(sta.empty())
{
System.out.println("Stack is Empty");
return false;
}
else if(sta.peek()=='(')
{
sta.pop();
System.out.println(" ) is poped from the Stack");
}
else if(sta.peek()=='(' && sta.empty())
{
System.out.println("Stack is Empty");
return false;
}
}
else if(c=='}')
{
if(sta.empty())
{
System.out.println("Stack is Empty");
return false;
}
else if(sta.peek()=='{')
{
sta.pop();
System.out.println(" } is poped from the Stack");
}
}
else if(c=='(')
{
if(sta.empty())
{
System.out.println("Stack is empty only ( parenthesis in Stack ");
}
}
}
// System.out.print("The top element is : "+sta.peek());
return sta.empty();
}
}
public class ParaenthesisChehck {
/**
* @param args the command line arguments
*/
public static void main(String args) {
// TODO code application logic here
Demo d1= new Demo();
// d1.checkParan(" ");
// d1.checkParan("{}");
//d1.checkParan("()");
//d1.checkParan("{()}");
// d1.checkParan("{123}");
d1.checkParan("{{{}}");
}
}
edited Nov 20 '15 at 10:55
gstackoverflow
9,66644164349
answered Nov 13 '15 at 20:34
Pooja Gandhi
11
add a comment |
0
import java.util.Stack;
class Demo
{
char c;
public boolean checkParan(String word)
{
Stack<Character> sta = new Stack<Character>();
for(int i=0;i<word.length();i++)
{
c=word.charAt(i);
if(c=='(')
{
sta.push(c);
System.out.println("( Pushed into the stack");
}
else if(c=='{')
{
sta.push(c);
System.out.println("( Pushed into the stack");
}
else if(c==')')
{
if(sta.empty())
{
System.out.println("Stack is Empty");
return false;
}
else if(sta.peek()=='(')
{
sta.pop();
System.out.println(" ) is poped from the Stack");
}
else if(sta.peek()=='(' && sta.empty())
{
System.out.println("Stack is Empty");
return false;
}
}
else if(c=='}')
{
if(sta.empty())
{
System.out.println("Stack is Empty");
return false;
}
else if(sta.peek()=='{')
{
sta.pop();
System.out.println(" } is poped from the Stack");
}
}
else if(c=='(')
{
if(sta.empty())
{
System.out.println("Stack is empty only ( parenthesis in Stack ");
}
}
}
// System.out.print("The top element is : "+sta.peek());
return sta.empty();
}
}
public class ParaenthesisChehck {
/**
* @param args the command line arguments
*/
public static void main(String args) {
// TODO code application logic here
Demo d1= new Demo();
// d1.checkParan(" ");
// d1.checkParan("{}");
//d1.checkParan("()");
//d1.checkParan("{()}");
// d1.checkParan("{123}");
d1.checkParan("{{{}}");
}
}
edited Nov 20 '15 at 10:55
gstackoverflow
9,66644164349
answered Nov 13 '15 at 20:34
Pooja Gandhi
11
add a comment |
0
0
0
import java.util.Stack;
class Demo
{
char c;
public boolean checkParan(String word)
{
Stack<Character> sta = new Stack<Character>();
for(int i=0;i<word.length();i++)
{
c=word.charAt(i);
if(c=='(')
{
sta.push(c);
System.out.println("( Pushed into the stack");
}
else if(c=='{')
{
sta.push(c);
System.out.println("( Pushed into the stack");
}
else if(c==')')
{
if(sta.empty())
{
System.out.println("Stack is Empty");
return false;
}
else if(sta.peek()=='(')
{
sta.pop();
System.out.println(" ) is poped from the Stack");
}
else if(sta.peek()=='(' && sta.empty())
{
System.out.println("Stack is Empty");
return false;
}
}
else if(c=='}')
{
if(sta.empty())
{
System.out.println("Stack is Empty");
return false;
}
else if(sta.peek()=='{')
{
sta.pop();
System.out.println(" } is poped from the Stack");
}
}
else if(c=='(')
{
if(sta.empty())
{
System.out.println("Stack is empty only ( parenthesis in Stack ");
}
}
}
// System.out.print("The top element is : "+sta.peek());
return sta.empty();
}
}
public class ParaenthesisChehck {
/**
* @param args the command line arguments
*/
public static void main(String args) {
// TODO code application logic here
Demo d1= new Demo();
// d1.checkParan(" ");
// d1.checkParan("{}");
//d1.checkParan("()");
//d1.checkParan("{()}");
// d1.checkParan("{123}");
d1.checkParan("{{{}}");
}
}
edited Nov 20 '15 at 10:55
gstackoverflow
9,66644164349
answered Nov 13 '15 at 20:34
Pooja Gandhi
11
import java.util.Stack;
class Demo
{
char c;
public boolean checkParan(String word)
{
Stack<Character> sta = new Stack<Character>();
for(int i=0;i<word.length();i++)
{
c=word.charAt(i);
if(c=='(')
{
sta.push(c);
System.out.println("( Pushed into the stack");
}
else if(c=='{')
{
sta.push(c);
System.out.println("( Pushed into the stack");
}
else if(c==')')
{
if(sta.empty())
{
System.out.println("Stack is Empty");
return false;
}
else if(sta.peek()=='(')
{
sta.pop();
System.out.println(" ) is poped from the Stack");
}
else if(sta.peek()=='(' && sta.empty())
{
System.out.println("Stack is Empty");
return false;
}
}
else if(c=='}')
{
if(sta.empty())
{
System.out.println("Stack is Empty");
return false;
}
else if(sta.peek()=='{')
{
sta.pop();
System.out.println(" } is poped from the Stack");
}
}
else if(c=='(')
{
if(sta.empty())
{
System.out.println("Stack is empty only ( parenthesis in Stack ");
}
}
}
// System.out.print("The top element is : "+sta.peek());
return sta.empty();
}
}
public class ParaenthesisChehck {
/**
* @param args the command line arguments
*/
public static void main(String args) {
// TODO code application logic here
Demo d1= new Demo();
// d1.checkParan(" ");
// d1.checkParan("{}");
//d1.checkParan("()");
//d1.checkParan("{()}");
// d1.checkParan("{123}");
d1.checkParan("{{{}}");
}
}
edited Nov 20 '15 at 10:55
gstackoverflow
9,66644164349
answered Nov 13 '15 at 20:34
Pooja Gandhi
11
edited Nov 20 '15 at 10:55
gstackoverflow
9,66644164349
edited Nov 20 '15 at 10:55
gstackoverflow
9,66644164349
edited Nov 20 '15 at 10:55
gstackoverflow
9,66644164349
9,66644164349
answered Nov 13 '15 at 20:34
Pooja Gandhi
11
answered Nov 13 '15 at 20:34
Pooja Gandhi
11
answered Nov 13 '15 at 20:34
Pooja Gandhi
11
11
add a comment |
add a comment |
0
I tried this using javascript below is the result.
function bracesChecker(str) {
if(!str) {
return true;
}
var openingBraces = ['{', '[', '('];
var closingBraces = ['}', ']', ')'];
var stack = ;
var openIndex;
var closeIndex;
//check for opening Braces in the val
for (var i = 0, len = str.length; i < len; i++) {
openIndex = openingBraces.indexOf(str[i]);
closeIndex = closingBraces.indexOf(str[i]);
if(openIndex !== -1) {
stack.push(str[i]);
}
if(closeIndex !== -1) {
if(openingBraces[closeIndex] === stack[stack.length-1]) {
stack.pop();
} else {
return false;
}
}
}
if(stack.length === 0) {
return true;
} else {
return false;
}
}
var testStrings = [
'',
'test',
'{{()()}()}()',
'{test{[test]}}',
'{test{[test]}',
'{test{(yo)[test]}}',
'test{[test]}}',
'te()st{[test]}',
'te()st{[test'
];
testStrings.forEach(val => console.log(`${val} => ${bracesChecker(val)}`));
answered Dec 30 '15 at 8:58
Yalamber
4,068104571
add a comment |
0
I tried this using javascript below is the result.
function bracesChecker(str) {
if(!str) {
return true;
}
var openingBraces = ['{', '[', '('];
var closingBraces = ['}', ']', ')'];
var stack = ;
var openIndex;
var closeIndex;
//check for opening Braces in the val
for (var i = 0, len = str.length; i < len; i++) {
openIndex = openingBraces.indexOf(str[i]);
closeIndex = closingBraces.indexOf(str[i]);
if(openIndex !== -1) {
stack.push(str[i]);
}
if(closeIndex !== -1) {
if(openingBraces[closeIndex] === stack[stack.length-1]) {
stack.pop();
} else {
return false;
}
}
}
if(stack.length === 0) {
return true;
} else {
return false;
}
}
var testStrings = [
'',
'test',
'{{()()}()}()',
'{test{[test]}}',
'{test{[test]}',
'{test{(yo)[test]}}',
'test{[test]}}',
'te()st{[test]}',
'te()st{[test'
];
testStrings.forEach(val => console.log(`${val} => ${bracesChecker(val)}`));
answered Dec 30 '15 at 8:58
Yalamber
4,068104571
add a comment |
0
0
0
I tried this using javascript below is the result.
function bracesChecker(str) {
if(!str) {
return true;
}
var openingBraces = ['{', '[', '('];
var closingBraces = ['}', ']', ')'];
var stack = ;
var openIndex;
var closeIndex;
//check for opening Braces in the val
for (var i = 0, len = str.length; i < len; i++) {
openIndex = openingBraces.indexOf(str[i]);
closeIndex = closingBraces.indexOf(str[i]);
if(openIndex !== -1) {
stack.push(str[i]);
}
if(closeIndex !== -1) {
if(openingBraces[closeIndex] === stack[stack.length-1]) {
stack.pop();
} else {
return false;
}
}
}
if(stack.length === 0) {
return true;
} else {
return false;
}
}
var testStrings = [
'',
'test',
'{{()()}()}()',
'{test{[test]}}',
'{test{[test]}',
'{test{(yo)[test]}}',
'test{[test]}}',
'te()st{[test]}',
'te()st{[test'
];
testStrings.forEach(val => console.log(`${val} => ${bracesChecker(val)}`));
answered Dec 30 '15 at 8:58
Yalamber
4,068104571
I tried this using javascript below is the result.
function bracesChecker(str) {
if(!str) {
return true;
}
var openingBraces = ['{', '[', '('];
var closingBraces = ['}', ']', ')'];
var stack = ;
var openIndex;
var closeIndex;
//check for opening Braces in the val
for (var i = 0, len = str.length; i < len; i++) {
openIndex = openingBraces.indexOf(str[i]);
closeIndex = closingBraces.indexOf(str[i]);
if(openIndex !== -1) {
stack.push(str[i]);
}
if(closeIndex !== -1) {
if(openingBraces[closeIndex] === stack[stack.length-1]) {
stack.pop();
} else {
return false;
}
}
}
if(stack.length === 0) {
return true;
} else {
return false;
}
}
var testStrings = [
'',
'test',
'{{()()}()}()',
'{test{[test]}}',
'{test{[test]}',
'{test{(yo)[test]}}',
'test{[test]}}',
'te()st{[test]}',
'te()st{[test'
];
testStrings.forEach(val => console.log(`${val} => ${bracesChecker(val)}`));
answered Dec 30 '15 at 8:58
Yalamber
4,068104571
answered Dec 30 '15 at 8:58
Yalamber
4,068104571
answered Dec 30 '15 at 8:58
Yalamber
4,068104571
answered Dec 30 '15 at 8:58
Yalamber
4,068104571
4,068104571
add a comment |
add a comment |
0
I have seen answers here and almost all did well. However, I have written my own version that utilizes a Dictionary for managing the bracket pairs and a stack to monitor the order of detected braces. I have also written a blog post for this.
Here is my class
public class FormulaValidator
{
// Question: Check if a string is balanced. Every opening bracket is matched by a closing bracket in a correct position.
// { [ ( } ] )
// Example: "()" is balanced
// Example: "{ ]" is not balanced.
// Examples: "(){}" is balanced.
// "{()}" is balanced
// "{ ( [ ) ] }" is _not_ balanced
// Input: string, containing the bracket symbols only
// Output: true or false
public bool IsBalanced(string input)
{
var brackets = BuildBracketMap();
var openingBraces = new Stack<char>();
var inputCharacters = input.ToCharArray();
foreach (char character in inputCharacters)
{
if (brackets.ContainsKey(character))
{
openingBraces.Push(character);
}
if (brackets.ContainsValue(character))
{
var closingBracket = character;
var openingBracket = brackets.FirstOrDefault(x => x.Value == closingBracket).Key;
if (openingBraces.Peek() == openingBracket)
openingBraces.Pop();
else
return false;
}
}
return openingBraces.Count == 0;
}
private Dictionary<char, char> BuildBracketMap()
{
return new Dictionary<char, char>()
{
{'[', ']'},
{'(', ')'},
{'{', '}'}
};
}
}
answered Mar 23 '17 at 13:05
Allan Chua
3,73782855
add a comment |
0
I have seen answers here and almost all did well. However, I have written my own version that utilizes a Dictionary for managing the bracket pairs and a stack to monitor the order of detected braces. I have also written a blog post for this.
Here is my class
public class FormulaValidator
{
// Question: Check if a string is balanced. Every opening bracket is matched by a closing bracket in a correct position.
// { [ ( } ] )
// Example: "()" is balanced
// Example: "{ ]" is not balanced.
// Examples: "(){}" is balanced.
// "{()}" is balanced
// "{ ( [ ) ] }" is _not_ balanced
// Input: string, containing the bracket symbols only
// Output: true or false
public bool IsBalanced(string input)
{
var brackets = BuildBracketMap();
var openingBraces = new Stack<char>();
var inputCharacters = input.ToCharArray();
foreach (char character in inputCharacters)
{
if (brackets.ContainsKey(character))
{
openingBraces.Push(character);
}
if (brackets.ContainsValue(character))
{
var closingBracket = character;
var openingBracket = brackets.FirstOrDefault(x => x.Value == closingBracket).Key;
if (openingBraces.Peek() == openingBracket)
openingBraces.Pop();
else
return false;
}
}
return openingBraces.Count == 0;
}
private Dictionary<char, char> BuildBracketMap()
{
return new Dictionary<char, char>()
{
{'[', ']'},
{'(', ')'},
{'{', '}'}
};
}
}
answered Mar 23 '17 at 13:05
Allan Chua
3,73782855
add a comment |
0
0
0
I have seen answers here and almost all did well. However, I have written my own version that utilizes a Dictionary for managing the bracket pairs and a stack to monitor the order of detected braces. I have also written a blog post for this.
Here is my class
public class FormulaValidator
{
// Question: Check if a string is balanced. Every opening bracket is matched by a closing bracket in a correct position.
// { [ ( } ] )
// Example: "()" is balanced
// Example: "{ ]" is not balanced.
// Examples: "(){}" is balanced.
// "{()}" is balanced
// "{ ( [ ) ] }" is _not_ balanced
// Input: string, containing the bracket symbols only
// Output: true or false
public bool IsBalanced(string input)
{
var brackets = BuildBracketMap();
var openingBraces = new Stack<char>();
var inputCharacters = input.ToCharArray();
foreach (char character in inputCharacters)
{
if (brackets.ContainsKey(character))
{
openingBraces.Push(character);
}
if (brackets.ContainsValue(character))
{
var closingBracket = character;
var openingBracket = brackets.FirstOrDefault(x => x.Value == closingBracket).Key;
if (openingBraces.Peek() == openingBracket)
openingBraces.Pop();
else
return false;
}
}
return openingBraces.Count == 0;
}
private Dictionary<char, char> BuildBracketMap()
{
return new Dictionary<char, char>()
{
{'[', ']'},
{'(', ')'},
{'{', '}'}
};
}
}
answered Mar 23 '17 at 13:05
Allan Chua
3,73782855
I have seen answers here and almost all did well. However, I have written my own version that utilizes a Dictionary for managing the bracket pairs and a stack to monitor the order of detected braces. I have also written a blog post for this.
Here is my class
public class FormulaValidator
{
// Question: Check if a string is balanced. Every opening bracket is matched by a closing bracket in a correct position.
// { [ ( } ] )
// Example: "()" is balanced
// Example: "{ ]" is not balanced.
// Examples: "(){}" is balanced.
// "{()}" is balanced
// "{ ( [ ) ] }" is _not_ balanced
// Input: string, containing the bracket symbols only
// Output: true or false
public bool IsBalanced(string input)
{
var brackets = BuildBracketMap();
var openingBraces = new Stack<char>();
var inputCharacters = input.ToCharArray();
foreach (char character in inputCharacters)
{
if (brackets.ContainsKey(character))
{
openingBraces.Push(character);
}
if (brackets.ContainsValue(character))
{
var closingBracket = character;
var openingBracket = brackets.FirstOrDefault(x => x.Value == closingBracket).Key;
if (openingBraces.Peek() == openingBracket)
openingBraces.Pop();
else
return false;
}
}
return openingBraces.Count == 0;
}
private Dictionary<char, char> BuildBracketMap()
{
return new Dictionary<char, char>()
{
{'[', ']'},
{'(', ')'},
{'{', '}'}
};
}
}
answered Mar 23 '17 at 13:05
Allan Chua
3,73782855
answered Mar 23 '17 at 13:05
Allan Chua
3,73782855
answered Mar 23 '17 at 13:05
Allan Chua
3,73782855
answered Mar 23 '17 at 13:05
Allan Chua
3,73782855
3,73782855
add a comment |
add a comment |
0
If you want to have a look at my code. Just for reference
public class Default {
public static void main(String args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int numOfString = Integer.parseInt(br.readLine());
String s;
String stringBalanced = "YES";
Stack<Character> exprStack = new Stack<Character>();
while ((s = br.readLine()) != null) {
stringBalanced = "YES";
int length = s.length() - 1;
for (int i = 0; i <= length; i++) {
char tmp = s.charAt(i);
if(tmp=='[' || tmp=='{' || tmp=='('){
exprStack.push(tmp);
}else if(tmp==']' || tmp=='}' || tmp==')'){
if(!exprStack.isEmpty()){
char peekElement = exprStack.peek();
exprStack.pop();
if(tmp==']' && peekElement!='['){
stringBalanced="NO";
}else if(tmp=='}' && peekElement!='{'){
stringBalanced="NO";
}else if(tmp==')' && peekElement!='('){
stringBalanced="NO";
}
}else{
stringBalanced="NO";
break;
}
}
}
if(!exprStack.isEmpty()){
stringBalanced = "NO";
}
exprStack.clear();
System.out.println(stringBalanced);
}
}
}
answered May 18 '17 at 13:13
underdog
2,68022765
add a comment |
0
If you want to have a look at my code. Just for reference
public class Default {
public static void main(String args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int numOfString = Integer.parseInt(br.readLine());
String s;
String stringBalanced = "YES";
Stack<Character> exprStack = new Stack<Character>();
while ((s = br.readLine()) != null) {
stringBalanced = "YES";
int length = s.length() - 1;
for (int i = 0; i <= length; i++) {
char tmp = s.charAt(i);
if(tmp=='[' || tmp=='{' || tmp=='('){
exprStack.push(tmp);
}else if(tmp==']' || tmp=='}' || tmp==')'){
if(!exprStack.isEmpty()){
char peekElement = exprStack.peek();
exprStack.pop();
if(tmp==']' && peekElement!='['){
stringBalanced="NO";
}else if(tmp=='}' && peekElement!='{'){
stringBalanced="NO";
}else if(tmp==')' && peekElement!='('){
stringBalanced="NO";
}
}else{
stringBalanced="NO";
break;
}
}
}
if(!exprStack.isEmpty()){
stringBalanced = "NO";
}
exprStack.clear();
System.out.println(stringBalanced);
}
}
}
answered May 18 '17 at 13:13
underdog
2,68022765
add a comment |
0
0
0
If you want to have a look at my code. Just for reference
public class Default {
public static void main(String args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int numOfString = Integer.parseInt(br.readLine());
String s;
String stringBalanced = "YES";
Stack<Character> exprStack = new Stack<Character>();
while ((s = br.readLine()) != null) {
stringBalanced = "YES";
int length = s.length() - 1;
for (int i = 0; i <= length; i++) {
char tmp = s.charAt(i);
if(tmp=='[' || tmp=='{' || tmp=='('){
exprStack.push(tmp);
}else if(tmp==']' || tmp=='}' || tmp==')'){
if(!exprStack.isEmpty()){
char peekElement = exprStack.peek();
exprStack.pop();
if(tmp==']' && peekElement!='['){
stringBalanced="NO";
}else if(tmp=='}' && peekElement!='{'){
stringBalanced="NO";
}else if(tmp==')' && peekElement!='('){
stringBalanced="NO";
}
}else{
stringBalanced="NO";
break;
}
}
}
if(!exprStack.isEmpty()){
stringBalanced = "NO";
}
exprStack.clear();
System.out.println(stringBalanced);
}
}
}
answered May 18 '17 at 13:13
underdog
2,68022765
If you want to have a look at my code. Just for reference
public class Default {
public static void main(String args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int numOfString = Integer.parseInt(br.readLine());
String s;
String stringBalanced = "YES";
Stack<Character> exprStack = new Stack<Character>();
while ((s = br.readLine()) != null) {
stringBalanced = "YES";
int length = s.length() - 1;
for (int i = 0; i <= length; i++) {
char tmp = s.charAt(i);
if(tmp=='[' || tmp=='{' || tmp=='('){
exprStack.push(tmp);
}else if(tmp==']' || tmp=='}' || tmp==')'){
if(!exprStack.isEmpty()){
char peekElement = exprStack.peek();
exprStack.pop();
if(tmp==']' && peekElement!='['){
stringBalanced="NO";
}else if(tmp=='}' && peekElement!='{'){
stringBalanced="NO";
}else if(tmp==')' && peekElement!='('){
stringBalanced="NO";
}
}else{
stringBalanced="NO";
break;
}
}
}
if(!exprStack.isEmpty()){
stringBalanced = "NO";
}
exprStack.clear();
System.out.println(stringBalanced);
}
}
}
answered May 18 '17 at 13:13
underdog
2,68022765
answered May 18 '17 at 13:13
underdog
2,68022765
answered May 18 '17 at 13:13
underdog
2,68022765
answered May 18 '17 at 13:13
underdog
2,68022765
2,68022765
add a comment |
add a comment |
0
public String checkString(String value) {
Stack<Character> stack = new Stack<>();
char topStackChar = 0;
for (int i = 0; i < value.length(); i++) {
if (!stack.isEmpty()) {
topStackChar = stack.peek();
}
stack.push(value.charAt(i));
if (!stack.isEmpty() && stack.size() > 1) {
if ((topStackChar == '[' && stack.peek() == ']') ||
(topStackChar == '{' && stack.peek() == '}') ||
(topStackChar == '(' && stack.peek() == ')')) {
stack.pop();
stack.pop();
}
}
}
return stack.isEmpty() ? "YES" : "NO";
}
answered Aug 19 '17 at 14:42
unicredit
19610
add a comment |
0
public String checkString(String value) {
Stack<Character> stack = new Stack<>();
char topStackChar = 0;
for (int i = 0; i < value.length(); i++) {
if (!stack.isEmpty()) {
topStackChar = stack.peek();
}
stack.push(value.charAt(i));
if (!stack.isEmpty() && stack.size() > 1) {
if ((topStackChar == '[' && stack.peek() == ']') ||
(topStackChar == '{' && stack.peek() == '}') ||
(topStackChar == '(' && stack.peek() == ')')) {
stack.pop();
stack.pop();
}
}
}
return stack.isEmpty() ? "YES" : "NO";
}
answered Aug 19 '17 at 14:42
unicredit
19610
add a comment |
0
0
0
public String checkString(String value) {
Stack<Character> stack = new Stack<>();
char topStackChar = 0;
for (int i = 0; i < value.length(); i++) {
if (!stack.isEmpty()) {
topStackChar = stack.peek();
}
stack.push(value.charAt(i));
if (!stack.isEmpty() && stack.size() > 1) {
if ((topStackChar == '[' && stack.peek() == ']') ||
(topStackChar == '{' && stack.peek() == '}') ||
(topStackChar == '(' && stack.peek() == ')')) {
stack.pop();
stack.pop();
}
}
}
return stack.isEmpty() ? "YES" : "NO";
}
answered Aug 19 '17 at 14:42
unicredit
19610
public String checkString(String value) {
Stack<Character> stack = new Stack<>();
char topStackChar = 0;
for (int i = 0; i < value.length(); i++) {
if (!stack.isEmpty()) {
topStackChar = stack.peek();
}
stack.push(value.charAt(i));
if (!stack.isEmpty() && stack.size() > 1) {
if ((topStackChar == '[' && stack.peek() == ']') ||
(topStackChar == '{' && stack.peek() == '}') ||
(topStackChar == '(' && stack.peek() == ')')) {
stack.pop();
stack.pop();
}
}
}
return stack.isEmpty() ? "YES" : "NO";
}
answered Aug 19 '17 at 14:42
unicredit
19610
answered Aug 19 '17 at 14:42
unicredit
19610
answered Aug 19 '17 at 14:42
unicredit
19610
answered Aug 19 '17 at 14:42
unicredit
19610
19610
add a comment |
add a comment |
0
Here's a solution in Python.
#!/usr/bin/env python
def brackets_match(brackets):
stack =
for char in brackets:
if char == "{" or char == "(" or char == "[":
stack.append(char)
if char == "}":
if stack[-1] == "{":
stack.pop()
else:
return False
elif char == "]":
if stack[-1] == "[":
stack.pop()
else:
return False
elif char == ")":
if stack[-1] == "(":
stack.pop()
else:
return False
if len(stack) == 0:
return True
else:
return False
if __name__ == "__main__":
print(brackets_match("This is testing {()} if brackets have match."))
answered May 29 at 12:13
Said Ali Samed
8412
add a comment |
0
Here's a solution in Python.
#!/usr/bin/env python
def brackets_match(brackets):
stack =
for char in brackets:
if char == "{" or char == "(" or char == "[":
stack.append(char)
if char == "}":
if stack[-1] == "{":
stack.pop()
else:
return False
elif char == "]":
if stack[-1] == "[":
stack.pop()
else:
return False
elif char == ")":
if stack[-1] == "(":
stack.pop()
else:
return False
if len(stack) == 0:
return True
else:
return False
if __name__ == "__main__":
print(brackets_match("This is testing {()} if brackets have match."))
answered May 29 at 12:13
Said Ali Samed
8412
add a comment |
0
0
0
Here's a solution in Python.
#!/usr/bin/env python
def brackets_match(brackets):
stack =
for char in brackets:
if char == "{" or char == "(" or char == "[":
stack.append(char)
if char == "}":
if stack[-1] == "{":
stack.pop()
else:
return False
elif char == "]":
if stack[-1] == "[":
stack.pop()
else:
return False
elif char == ")":
if stack[-1] == "(":
stack.pop()
else:
return False
if len(stack) == 0:
return True
else:
return False
if __name__ == "__main__":
print(brackets_match("This is testing {()} if brackets have match."))
answered May 29 at 12:13
Said Ali Samed
8412
Here's a solution in Python.
#!/usr/bin/env python
def brackets_match(brackets):
stack =
for char in brackets:
if char == "{" or char == "(" or char == "[":
stack.append(char)
if char == "}":
if stack[-1] == "{":
stack.pop()
else:
return False
elif char == "]":
if stack[-1] == "[":
stack.pop()
else:
return False
elif char == ")":
if stack[-1] == "(":
stack.pop()
else:
return False
if len(stack) == 0:
return True
else:
return False
if __name__ == "__main__":
print(brackets_match("This is testing {()} if brackets have match."))
answered May 29 at 12:13
Said Ali Samed
8412
answered May 29 at 12:13
Said Ali Samed
8412
answered May 29 at 12:13
Said Ali Samed
8412
answered May 29 at 12:13
Said Ali Samed
8412
8412
add a comment |
add a comment |
0
Was asked to implement this algorithm at live coding interview, here's my refactored solution in C#:
Git Tests
answered Jun 22 at 16:10
Dmytro Zhluktenko
647
add a comment |
0
Was asked to implement this algorithm at live coding interview, here's my refactored solution in C#:
Git Tests
answered Jun 22 at 16:10
Dmytro Zhluktenko
647
add a comment |
0
0
0
Was asked to implement this algorithm at live coding interview, here's my refactored solution in C#:
Git Tests
answered Jun 22 at 16:10
Dmytro Zhluktenko
647
Was asked to implement this algorithm at live coding interview, here's my refactored solution in C#:
Git Tests
answered Jun 22 at 16:10
Dmytro Zhluktenko
647
answered Jun 22 at 16:10
Dmytro Zhluktenko
647
answered Jun 22 at 16:10
Dmytro Zhluktenko
647
answered Jun 22 at 16:10
Dmytro Zhluktenko
647
647
add a comment |
add a comment |
0
package com.balance.braces;
import java.util.Arrays;
import java.util.Stack;
public class BalanceBraces {
public static void main(String args) {
String values = { "()]", "[()]" };
String rsult = match(values);
Arrays.stream(rsult).forEach(str -> System.out.println(str));
}
static String match(String values) {
String returnString = new String[values.length];
for (int i = 0; i < values.length; i++) {
String value = values[i];
if (value.length() % 2 != 0) {
returnString[i] = "NO";
continue;
} else {
Stack<Character> buffer = new Stack<Character>();
for (char ch : value.toCharArray()) {
if (buffer.isEmpty()) {
buffer.add(ch);
} else {
if (isMatchedBrace(buffer.peek(), ch)) {
buffer.pop();
} else {
buffer.push(ch);
}
}
if (buffer.isEmpty()) {
returnString[i] = "YES";
} else {
returnString[i] = "FALSE";
}
}
}
}
return returnString;
}
static boolean isMatchedBrace(char start, char endmatch) {
if (start == '{')
return endmatch == '}';
if (start == '(')
return endmatch == ')';
if (start == '[')
return endmatch == ']';
return false;
}
}
edited Aug 2 at 12:12
Fredrik Widerberg
2,687102340
answered Aug 2 at 11:51
Ritesh Nailwal
11
add a comment |
0
package com.balance.braces;
import java.util.Arrays;
import java.util.Stack;
public class BalanceBraces {
public static void main(String args) {
String values = { "()]", "[()]" };
String rsult = match(values);
Arrays.stream(rsult).forEach(str -> System.out.println(str));
}
static String match(String values) {
String returnString = new String[values.length];
for (int i = 0; i < values.length; i++) {
String value = values[i];
if (value.length() % 2 != 0) {
returnString[i] = "NO";
continue;
} else {
Stack<Character> buffer = new Stack<Character>();
for (char ch : value.toCharArray()) {
if (buffer.isEmpty()) {
buffer.add(ch);
} else {
if (isMatchedBrace(buffer.peek(), ch)) {
buffer.pop();
} else {
buffer.push(ch);
}
}
if (buffer.isEmpty()) {
returnString[i] = "YES";
} else {
returnString[i] = "FALSE";
}
}
}
}
return returnString;
}
static boolean isMatchedBrace(char start, char endmatch) {
if (start == '{')
return endmatch == '}';
if (start == '(')
return endmatch == ')';
if (start == '[')
return endmatch == ']';
return false;
}
}
edited Aug 2 at 12:12
Fredrik Widerberg
2,687102340
answered Aug 2 at 11:51
Ritesh Nailwal
11
add a comment |
0
0
0
package com.balance.braces;
import java.util.Arrays;
import java.util.Stack;
public class BalanceBraces {
public static void main(String args) {
String values = { "()]", "[()]" };
String rsult = match(values);
Arrays.stream(rsult).forEach(str -> System.out.println(str));
}
static String match(String values) {
String returnString = new String[values.length];
for (int i = 0; i < values.length; i++) {
String value = values[i];
if (value.length() % 2 != 0) {
returnString[i] = "NO";
continue;
} else {
Stack<Character> buffer = new Stack<Character>();
for (char ch : value.toCharArray()) {
if (buffer.isEmpty()) {
buffer.add(ch);
} else {
if (isMatchedBrace(buffer.peek(), ch)) {
buffer.pop();
} else {
buffer.push(ch);
}
}
if (buffer.isEmpty()) {
returnString[i] = "YES";
} else {
returnString[i] = "FALSE";
}
}
}
}
return returnString;
}
static boolean isMatchedBrace(char start, char endmatch) {
if (start == '{')
return endmatch == '}';
if (start == '(')
return endmatch == ')';
if (start == '[')
return endmatch == ']';
return false;
}
}
edited Aug 2 at 12:12
Fredrik Widerberg
2,687102340
answered Aug 2 at 11:51
Ritesh Nailwal
11
package com.balance.braces;
import java.util.Arrays;
import java.util.Stack;
public class BalanceBraces {
public static void main(String args) {
String values = { "()]", "[()]" };
String rsult = match(values);
Arrays.stream(rsult).forEach(str -> System.out.println(str));
}
static String match(String values) {
String returnString = new String[values.length];
for (int i = 0; i < values.length; i++) {
String value = values[i];
if (value.length() % 2 != 0) {
returnString[i] = "NO";
continue;
} else {
Stack<Character> buffer = new Stack<Character>();
for (char ch : value.toCharArray()) {
if (buffer.isEmpty()) {
buffer.add(ch);
} else {
if (isMatchedBrace(buffer.peek(), ch)) {
buffer.pop();
} else {
buffer.push(ch);
}
}
if (buffer.isEmpty()) {
returnString[i] = "YES";
} else {
returnString[i] = "FALSE";
}
}
}
}
return returnString;
}
static boolean isMatchedBrace(char start, char endmatch) {
if (start == '{')
return endmatch == '}';
if (start == '(')
return endmatch == ')';
if (start == '[')
return endmatch == ']';
return false;
}
}
edited Aug 2 at 12:12
Fredrik Widerberg
2,687102340
answered Aug 2 at 11:51
Ritesh Nailwal
11
edited Aug 2 at 12:12
Fredrik Widerberg
2,687102340
edited Aug 2 at 12:12
Fredrik Widerberg
2,687102340
edited Aug 2 at 12:12
Fredrik Widerberg
2,687102340
2,687102340
answered Aug 2 at 11:51
Ritesh Nailwal
11
answered Aug 2 at 11:51
Ritesh Nailwal
11
answered Aug 2 at 11:51
Ritesh Nailwal
11
11
add a comment |
add a comment |
0
Check balanced parenthesis or brackets with stack--
var excp = "{{()}[{a+b+b}][{(c+d){}}]}";
var stk = ;
function bracket_balance(){
for(var i=0;i<excp.length;i++){
if(excp[i]=='[' || excp[i]=='(' || excp[i]=='{'){
stk.push(excp[i]);
}else if(excp[i]== ']' && stk.pop() != '['){
return false;
}else if(excp[i]== '}' && stk.pop() != '{'){
return false;
}else if(excp[i]== ')' && stk.pop() != '('){
return false;
}
}
return true;
}
console.log(bracket_balance());
//Parenthesis are balance then return true else false
answered Nov 25 at 8:56
suryadev
732
add a comment |
0
Check balanced parenthesis or brackets with stack--
var excp = "{{()}[{a+b+b}][{(c+d){}}]}";
var stk = ;
function bracket_balance(){
for(var i=0;i<excp.length;i++){
if(excp[i]=='[' || excp[i]=='(' || excp[i]=='{'){
stk.push(excp[i]);
}else if(excp[i]== ']' && stk.pop() != '['){
return false;
}else if(excp[i]== '}' && stk.pop() != '{'){
return false;
}else if(excp[i]== ')' && stk.pop() != '('){
return false;
}
}
return true;
}
console.log(bracket_balance());
//Parenthesis are balance then return true else false
answered Nov 25 at 8:56
suryadev
732
add a comment |
0
0
0
Check balanced parenthesis or brackets with stack--
var excp = "{{()}[{a+b+b}][{(c+d){}}]}";
var stk = ;
function bracket_balance(){
for(var i=0;i<excp.length;i++){
if(excp[i]=='[' || excp[i]=='(' || excp[i]=='{'){
stk.push(excp[i]);
}else if(excp[i]== ']' && stk.pop() != '['){
return false;
}else if(excp[i]== '}' && stk.pop() != '{'){
return false;
}else if(excp[i]== ')' && stk.pop() != '('){
return false;
}
}
return true;
}
console.log(bracket_balance());
//Parenthesis are balance then return true else false
answered Nov 25 at 8:56
suryadev
732
Check balanced parenthesis or brackets with stack--
var excp = "{{()}[{a+b+b}][{(c+d){}}]}";
var stk = ;
function bracket_balance(){
for(var i=0;i<excp.length;i++){
if(excp[i]=='[' || excp[i]=='(' || excp[i]=='{'){
stk.push(excp[i]);
}else if(excp[i]== ']' && stk.pop() != '['){
return false;
}else if(excp[i]== '}' && stk.pop() != '{'){
return false;
}else if(excp[i]== ')' && stk.pop() != '('){
return false;
}
}
return true;
}
console.log(bracket_balance());
//Parenthesis are balance then return true else false
answered Nov 25 at 8:56
suryadev
732
edited Nov 26 at 3:53
answered Nov 25 at 8:56
suryadev
732
answered Nov 25 at 8:56
suryadev
732
answered Nov 25 at 8:56
suryadev
732
732
add a comment |
add a comment |
0
You're doing some extra checks that aren't needed. Doesn't make any diff to functionality, but a cleaner way to write your code would be:
public static boolean isParenthesisMatch(String str) {
Stack<Character> stack = new Stack<Character>();
char c;
for (int i = 0; i < str.length(); i++) {
c = str.charAt(i);
if (c == '(' || c == '{')
stack.push(c);
else if (stack.empty())
return false;
else if (c == ')') {
if (stack.pop() != '(')
return false;
} else if (c == '}') {
if (stack.pop() != '{')
return false;
}
}
return stack.empty();
}
There is no reason to peek at a paranthesis before removing it from the stack. I'd also consider wrapping instruction blocks in parantheses to improve readability.
answered Dec 23 at 14:36
tfp95
81
add a comment |
0
You're doing some extra checks that aren't needed. Doesn't make any diff to functionality, but a cleaner way to write your code would be:
public static boolean isParenthesisMatch(String str) {
Stack<Character> stack = new Stack<Character>();
char c;
for (int i = 0; i < str.length(); i++) {
c = str.charAt(i);
if (c == '(' || c == '{')
stack.push(c);
else if (stack.empty())
return false;
else if (c == ')') {
if (stack.pop() != '(')
return false;
} else if (c == '}') {
if (stack.pop() != '{')
return false;
}
}
return stack.empty();
}
There is no reason to peek at a paranthesis before removing it from the stack. I'd also consider wrapping instruction blocks in parantheses to improve readability.
answered Dec 23 at 14:36
tfp95
81
add a comment |
0
0
0
You're doing some extra checks that aren't needed. Doesn't make any diff to functionality, but a cleaner way to write your code would be:
public static boolean isParenthesisMatch(String str) {
Stack<Character> stack = new Stack<Character>();
char c;
for (int i = 0; i < str.length(); i++) {
c = str.charAt(i);
if (c == '(' || c == '{')
stack.push(c);
else if (stack.empty())
return false;
else if (c == ')') {
if (stack.pop() != '(')
return false;
} else if (c == '}') {
if (stack.pop() != '{')
return false;
}
}
return stack.empty();
}
There is no reason to peek at a paranthesis before removing it from the stack. I'd also consider wrapping instruction blocks in parantheses to improve readability.
answered Dec 23 at 14:36
tfp95
81
You're doing some extra checks that aren't needed. Doesn't make any diff to functionality, but a cleaner way to write your code would be:
public static boolean isParenthesisMatch(String str) {
Stack<Character> stack = new Stack<Character>();
char c;
for (int i = 0; i < str.length(); i++) {
c = str.charAt(i);
if (c == '(' || c == '{')
stack.push(c);
else if (stack.empty())
return false;
else if (c == ')') {
if (stack.pop() != '(')
return false;
} else if (c == '}') {
if (stack.pop() != '{')
return false;
}
}
return stack.empty();
}
There is no reason to peek at a paranthesis before removing it from the stack. I'd also consider wrapping instruction blocks in parantheses to improve readability.
answered Dec 23 at 14:36
tfp95
81
answered Dec 23 at 14:36
tfp95
81
answered Dec 23 at 14:36
tfp95
81
answered Dec 23 at 14:36
tfp95
81
81
add a comment |
add a comment |
-1
import java.util.*;
public class Parenthesis
{
public static void main(String...okok)
{
Scanner sc= new Scanner(System.in);
String str=sc.next();
System.out.println(isValid(str));
}
public static int isValid(String a) {
if(a.length()%2!=0)
{
return 0;
}
else if(a.length()==0)
{
return 1;
}
else
{
char c=a.toCharArray();
Stack<Character> stk = new Stack<Character>();
for(int i=0;i<c.length;i++)
{
if(c[i]=='(' || c[i]=='[' || c[i]=='{')
{
stk.push(c[i]);
}
else
{
if(stk.isEmpty())
{
return 0;
//break;
}
else
{
char cc=c[i];
if(cc==')' && stk.peek()=='(' )
{
stk.pop();
}
else if(cc==']' && stk.peek()=='[' )
{
stk.pop();
}
else if(cc=='}' && stk.peek()=='{' )
{
stk.pop();
}
}
}
}
if(stk.isEmpty())
{
return 1;
}else
{
return 0;
}
}
}
}
edited Dec 4 '15 at 5:26
Haris
10.5k62851
answered Dec 4 '15 at 4:20
Prabhu
11
add a comment |
-1
import java.util.*;
public class Parenthesis
{
public static void main(String...okok)
{
Scanner sc= new Scanner(System.in);
String str=sc.next();
System.out.println(isValid(str));
}
public static int isValid(String a) {
if(a.length()%2!=0)
{
return 0;
}
else if(a.length()==0)
{
return 1;
}
else
{
char c=a.toCharArray();
Stack<Character> stk = new Stack<Character>();
for(int i=0;i<c.length;i++)
{
if(c[i]=='(' || c[i]=='[' || c[i]=='{')
{
stk.push(c[i]);
}
else
{
if(stk.isEmpty())
{
return 0;
//break;
}
else
{
char cc=c[i];
if(cc==')' && stk.peek()=='(' )
{
stk.pop();
}
else if(cc==']' && stk.peek()=='[' )
{
stk.pop();
}
else if(cc=='}' && stk.peek()=='{' )
{
stk.pop();
}
}
}
}
if(stk.isEmpty())
{
return 1;
}else
{
return 0;
}
}
}
}
edited Dec 4 '15 at 5:26
Haris
10.5k62851
answered Dec 4 '15 at 4:20
Prabhu
11
add a comment |
-1
-1
-1
import java.util.*;
public class Parenthesis
{
public static void main(String...okok)
{
Scanner sc= new Scanner(System.in);
String str=sc.next();
System.out.println(isValid(str));
}
public static int isValid(String a) {
if(a.length()%2!=0)
{
return 0;
}
else if(a.length()==0)
{
return 1;
}
else
{
char c=a.toCharArray();
Stack<Character> stk = new Stack<Character>();
for(int i=0;i<c.length;i++)
{
if(c[i]=='(' || c[i]=='[' || c[i]=='{')
{
stk.push(c[i]);
}
else
{
if(stk.isEmpty())
{
return 0;
//break;
}
else
{
char cc=c[i];
if(cc==')' && stk.peek()=='(' )
{
stk.pop();
}
else if(cc==']' && stk.peek()=='[' )
{
stk.pop();
}
else if(cc=='}' && stk.peek()=='{' )
{
stk.pop();
}
}
}
}
if(stk.isEmpty())
{
return 1;
}else
{
return 0;
}
}
}
}
edited Dec 4 '15 at 5:26
Haris
10.5k62851
answered Dec 4 '15 at 4:20
Prabhu
11
import java.util.*;
public class Parenthesis
{
public static void main(String...okok)
{
Scanner sc= new Scanner(System.in);
String str=sc.next();
System.out.println(isValid(str));
}
public static int isValid(String a) {
if(a.length()%2!=0)
{
return 0;
}
else if(a.length()==0)
{
return 1;
}
else
{
char c=a.toCharArray();
Stack<Character> stk = new Stack<Character>();
for(int i=0;i<c.length;i++)
{
if(c[i]=='(' || c[i]=='[' || c[i]=='{')
{
stk.push(c[i]);
}
else
{
if(stk.isEmpty())
{
return 0;
//break;
}
else
{
char cc=c[i];
if(cc==')' && stk.peek()=='(' )
{
stk.pop();
}
else if(cc==']' && stk.peek()=='[' )
{
stk.pop();
}
else if(cc=='}' && stk.peek()=='{' )
{
stk.pop();
}
}
}
}
if(stk.isEmpty())
{
return 1;
}else
{
return 0;
}
}
}
}
edited Dec 4 '15 at 5:26
Haris
10.5k62851
answered Dec 4 '15 at 4:20
Prabhu
11
edited Dec 4 '15 at 5:26
Haris
10.5k62851
edited Dec 4 '15 at 5:26
Haris
10.5k62851
edited Dec 4 '15 at 5:26
Haris
10.5k62851
10.5k62851
answered Dec 4 '15 at 4:20
Prabhu
11
answered Dec 4 '15 at 4:20
Prabhu
11
answered Dec 4 '15 at 4:20
Prabhu
11
11
add a comment |
add a comment |
-1
import java.util.*;
public class MatchBrackets {
public static void main(String argh) {
String input = "{()}";
System.out.println (input);
char openChars = {'[','{','('};
char closeChars = {']','}',')'};
Stack<Character> stack = new Stack<Character>();
for (int i = 0; i < input.length(); i++) {
String x = "" +input.charAt(i);
if (String.valueOf(openChars).indexOf(x) != -1)
{
stack.push(input.charAt(i));
}
else
{
Character lastOpener = stack.peek();
int idx1 = String.valueOf(openChars).indexOf(lastOpener.toString());
int idx2 = String.valueOf(closeChars).indexOf(x);
if (idx1 != idx2)
{
System.out.println("false");
return;
}
else
{
stack.pop();
}
}
}
if (stack.size() == 0)
System.out.println("true");
else
System.out.println("false");
}
}
edited Feb 25 '16 at 18:48
gengisdave
1,40741517
answered Feb 25 '16 at 17:53
Pravin Lobo
1
add a comment |
-1
import java.util.*;
public class MatchBrackets {
public static void main(String argh) {
String input = "{()}";
System.out.println (input);
char openChars = {'[','{','('};
char closeChars = {']','}',')'};
Stack<Character> stack = new Stack<Character>();
for (int i = 0; i < input.length(); i++) {
String x = "" +input.charAt(i);
if (String.valueOf(openChars).indexOf(x) != -1)
{
stack.push(input.charAt(i));
}
else
{
Character lastOpener = stack.peek();
int idx1 = String.valueOf(openChars).indexOf(lastOpener.toString());
int idx2 = String.valueOf(closeChars).indexOf(x);
if (idx1 != idx2)
{
System.out.println("false");
return;
}
else
{
stack.pop();
}
}
}
if (stack.size() == 0)
System.out.println("true");
else
System.out.println("false");
}
}
edited Feb 25 '16 at 18:48
gengisdave
1,40741517
answered Feb 25 '16 at 17:53
Pravin Lobo
1
add a comment |
-1
-1
-1
import java.util.*;
public class MatchBrackets {
public static void main(String argh) {
String input = "{()}";
System.out.println (input);
char openChars = {'[','{','('};
char closeChars = {']','}',')'};
Stack<Character> stack = new Stack<Character>();
for (int i = 0; i < input.length(); i++) {
String x = "" +input.charAt(i);
if (String.valueOf(openChars).indexOf(x) != -1)
{
stack.push(input.charAt(i));
}
else
{
Character lastOpener = stack.peek();
int idx1 = String.valueOf(openChars).indexOf(lastOpener.toString());
int idx2 = String.valueOf(closeChars).indexOf(x);
if (idx1 != idx2)
{
System.out.println("false");
return;
}
else
{
stack.pop();
}
}
}
if (stack.size() == 0)
System.out.println("true");
else
System.out.println("false");
}
}
edited Feb 25 '16 at 18:48
gengisdave
1,40741517
answered Feb 25 '16 at 17:53
Pravin Lobo
1
import java.util.*;
public class MatchBrackets {
public static void main(String argh) {
String input = "{()}";
System.out.println (input);
char openChars = {'[','{','('};
char closeChars = {']','}',')'};
Stack<Character> stack = new Stack<Character>();
for (int i = 0; i < input.length(); i++) {
String x = "" +input.charAt(i);
if (String.valueOf(openChars).indexOf(x) != -1)
{
stack.push(input.charAt(i));
}
else
{
Character lastOpener = stack.peek();
int idx1 = String.valueOf(openChars).indexOf(lastOpener.toString());
int idx2 = String.valueOf(closeChars).indexOf(x);
if (idx1 != idx2)
{
System.out.println("false");
return;
}
else
{
stack.pop();
}
}
}
if (stack.size() == 0)
System.out.println("true");
else
System.out.println("false");
}
}
edited Feb 25 '16 at 18:48
gengisdave
1,40741517
answered Feb 25 '16 at 17:53
Pravin Lobo
1
edited Feb 25 '16 at 18:48
gengisdave
1,40741517
edited Feb 25 '16 at 18:48
gengisdave
1,40741517
edited Feb 25 '16 at 18:48
gengisdave
1,40741517
1,40741517
answered Feb 25 '16 at 17:53
Pravin Lobo
1
answered Feb 25 '16 at 17:53
Pravin Lobo
1
answered Feb 25 '16 at 17:53
Pravin Lobo
1
1
add a comment |
add a comment |
-1
public static bool IsBalanced(string input)
{
Dictionary<char, char> bracketPairs = new Dictionary<char, char>() {
{ '(', ')' },
{ '{', '}' },
{ '[', ']' },
{ '<', '>' }
};
Stack<char> brackets = new Stack<char>();
try
{
// Iterate through each character in the input string
foreach (char c in input)
{
// check if the character is one of the 'opening' brackets
if (bracketPairs.Keys.Contains(c))
{
// if yes, push to stack
brackets.Push(c);
}
else
// check if the character is one of the 'closing' brackets
if (bracketPairs.Values.Contains(c))
{
// check if the closing bracket matches the 'latest' 'opening' bracket
if (c == bracketPairs[brackets.First()])
{
brackets.Pop();
}
else
// if not, its an unbalanced string
return false;
}
else
// continue looking
continue;
}
}
catch
{
// an exception will be caught in case a closing bracket is found,
// before any opening bracket.
// that implies, the string is not balanced. Return false
return false;
}
// Ensure all brackets are closed
return brackets.Count() == 0 ? true : false;
}
answered Jun 8 '17 at 5:28
Muhammad Kashif
1
add a comment |
-1
public static bool IsBalanced(string input)
{
Dictionary<char, char> bracketPairs = new Dictionary<char, char>() {
{ '(', ')' },
{ '{', '}' },
{ '[', ']' },
{ '<', '>' }
};
Stack<char> brackets = new Stack<char>();
try
{
// Iterate through each character in the input string
foreach (char c in input)
{
// check if the character is one of the 'opening' brackets
if (bracketPairs.Keys.Contains(c))
{
// if yes, push to stack
brackets.Push(c);
}
else
// check if the character is one of the 'closing' brackets
if (bracketPairs.Values.Contains(c))
{
// check if the closing bracket matches the 'latest' 'opening' bracket
if (c == bracketPairs[brackets.First()])
{
brackets.Pop();
}
else
// if not, its an unbalanced string
return false;
}
else
// continue looking
continue;
}
}
catch
{
// an exception will be caught in case a closing bracket is found,
// before any opening bracket.
// that implies, the string is not balanced. Return false
return false;
}
// Ensure all brackets are closed
return brackets.Count() == 0 ? true : false;
}
answered Jun 8 '17 at 5:28
Muhammad Kashif
1
add a comment |
-1
-1
-1
public static bool IsBalanced(string input)
{
Dictionary<char, char> bracketPairs = new Dictionary<char, char>() {
{ '(', ')' },
{ '{', '}' },
{ '[', ']' },
{ '<', '>' }
};
Stack<char> brackets = new Stack<char>();
try
{
// Iterate through each character in the input string
foreach (char c in input)
{
// check if the character is one of the 'opening' brackets
if (bracketPairs.Keys.Contains(c))
{
// if yes, push to stack
brackets.Push(c);
}
else
// check if the character is one of the 'closing' brackets
if (bracketPairs.Values.Contains(c))
{
// check if the closing bracket matches the 'latest' 'opening' bracket
if (c == bracketPairs[brackets.First()])
{
brackets.Pop();
}
else
// if not, its an unbalanced string
return false;
}
else
// continue looking
continue;
}
}
catch
{
// an exception will be caught in case a closing bracket is found,
// before any opening bracket.
// that implies, the string is not balanced. Return false
return false;
}
// Ensure all brackets are closed
return brackets.Count() == 0 ? true : false;
}
answered Jun 8 '17 at 5:28
Muhammad Kashif
1
public static bool IsBalanced(string input)
{
Dictionary<char, char> bracketPairs = new Dictionary<char, char>() {
{ '(', ')' },
{ '{', '}' },
{ '[', ']' },
{ '<', '>' }
};
Stack<char> brackets = new Stack<char>();
try
{
// Iterate through each character in the input string
foreach (char c in input)
{
// check if the character is one of the 'opening' brackets
if (bracketPairs.Keys.Contains(c))
{
// if yes, push to stack
brackets.Push(c);
}
else
// check if the character is one of the 'closing' brackets
if (bracketPairs.Values.Contains(c))
{
// check if the closing bracket matches the 'latest' 'opening' bracket
if (c == bracketPairs[brackets.First()])
{
brackets.Pop();
}
else
// if not, its an unbalanced string
return false;
}
else
// continue looking
continue;
}
}
catch
{
// an exception will be caught in case a closing bracket is found,
// before any opening bracket.
// that implies, the string is not balanced. Return false
return false;
}
// Ensure all brackets are closed
return brackets.Count() == 0 ? true : false;
}
answered Jun 8 '17 at 5:28
Muhammad Kashif
1
answered Jun 8 '17 at 5:28
Muhammad Kashif
1
answered Jun 8 '17 at 5:28
Muhammad Kashif
1
answered Jun 8 '17 at 5:28
Muhammad Kashif
1
1
add a comment |
add a comment |
-1
in java you don't want to compare the string or char by == signs. you would use equals method. equalsIgnoreCase or something of the like. if you use == it must point to the same memory location. In the method below I attempted to use ints to get around this. using ints here from the string index since every opening brace has a closing brace. I wanted to use location match instead of a comparison match. But i think with this you have to be intentional in where you place the characters of the string. Lets also consider that Yes = true and No = false for simplicity. This answer assumes that you passed an array of strings to inspect and required an array of if yes (they matched) or No (they didn't)
import java.util.Stack;
public static void main(String args) {
//String arrayOfBraces = new String{"{}","([{}])","{}{()}","{}","}]{}","{[)]()}"};
// Example: "()" is balanced
// Example: "{ ]" is not balanced.
// Examples: "(){}" is balanced.
// "{()}" is balanced
// "{([)]}" is _not_ balanced
String arrayOfBraces = new String{"{}","([{}])","{}{()}","(){}","}]{}","{[)]()}","{[)]()}","{([)]}"};
String answers = new String[arrayOfBraces.length];
String openers = "([{";
String closers = ")]}";
String stringToInspect = "";
Stack<String> stack = new Stack<String>();
for (int i = 0; i < arrayOfBraces.length; i++) {
stringToInspect = arrayOfBraces[i];
for (int j = 0; j < stringToInspect.length(); j++) {
if(stack.isEmpty()){
if (openers.indexOf(stringToInspect.charAt(j))>=0) {
stack.push(""+stringToInspect.charAt(j));
}
else{
answers[i]= "NO";
j=stringToInspect.length();
}
}
else if(openers.indexOf(stringToInspect.charAt(j))>=0){
stack.push(""+stringToInspect.charAt(j));
}
else{
String comparator = stack.pop();
int compLoc = openers.indexOf(comparator);
int thisLoc = closers.indexOf(stringToInspect.charAt(j));
if (compLoc != thisLoc) {
answers[i]= "NO";
j=stringToInspect.length();
}
else{
if(stack.empty() && (j== stringToInspect.length()-1)){
answers[i]= "YES";
}
}
}
}
}
System.out.println(answers.length);
for (int j = 0; j < answers.length; j++) {
System.out.println(answers[j]);
}
}
answered Sep 11 at 20:07
TimeTrax
19527
add a comment |
-1
in java you don't want to compare the string or char by == signs. you would use equals method. equalsIgnoreCase or something of the like. if you use == it must point to the same memory location. In the method below I attempted to use ints to get around this. using ints here from the string index since every opening brace has a closing brace. I wanted to use location match instead of a comparison match. But i think with this you have to be intentional in where you place the characters of the string. Lets also consider that Yes = true and No = false for simplicity. This answer assumes that you passed an array of strings to inspect and required an array of if yes (they matched) or No (they didn't)
import java.util.Stack;
public static void main(String args) {
//String arrayOfBraces = new String{"{}","([{}])","{}{()}","{}","}]{}","{[)]()}"};
// Example: "()" is balanced
// Example: "{ ]" is not balanced.
// Examples: "(){}" is balanced.
// "{()}" is balanced
// "{([)]}" is _not_ balanced
String arrayOfBraces = new String{"{}","([{}])","{}{()}","(){}","}]{}","{[)]()}","{[)]()}","{([)]}"};
String answers = new String[arrayOfBraces.length];
String openers = "([{";
String closers = ")]}";
String stringToInspect = "";
Stack<String> stack = new Stack<String>();
for (int i = 0; i < arrayOfBraces.length; i++) {
stringToInspect = arrayOfBraces[i];
for (int j = 0; j < stringToInspect.length(); j++) {
if(stack.isEmpty()){
if (openers.indexOf(stringToInspect.charAt(j))>=0) {
stack.push(""+stringToInspect.charAt(j));
}
else{
answers[i]= "NO";
j=stringToInspect.length();
}
}
else if(openers.indexOf(stringToInspect.charAt(j))>=0){
stack.push(""+stringToInspect.charAt(j));
}
else{
String comparator = stack.pop();
int compLoc = openers.indexOf(comparator);
int thisLoc = closers.indexOf(stringToInspect.charAt(j));
if (compLoc != thisLoc) {
answers[i]= "NO";
j=stringToInspect.length();
}
else{
if(stack.empty() && (j== stringToInspect.length()-1)){
answers[i]= "YES";
}
}
}
}
}
System.out.println(answers.length);
for (int j = 0; j < answers.length; j++) {
System.out.println(answers[j]);
}
}
answered Sep 11 at 20:07
TimeTrax
19527
add a comment |
-1
-1
-1
in java you don't want to compare the string or char by == signs. you would use equals method. equalsIgnoreCase or something of the like. if you use == it must point to the same memory location. In the method below I attempted to use ints to get around this. using ints here from the string index since every opening brace has a closing brace. I wanted to use location match instead of a comparison match. But i think with this you have to be intentional in where you place the characters of the string. Lets also consider that Yes = true and No = false for simplicity. This answer assumes that you passed an array of strings to inspect and required an array of if yes (they matched) or No (they didn't)
import java.util.Stack;
public static void main(String args) {
//String arrayOfBraces = new String{"{}","([{}])","{}{()}","{}","}]{}","{[)]()}"};
// Example: "()" is balanced
// Example: "{ ]" is not balanced.
// Examples: "(){}" is balanced.
// "{()}" is balanced
// "{([)]}" is _not_ balanced
String arrayOfBraces = new String{"{}","([{}])","{}{()}","(){}","}]{}","{[)]()}","{[)]()}","{([)]}"};
String answers = new String[arrayOfBraces.length];
String openers = "([{";
String closers = ")]}";
String stringToInspect = "";
Stack<String> stack = new Stack<String>();
for (int i = 0; i < arrayOfBraces.length; i++) {
stringToInspect = arrayOfBraces[i];
for (int j = 0; j < stringToInspect.length(); j++) {
if(stack.isEmpty()){
if (openers.indexOf(stringToInspect.charAt(j))>=0) {
stack.push(""+stringToInspect.charAt(j));
}
else{
answers[i]= "NO";
j=stringToInspect.length();
}
}
else if(openers.indexOf(stringToInspect.charAt(j))>=0){
stack.push(""+stringToInspect.charAt(j));
}
else{
String comparator = stack.pop();
int compLoc = openers.indexOf(comparator);
int thisLoc = closers.indexOf(stringToInspect.charAt(j));
if (compLoc != thisLoc) {
answers[i]= "NO";
j=stringToInspect.length();
}
else{
if(stack.empty() && (j== stringToInspect.length()-1)){
answers[i]= "YES";
}
}
}
}
}
System.out.println(answers.length);
for (int j = 0; j < answers.length; j++) {
System.out.println(answers[j]);
}
}
answered Sep 11 at 20:07
TimeTrax
19527
in java you don't want to compare the string or char by == signs. you would use equals method. equalsIgnoreCase or something of the like. if you use == it must point to the same memory location. In the method below I attempted to use ints to get around this. using ints here from the string index since every opening brace has a closing brace. I wanted to use location match instead of a comparison match. But i think with this you have to be intentional in where you place the characters of the string. Lets also consider that Yes = true and No = false for simplicity. This answer assumes that you passed an array of strings to inspect and required an array of if yes (they matched) or No (they didn't)
import java.util.Stack;
public static void main(String args) {
//String arrayOfBraces = new String{"{}","([{}])","{}{()}","{}","}]{}","{[)]()}"};
// Example: "()" is balanced
// Example: "{ ]" is not balanced.
// Examples: "(){}" is balanced.
// "{()}" is balanced
// "{([)]}" is _not_ balanced
String arrayOfBraces = new String{"{}","([{}])","{}{()}","(){}","}]{}","{[)]()}","{[)]()}","{([)]}"};
String answers = new String[arrayOfBraces.length];
String openers = "([{";
String closers = ")]}";
String stringToInspect = "";
Stack<String> stack = new Stack<String>();
for (int i = 0; i < arrayOfBraces.length; i++) {
stringToInspect = arrayOfBraces[i];
for (int j = 0; j < stringToInspect.length(); j++) {
if(stack.isEmpty()){
if (openers.indexOf(stringToInspect.charAt(j))>=0) {
stack.push(""+stringToInspect.charAt(j));
}
else{
answers[i]= "NO";
j=stringToInspect.length();
}
}
else if(openers.indexOf(stringToInspect.charAt(j))>=0){
stack.push(""+stringToInspect.charAt(j));
}
else{
String comparator = stack.pop();
int compLoc = openers.indexOf(comparator);
int thisLoc = closers.indexOf(stringToInspect.charAt(j));
if (compLoc != thisLoc) {
answers[i]= "NO";
j=stringToInspect.length();
}
else{
if(stack.empty() && (j== stringToInspect.length()-1)){
answers[i]= "YES";
}
}
}
}
}
System.out.println(answers.length);
for (int j = 0; j < answers.length; j++) {
System.out.println(answers[j]);
}
}
answered Sep 11 at 20:07
TimeTrax
19527
edited Sep 11 at 20:29
answered Sep 11 at 20:07
TimeTrax
19527
answered Sep 11 at 20:07
TimeTrax
19527
answered Sep 11 at 20:07
TimeTrax
19527
19527
add a comment |
add a comment |
draft saved
draft discarded
Thanks for contributing an answer to Stack Overflow!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
draft saved
draft discarded
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f16874176%2fparenthesis-brackets-matching-using-stack-algorithm%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
You say "parens" but you also seem to want to check brackets...
– fge
Jun 1 '13 at 15:18
1
what's so special about java here?
– SMA
Apr 1 '15 at 16:54
7
Question. Is
[ { ] }a valid matching?– Kevin
Apr 1 '15 at 17:07
3
Without a language specification (i.e. a precise answer to the question "according to which rules are the expressions you want to parse being formed") we can't answer this. Are they a context free language? They definitely aren't regular due to the parentheses alone. Are they context-sensitive? Turing-complete? Regardless of all that, this question should be on CS.SE
– G. Bach
Apr 1 '15 at 17:45
1
Or you could write a real parser instead of abusing regex.
– cpburnz
Apr 2 '15 at 19:12