Reputation:

Error in balanced brackets program in Java

I am trying with the Java program for finding condition of balanced brackets for the bracket expression
The bracket expression is said to be balanced if It contains no unmatched brackets. The subset of brackets enclosed within the confines of a matched pair of brackets is also a matched pair of brackets.
For example, if the input is given as {[()]}, then the condition of balanced bracket is YES, if it doesn't satisfy conditions, then condition is mentioned as NO.
When trying with the test case {(([])[])[]]}, the state of balanced brackets is showing as YES instead of expected output NO
I researched and debugged the code and showing the error as uncompleted bracket is missing in the stack element
can you guys provide your help to resolve the issue with your suggestions
providing the entire code below:

import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.regex.*;

public class Solution {

    // Complete the isBalanced function below.
    static String isBalanced(String s) {
        Stack<Character> bracket = new Stack<Character>();
        String decision; char element;
        //char[] s_new = s.toCharArray();
        for(int i=0; i<s.length(); i++){
            element = s.charAt(i);
            if(element == '{' || element == '[' || element == '(')
                bracket.push(element);
                //System.out.println(element);
            if((!bracket.empty()) && (element == '}') && (bracket.peek()=='{'))
                bracket.pop();
            if((!bracket.empty()) && (element == ']') && (bracket.peek()=='['))
                bracket.pop();
            if((!bracket.empty()) && (element == ')') && (bracket.peek()=='('))
                bracket.pop();
            System.out.println(bracket);
        }
        if(bracket.empty())
            decision = "YES";
        else
            decision = "NO";
        System.out.println(bracket);

        return decision;
    }

    private static final Scanner scanner = new Scanner(System.in);

    public static void main(String[] args) throws IOException {
        BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

        int t = scanner.nextInt();
        scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");

        for (int tItr = 0; tItr < t; tItr++) {
            String s = scanner.nextLine();

            String result = isBalanced(s);

            bufferedWriter.write(result);
            bufferedWriter.newLine();
        }

        bufferedWriter.close();

        scanner.close();
    }
}

Upvotes: 1

Answers (8)

Naseem Ahamed

Reputation: 129

For simplicity, let me explain in your own approach for the failure case. It looks like you have attempted it in an interview.

1) In your example, the problem is when you encounter this bracket in bold {(([])[])[]]}

At this point, your stack is not empty, the element is ] and the top of the stack has { <- In this case, there is a bracket mismatch and the loop should not go through. The loop should break and hence, the stack won't be empty. It will give the result as NO as expected

2) There is also another edge case. Lets say you have a string ]{(([])[])[]} In the first iteration, your stack will be empty and the element is an open square bracket. Whenever the stack is empty and you encounter an open bracket in any form, the condition should evaluate to false and prevent further processing of the characters.

static String  isBalanced(String s) {
    Stack<Character> bracket = new Stack<Character>();

    String decision;
    char element;
    //char[] s_new = s.toCharArray();

    for (int i = 0; i < s.length(); i++) {
        element = s.charAt(i);
        if (element == '{' || element == '[' || element == '(')
            bracket.push(element);
        else if(bracket.empty() && (element =='}' || element ==']' || element ==')'))
        {
            bracket.push(element);
            break;
        } // *******Added this 'else if' block  to support point no 2*******


        if ((!bracket.empty()) && (element == '}') && (bracket.peek() == '{'))
            bracket.pop();
        else if ((!bracket.empty()) && (element == '}') && (bracket.peek() != '{'))
            break; // *******Added this 'else if' block to support point no 1

        if ((!bracket.empty()) && (element == ']') && (bracket.peek() == '['))
            bracket.pop();
        else if ((!bracket.empty()) && (element == ']') && (bracket.peek() != '['))
            break; // *******Added this 'else if' block to support point no 1

        if ((!bracket.empty()) && (element == ')') && (bracket.peek() == '('))
            bracket.pop();
        else if ((!bracket.empty()) && (element == ')') && (bracket.peek() != '('))
            break; // *******Added this 'else if' block to support point no 1

        System.out.println(bracket);
    }
    if (bracket.empty())
        decision = "YES";
    else
        decision = "NO";
    System.out.println(bracket);

    return decision;
}

3) If the input string is empty, it is assumed that the condition evaluates to true here. If not, we can validate it in the beginning of the function and return false.

Upvotes: 0

Vimit Dhawan

Reputation: 677

package com.coursera.course2.week1;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.Stack;

class Bracket {

    char type;
    int position;

    Bracket(char type, int position) {
        this.type = type;
        this.position = position;
    }

    boolean Match(char c) {
        if (this.type == '[' && c == ']')
            return true;
        if (this.type == '{' && c == '}')
            return true;
        if (this.type == '(' && c == ')')
            return true;
        return false;
    }

}

class check_brackets {
    public static void main(String[] args) throws IOException {
        InputStreamReader input_stream = new InputStreamReader(System.in);
        BufferedReader reader = new BufferedReader(input_stream);
        String text = reader.readLine();
        Stack<Bracket> opening_brackets_stack = new Stack<Bracket>();
        for (int position = 0; position < text.length(); ++position) {
            char next = text.charAt(position);

            if (next == '(' || next == '[' || next == '{') {
                opening_brackets_stack.push(new Bracket(next,position));
            } else if (next == ')' || next == ']' || next == '}') {
                 if(!opening_brackets_stack.isEmpty() && opening_brackets_stack.peek().Match(next)) {
                     opening_brackets_stack.pop();

                 } else {
                     opening_brackets_stack.push(new Bracket(next,position));
                     break;
                 }

            }



        }
        if(opening_brackets_stack.isEmpty()) {
            System.out.println("Success");
        } else {
            System.out.println(opening_brackets_stack.pop().position+1);
        }
    }
}

Upvotes: 0

Harshavardhan reddy.

Reputation: 497

Actually you are missing one condition...what if the current element = s.charAt(i) doesnt match with stack.peep().you need to break the for loop. Add an else condition in your for loop.

'''
  for(int i=0; i<s.length(); i++){
            element = s.charAt(i);
            if(element == '{' || element == '[' || element == '(')
                bracket.push(element);
                //System.out.println(element);
            if((!bracket.empty()) && (element == '}') && (bracket.peek()=='{'))
                bracket.pop();
            else if((!bracket.empty()) && (element == ']') && (bracket.peek()=='['))
                bracket.pop();
            else if((!bracket.empty()) && (element == ')') && (bracket.peek()=='('))
                bracket.pop();
            else
                break;
            System.out.println(bracket);
        }

''' This will work for the testcases u mentioned..!!

Upvotes: 1

Oleg Cherednik

Reputation: 18245

Just be simple!

public static boolean isBalanced(String str) {
    Deque<Character> stack = new LinkedList<>();

    for (int i = 0; i < str.length(); i++) {
        char ch = str.charAt(i);

        if (ch == '{' || ch == '(' || ch == '[')
            stack.push(ch);
        else if (ch == '}' || ch == ')' || ch == ']') {
            if (stack.isEmpty())
                return false;

            char prv = stack.pop();

            if (prv == '{' && ch != '}')
                return false;
            if (prv == '(' && ch != ')')
                return false;
            if (prv == '[' && ch != ']')
                return false;
        }
    }

    return stack.isEmpty();
}

Upvotes: 0

Rowi

Reputation: 565

Here is the complete solution for Balance Bracket JAVA 8

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {

    public static boolean isBalanced(String expression) {
        char[] braces = expression.toCharArray();
        if(braces.length%2!=0){
            return false;
        }
        Map<Character, Character> endbrackets = new HashMap<Character, Character>();
        endbrackets.put('{', '}');
        endbrackets.put('[', ']');
        endbrackets.put('(', ')');
        if(endbrackets.get(braces[0]) == null){
            return false;
        }
        Stack<Character> stack= new Stack<Character>(); 
        for(int i=0; i < braces.length; i++){
            Character c = braces[i];  
            if(stack.isEmpty() && endbrackets.get(c) == null){
                 return false;
            }               
            else if(stack.isEmpty() || endbrackets.get(c) != null){
               stack.push(c); 
            }
            else if(!stack.isEmpty() && endbrackets.get(stack.peek()).equals(c)){
                stack.pop();
            } else {
                return false;
            }
        }
        if(stack.size() == 0){
            return true;
        }
        return false;
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int t = in.nextInt();
        for (int a0 = 0; a0 < t; a0++) {
            String expression = in.next();
            System.out.println( (isBalanced(expression)) ? "YES" : "NO" );
        }
    }
}

Upvotes: 0

briantaurostack7

Reputation: 1273

I would recommend you to approach such type of problems by first sketching an algorithm, anyways as pointed by the above answers you are missing the break statement and also you can use more efficient debugging techniques such as break down the problem into a simpler problem in this case yes you have the debugging prints but you also need to verify the correctness of your program by the algorithm you have sketched for it.

So for an example to debug this problem i would write a smaller program which can better help me understand the nature of the problem. for example something like this

import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.regex.*;

public class Main {

  // Complete the isBalanced function below.
  static String isBalanced(String s) {
    Stack<Character> bracket = new Stack<Character>();
    String decision;
    char element;
    // char[] s_new = s.toCharArray();
    for (int i = 0; i < s.length(); i++) {
      element = s.charAt(i);
      if (element == '{' || element == '[' || element == '(')
        bracket.push(element);
      // System.out.println(element);
      if ((!bracket.empty()) && (element == '}') && (bracket.peek() == '{'))
        bracket.pop();
      else if (element == '}' && (bracket.peek() != '{'))
        break;
      if ((!bracket.empty()) && (element == ']') && (bracket.peek() == '['))
        bracket.pop();
      else if (element == ']' && (bracket.peek() != '['))
        break;
      if ((!bracket.empty()) && (element == ')') && (bracket.peek() == '('))
        bracket.pop();
      else if (element == ')' && (bracket.peek() != '('))
        break;
      System.out.println(bracket);
    }
    if (bracket.empty())
      decision = "YES";
    else
      decision = "NO";
    System.out.println(bracket);

    return decision;
  }

  public static void main(String[] args) throws IOException {

    String s = "{(([])[])[]}";
    String result = isBalanced(s);

    System.out.println(result);

  }
}

Upvotes: 0

Mukit09

Reputation: 3399

You missed a condition. If the current element is a closing bracket but top of the stack is not opening one of the same bracket? Just think about this input: "}". As there is no opening bracket, stack has not been pushed any bracket. As stack is empty, there is no pop() as well.

So after end of loop, bracket is empty and decision is initialized to "YES". So you are getting "YES"

Upvotes: 1

Govind Sharma

Reputation: 137

I think ,it's useful for you.

   public class Solution {   
        public static boolean validBraces(String input){
            String previous = "";
            while (input.length() != previous.length())
            {
                previous = input;
                System.out.println("input"+input+"              previous"+previous);
                input = input
                    .replace("()", "")
                    .replace("[]", "")
                    .replace("{}", "");            

             }
            return (input.length() == 0);
          }

        public static void main(String[] args) {
        System.out.println(validBraces("(}[]" ));
        }
    }

Upvotes: 1

Error in balanced brackets program in Java

Answers (8)

Related Questions