Java balanced expressions check {[()]}

Question

I am trying to create a program that takes a string as an argument into its constructor. I need a method that checks whether the string is a balanced parenthesized expression. It needs to handle ( { [ ] } ) each open needs to balance with its corresponding closing bracket. For example a user could input [({})] which would be balanced and }{ would be unbalanced. This doesn't need to handle letters or numbers. I need to use a stack to do this.

I was given this pseudocode but can not figure how to implement it in java. Any advice would be awesome.

Update- sorry forgot to post what i had so far. Its all messed up because at first i was trying to use char and then i tried an array.. im not exactly sure where to go.

import java.util.*;

public class Expression
{
  Scanner in = new Scanner(System.in);
  Stack<Integer> stack = new Stack<Integer>();



  public boolean check()
  {
    System.out.println("Please enter your expression.");
    String newExp = in.next();
    String[] exp = new String[newExp];
    for (int i = 0; i < size; i++)
    { 


      char ch = exp.charAt(i);
      if (ch == '(' || ch == '[' || ch == '{')
        stack.push(i);
      else if (ch == ')'|| ch == ']' || ch == '}')
      {
        //nothing to match with
        if(stack.isEmpty())
        {  
          return false;
        }
        else if(stack.pop() != ch)
        { 
          return false;
        } 

      }            
    }
    if (stack.isEmpty())
    {
      return true;
    }
    else
    {
      return false;
    }
  }


}

Wagstaff

The pseudo code algorithm looks accurate why don't you post what you have for your implementation so far. – Brittneybrittni

void main(String[] args...) { //code here }; Sorry for being harsh, but you even have the pseudocode, you have to translate it to Java. Or at least give it a try, and fail on your own... Maybe, if there was any sign of effort in your question - as detailed in the FAQ - would have helped to get some help instead of some stale cynism... – Aboulia

i posted what i had been working on so far i forgot to post in the beginning, thanks so much – Wagstaff

You start by pushing the index of the loop onto the stack, and then you try and pop off a character. You should use a Character stack and push the opening braces onto it. Then, when you find a closing brace, pop the top element off and see if it correctly matches the open brace. Then keep going. If you have an empty stack at the end, the string is balanced. – Malley

codereview.stackexchange.com/questions/45916/… check it you will get batter idea. – Harrietteharrigan

Answer 1

I hope this code can help:

import java.util.Stack;

public class BalancedParenthensies {

    public static void main(String args[]) {

        System.out.println(balancedParenthensies("{(a,b)}"));
        System.out.println(balancedParenthensies("{(a},b)"));
        System.out.println(balancedParenthensies("{)(a,b}"));
    }

    public static boolean balancedParenthensies(String s) {
        Stack<Character> stack  = new Stack<Character>();
        for(int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if(c == '[' || c == '(' || c == '{' ) {     
                stack.push(c);
            } else if(c == ']') {
                if(stack.isEmpty() || stack.pop() != '[') {
                    return false;
                }
            } else if(c == ')') {
                if(stack.isEmpty() || stack.pop() != '(') {
                    return false;
                }           
            } else if(c == '}') {
                if(stack.isEmpty() || stack.pop() != '{') {
                    return false;
                }
            }

        }
        return stack.isEmpty();
    }
}

Hominy

I see that you can merge the nested IFs. – Addle

Answer 2

public static boolean isBalanced(String expression) {
  if ((expression.length() % 2) == 1) return false;
  else {
    Stack<Character> s = new Stack<>();
    for (char bracket : expression.toCharArray())
      switch (bracket) {
        case '{': s.push('}'); break;
        case '(': s.push(')'); break;
        case '[': s.push(']'); break;
        default :
          if (s.isEmpty() || bracket != s.peek()) { return false;}
          s.pop();
      }
    return s.isEmpty();
  }
}

public static void main(String[] args) {
    Scanner in = new Scanner(System.in);
    String expression = in.nextLine();
    boolean answer = isBalanced(expression);
    if (answer) { System.out.println("YES");}
    else { System.out.println("NO");}

}

Nepos

Answer 3

The pseudo code equivalent java implementation of the algorithm is java is as follows.

import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

/**
 * @author Yogen Rai
 */

public class BalancedBraces
{
    public static void main(String[] args) {
        System.out.println(isBalanced("{{}}") ? "YES" : "NO"); // YES
        System.out.println(isBalanced("{{}(") ? "YES" : "NO"); // NO 
        System.out.println(isBalanced("{()}") ? "YES" : "NO"); // YES 
        System.out.println(isBalanced("}{{}}") ? "YES" : "NO"); // NO
    }

    public static boolean isBalanced(String brackets) {
        // set matching pairs
        Map<Character, Character> braces = new HashMap<>();
        braces.put('(', ')');
        braces.put('[',']');
        braces.put('{','}');

        // if length of string is odd, then it is not balanced
        if (brackets.length() % 2 != 0) {
            return false;
        }

        // travel half until openings are found and compare with
        // remaining if the closings matches
        Stack<Character> halfBraces = new Stack();
        for(char ch: brackets.toCharArray()) {
            if (braces.containsKey(ch)) {
                halfBraces.push(braces.get(ch));
            }
            // if stack is empty or if closing bracket is not equal to top of stack,
            // then braces are not balanced
            else if(halfBraces.isEmpty() || ch != halfBraces.pop()) {
                return false;
            }
        }
        return halfBraces.isEmpty();
    }
}

Hassett

Nice! This is more data drive than the other answers - so you could easily expand it to include 100 different types of braces without changing the code (if you passed the braces data in of course!) – Blowup

@Yogen Rai My comment is related to the length of the string, I don't think if its length is not even that makes it unbalanced, for example "(A)" has a length of 3 but is balanced since it has a balanced number of brackets (opening ones and closing ones). That being said I would remove the logic that assumes only even strings are balanced. – Deva

@EbillsonGRANDJEAN i agree if input string can contain characters other than ( { [ ] } ), but questions says it only got ` ( { [ ] } )` characters – Hassett

Answer 4

It's important to use a stack to push opening symbols onto it, then when you come across a closing brace you pop the element off the top of the stack and then you check it to see if it matches the type of closing brace. Here is a java implementation.

import java.util.Stack;

public class Balanced {
    public static void main (String [] args)
    {
        String test_good = "()(){}{}{()}";
        String test_bad = "((({}{}))()";

        System.out.println(checkBalanced(test_good));
        System.out.println(checkBalanced(test_bad));
    }

    public static boolean checkBalanced(String check)
    {
        Stack<Character> S = new Stack<Character>();
        for(int a = 0; a < check.length(); a++)
        {
            char let = check.charAt(a);
            if(let == '[' || let == '{' || let == '(')
                S.push(let);
            else if(let == ']' || let == '}' || let == ')')
            {
                if(S.empty())
                    return false;
                switch(let)
                {
                    // Opening square brace
                    case ']':
                        if (S.pop() != '[')
                            return false;
                        break;
                    // Opening curly brace
                    case '}':
                        if (S.pop() != '{')
                            return false;
                        break;
                    // Opening paren brace
                    case ')':
                        if (S.pop() != '(')
                            return false;
                        break;
                    default:
                        break;
                }
            }
        }
        if(S.empty())
            return true;
        return false;
    }
}

Malley

You can use char in switch cases, and you can compare (even an int) against a char literal as well. – Ignoramus

^truth, probably better to use char, will update now. – Malley

Answer 5

Do you mind, if I will add my freaky-style solution based on JavaScript?

It's an ad-hoc stuff, not for production, but for the interviews or something like that. Or just for fun.

The code:

function reduceStr (str) {
  const newStr = str.replace('()', '').replace('{}', '').replace('[]', '')
  if (newStr !== str) return reduceStr(newStr)
  return newStr
}

function verifyNesting (str) {
  return reduceStr(str).length === 0
}

Checks:

console.log(verifyNesting('[{{[(){}]}}[]{}{{(())}}]')) //correct
console.log(verifyNesting('[{{[(){}]}}[]{}{({())}}]')) //incorrect

Explanation:

It will recursively remove closes pairs "()", "[]" and "{}":

'[{{[(){}]}}[]{}{{(())}}]'
'[{{}}[]{}{{(())}}]'
'[{}{}{{()}}]'
'[{}{{}}]'
'[{{}}]'
'[{}]'
'' 

If at the end string's length will be empty - it's true, if not - it's false.

P.S. Few answers

• Why not for production?

Because it's slow, and don't care about the possibility of some other characters between pairs.

• Why JS? We love Java

Because I'm a frontend developer but met the same task, so perhaps it can be useful for somebody. And JS is also JVM lang =)

• But why...

Because all JS developers are crazy, that's why.

Garik

Answer 6

This is my own implementation. I tried to make it the shortest an clearest way possible:

public static boolean isBraceBalanced(String braces) {
    Stack<Character> stack = new Stack<Character>();

    for(char c : braces.toCharArray()) {
        if(c == '(' || c == '[' || c == '{') {
            stack.push(c);
        } else if((c == ')' && (stack.isEmpty() || stack.pop() != '(')) ||
                  (c == ']' && (stack.isEmpty() || stack.pop() != '[')) ||
                  (c == '}' && (stack.isEmpty() || stack.pop() != '{'))) {
            return false;
        }
    }

    return stack.isEmpty();
}

Apomorphine

Answer 7

You are pushing i - the index - on the stack, and comparing against ch. You should push and pop ch.

Ignoramus

Answer 8

Please try this.

    import java.util.Stack;

    public class PatternMatcher {
        static String[] patterns = { "{([])}", "{}[]()", "(}{}]]", "{()", "{}" };
        static String openItems = "{([";

        boolean isOpen(String sy) {
            return openItems.contains(sy);
        }

        String getOpenSymbol(String byCloseSymbol) {
            switch (byCloseSymbol) {
            case "}":
                return "{";
            case "]":
                return "[";
            case ")":
                return "(";

            default:
                return null;
            }
        }

        boolean isValid(String pattern) {

            if(pattern == null) {
                return false;
            }

            Stack<String> stack = new Stack<String>();
            char[] symbols = pattern.toCharArray();

            if (symbols.length == 0 || symbols.length % 2 != 0) {
                return false;
            }

            for (char c : symbols) {
                String symbol = Character.toString(c);
                if (isOpen(symbol)) {
                    stack.push(symbol);
                } else {
                    String openSymbol = getOpenSymbol(symbol);
                    if (stack.isEmpty() 
                            || openSymbol == null 
                            || !openSymbol.equals(stack.pop())) {
                        return false;
                    }
                }
            }
            return stack.isEmpty();
        }

        public static void main(String[] args) {
            PatternMatcher patternMatcher = new PatternMatcher();

            for (String pattern : patterns) {
                boolean valid = patternMatcher.isValid(pattern);
                System.out.println(pattern + "\t" + valid);
            }
        }

    }

Firewarden

Answer 9

Using switch-case for better readability and handling of other scenarios:

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

public class JavaStack
{
    private static final Scanner scanner = new Scanner(System.in);

    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            String input = sc.next();
            System.out.println(isStringBalanced(input));
        }
        scanner.close();

    }

    private static boolean isStringBalanced(String testString)
    {
        Stack<Character> stack = new Stack<Character>();
        for (char c : testString.toCharArray()) {
            switch (c) {
                case '[':
                case '(':
                case '{':
                    stack.push(c);
                    break;
                case ']':
                    if (stack.isEmpty() || stack.pop() != '[') {
                        return false;
                    }
                    break;
                case ')':
                    if (stack.isEmpty() || stack.pop() != '(') {
                        return false;
                    }
                    break;
                case '}':
                    if (stack.isEmpty() || stack.pop() != '{') {
                        return false;
                    }
                    break;
                default:
                    break;
            }
        }
        // stack has to be empty, if not, the balance was wrong
        return stack.empty();
    }
}

Inboard

Answer 10

This is my implementation for this question. This program allows numbers, alphabets and special characters with input string but simply ignore them while processing the string.

CODE:

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

public class StringCheck {

    public static void main(String[] args) {
        boolean flag =false;
        Stack<Character> input = new Stack<Character>();
        System.out.println("Enter your String to check:");
        Scanner scanner = new Scanner(System.in);
        String sinput = scanner.nextLine();
        char[] c = new char[15];
        c = sinput.toCharArray();
        for (int i = 0; i < c.length; i++) {
            if (c[i] == '{' || c[i] == '(' || c[i] == '[')
                input.push(c[i]);
            else if (c[i] == ']') {
                if (input.pop() == '[') {
                    flag = true;
                    continue;
                } else {
                    flag = false;
                    break;
                }
            } else if (c[i] == ')') {
                if (input.pop() == '(') {
                    flag = true;
                    continue;
                } else {
                    flag = false;
                    break;
                }
            } else if (c[i] == '}') {
                if (input.pop() == '{') {
                    flag = true;
                    continue;
                } else {
                    flag = false;
                    break;
                }
            }
        }
        if (flag == true)
            System.out.println("Valid String");
        else
            System.out.println("Invalid String");
        scanner.close();

    }

}

Fairing

Answer 11

This code works for all cases include other chars not only parentheses ex:
Please enter input

{ibrahim[k]}
true

()[]{}[][]
true

saddsd] false

public class Solution {

    private static Map<Character, Character> parenthesesMapLeft = new HashMap<>();
    private static Map<Character, Character> parenthesesMapRight = new HashMap<>();

    static {
        parenthesesMapLeft.put('(', '(');
        parenthesesMapRight.put(')', '(');
        parenthesesMapLeft.put('[', '[');
        parenthesesMapRight.put(']', '[');
        parenthesesMapLeft.put('{', '{');
        parenthesesMapRight.put('}', '{');
    }

    public static void main(String[] args) {
        System.out.println("Please enter input");
        Scanner scanner = new Scanner(System.in);

        String str = scanner.nextLine();

        System.out.println(isBalanced(str));
    }

    public static boolean isBalanced(String str) {

        boolean result = false;
        if (str.length() < 2)
            return false;
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < str.length(); i++) {

            char ch = str.charAt(i);
            if (!parenthesesMapRight.containsKey(ch) && !parenthesesMapLeft.containsKey(ch)) {
                continue;
            }
            if (parenthesesMapLeft.containsKey(ch)) {
                stack.push(ch);
            } else {
                if (!stack.isEmpty() && stack.pop() == parenthesesMapRight.get(ch).charValue()) {
                    result = true;
                } else {
                    return false;
                }
            }

        }
        if (!stack.isEmpty())
            return result = false;
        return result;
    }
}

Chemism

Answer 12

class ParenthesisChecker
{

public static void main(String[] args) {

    // sample input
    //[{()}]
    // {}{(}))}  -> unbalanced
    //  [{()}{()}]

    Scanner sc = new Scanner(System.in);

    //Reading total number of testcases
    int t= sc.nextInt();

    while(t-- >0)
    {
        //reading the string
        String st = sc.next();
        System.out.println(isBalancedParenthesis(st));
    }
}

//Function to check if brackets are balanced or not.
public static boolean isBalancedParenthesis(String x)
{
    
    String open = "[{(";
    String close = ")}]";

    int n = x.length();

    /*
    
    base case :
    if (n is odd means either opening or closing parenthesis is missing in x ,
        first character of x contains closing parenthesis ,
        last character of x contains opening parenthesis)
            return false
    
     Note: code works fine without this if block.
    */

    /*
    if( n%2 != 0 ||
        close.contains(String.valueOf(x.charAt(0))) ||
            open.contains(String.valueOf(x.charAt(n-1))))
        return false;
    */
    if( n%2 == 0 ){

        Stack<Character> bracketStack = new Stack<>();

        for (int i = 0; i < n; i++) {
            char ch = x.charAt(i);
            if (open.contains(String.valueOf(ch)))
                bracketStack.push(ch);
            else if (!bracketStack.isEmpty() &&
                        (bracketStack.peek() == '[' && (ch == ']') ||
                        bracketStack.peek() == '{' && (ch == '}') ||
                        bracketStack.peek() == '(' && (ch == ')')))
                bracketStack.pop();
            else 
                return false;
                
        }
        return bracketStack.isEmpty();
    }
    return false;
}
}
    
    
    

Translucid

Hello, welcome to SO. In general, adding some kind of commentary or explanation instead of just giving the code is better. So please edit your answer and try to describe what it does and how. Thank you! – Elaterin

Answer 13

Similar to one of the code above in JAVA but It needs one more else statement added in order to avoid stack comparison with characters other than braces :

else if(bracketPair.containsValue(strExpression.charAt(i)))

public boolean isBalanced(String strExpression){
 Map<Character,Character> bracketPair = new HashMap<Character,Character>();
  bracketPair.put('(', ')');
  bracketPair.put('[', ']');
  bracketPair.put('{', '}');
  Stack<Character> stk = new Stack<Character>();
        for(int i =0;i<strExpression.length();i++){
            if(bracketPair.containsKey(strExpression.charAt(i)))
                stk.push(strExpression.charAt(i));
            else if(bracketPair.containsValue(strExpression.charAt(i))) 
                if(stk.isEmpty()||bracketPair.get(stk.pop())!=strExpression.charAt(i))
                return false;
        }

        if(stk.isEmpty())
            return true;
            else
                return false;
        }

Mylor

Answer 14

An alternative to Hashmap and an efficient way would be to use a Deque:

public boolean isValid(String s) 
{
    if(s == null || s.length() == 0)
        return true;

     Deque<Character> stack = new ArrayDeque<Character>();
     for(char c : s.toCharArray()) 
     {
         if(c == '{')
            stack.addFirst('}');

          else if(c == '(')
            stack.addFirst(')');

           else if(c == '[')
              stack .addFirst(']');

            else if(stack.isEmpty() || c != stack.removeFirst())
               return false;
     }
             return stack.isEmpty();
}

Boehmite

I think checking for s == null is not useful because in that case s.length() will throw an exception. – Cromer

In the condition where s == null, it would not reach the condition to check s.length(). This is called a Short Circuit Evaluation in java where if the operand is || and the first condition itself is true, it would return true without checking the other condition. That is why we check null conditions first – Boehmite

Answer 15

Late Post.

package com.prac.stack;

public class BalanceBrackets {

public static void main(String[] args) {
    String str = "{()}[]";
    char a[] = str.toCharArray();
    System.out.println(check(a));
}

static boolean check(char[] t) {
    Stackk st = new Stackk();
    for (int i = 0; i < t.length; i++) {
        if (t[i] == '{' || t[i] == '(' || t[i] == '[') {
            st.push(t[i]);
        }
        if (t[i] == '}' || t[i] == ')' || t[i] == ']') {
            if (st.isEmpty()) {
                return false;
            } else if (!isMatching(st.pop(), t[i])) {
                return false;
            }
        }
    }

    if (st.isEmpty()) {
        return true;
    } else {
        return false;
    }
}

static boolean isMatching(char a, char b) {
    if (a == '(' && b == ')') {
        return true;
    } else if (a == '{' && b == '}') {
        return true;
    } else if (a == '[' && b == ']') {
        return true;
    } else {
        return false;
    }
}

}

Codee

Answer 16

public static void main(String[] args) {
    
    String exp = "{[()()]()}";
    if(isBalanced(exp)){
        System.out.println("Balanced");
    }else{
        System.out.println("Not Balanced");
    }
    
}

public static boolean isBalanced(String exp){
    Stack<Character> stack = new Stack<Character>();
    
    for (int i = 0; i < exp.length(); i++) {
        char a = exp.charAt(i);
        char b =' ';
        if(!stack.isEmpty()){
            b = stack.peek();
        }
        if(a == '(' || a == '[' || a == '{'){
            stack.push(a);
            continue;
        }
        else if((b == '(' && a == ')') || (b == '[' && a == ']') || (b == '{' && a == '}')){
            stack.pop();
            continue;
        }
        else{
            return false;
        }
    }
    return stack.isEmpty();
}

Stack is always most preferable data structure in this case, you can try this by considering time and space complexity.

Pressmark

Answer 17

import java.util.Stack;

        public class StackParenthesisImplementation {
            public static void main(String[] args) {
                String Parenthesis = "[({})]";
                char[] charParenthesis  = Parenthesis.toCharArray();
                boolean evalParanthesisValue = evalParanthesis(charParenthesis);
                if(evalParanthesisValue == true)
                    System.out.println("Brackets are good");
                else
                    System.out.println("Brackets are not good");
            }
            static boolean evalParanthesis(char[] brackets)
            {       
                boolean IsBracesOk = false;
                boolean PairCount = false;
                Stack<Character> stack = new Stack<Character>();
                for(char brace : brackets)
                {                       
                    if(brace == '(' || brace == '{' || brace == '['){
                        stack.push(brace);  
                        PairCount = false;
                    }
                    else if(!stack.isEmpty())
                    {
                        if(brace == ')' || brace == '}' || brace == ']')
                        {
                            char CharPop = stack.pop();
                            if((brace == ')' && CharPop == '('))
                            {
                                IsBracesOk = true; PairCount = true;
                            }
                            else if((brace == '}') && (CharPop == '{'))
                            {
                                IsBracesOk = true; PairCount = true;
                            }
                            else if((brace == ']') && (CharPop == '['))
                            {
                                IsBracesOk = true; PairCount = true;
                            }
                            else 
                            {
                                IsBracesOk = false;
                                PairCount = false;
                                break;
                            }
                        }   
                    }
                }   
                if(PairCount == false)
                return IsBracesOk = false;
                else
                    return IsBracesOk = true;
            }
        }

Siu

Answer 18

public static void main(String[] args) {
    System.out.println("is balanced : "+isBalanced("(){}[]<>"));
    System.out.println("is balanced : "+isBalanced("({})[]<>"));
    System.out.println("is balanced : "+isBalanced("({[]})<>"));
    System.out.println("is balanced : "+isBalanced("({[<>]})"));
    System.out.println("is balanced : "+isBalanced("({})[<>]"));


    System.out.println("is balanced : "+isBalanced("({[}])[<>]"));
    System.out.println("is balanced : "+isBalanced("([{})]"));
    System.out.println("is balanced : "+isBalanced("[({}])"));
    System.out.println("is balanced : "+isBalanced("[(<{>})]"));

    System.out.println("is balanced : "+isBalanced("["));
    System.out.println("is balanced : "+isBalanced("]"));

    System.out.println("is balanced : "+isBalanced("asdlsa"));
}

private static boolean isBalanced(String brackets){
    char[] bracketsArray = brackets.toCharArray();
    Stack<Character> stack = new Stack<Character>();
    Map<Character, Character> openingClosingMap = initOpeningClosingMap();

    for (char bracket : bracketsArray) {
        if(openingClosingMap.keySet().contains(bracket)){ 
            stack.push(bracket);
        }else if(openingClosingMap.values().contains(bracket)){
            if(stack.isEmpty() || openingClosingMap.get(stack.pop())!=bracket){
                return false;
            }
        }else{
            System.out.println("Only  < > ( ) { } [ ] brackets  are allowed .");
            return false;
        }
    }
    return stack.isEmpty();
}

private static Map<Character, Character> initOpeningClosingMap() {
    Map<Character, Character> openingClosingMap = new HashMap<Character, Character>();
    openingClosingMap.put(Character.valueOf('('), Character.valueOf(')'));
    openingClosingMap.put(Character.valueOf('{'), Character.valueOf('}'));
    openingClosingMap.put(Character.valueOf('['), Character.valueOf(']'));
    openingClosingMap.put(Character.valueOf('<'), Character.valueOf('>'));
    return openingClosingMap;
}

Simplifying and making readable. Using One Map only and minimum conditions to get desired result.

Drysalter

Answer 19

How about this one, it uses both concept of stack plus counter checks:

import java.util.*;
class Solution{

public static void main(String []argh)
{
   Scanner sc = new Scanner(System.in);
   while (sc.hasNext()) {
      String input=sc.next();
      Stack<Character> stk = new Stack<Character>();
      char[] chr = input.toCharArray();
      int ctrl = 0, ctrr = 0;
      if(input.length()==0){
          System.out.println("true");
      }
      for(int i=0; i<input.length(); i++){
          if(chr[i]=='{'||chr[i]=='('||chr[i]=='['){
              ctrl++;
              stk.push(chr[i]);
              //System.out.println(stk);
          }
      }
      for(int i=0; i<input.length(); i++){
          if(chr[i]=='}'||chr[i]==')'||chr[i]==']'){
              ctrr++;
              if(!stk.isEmpty())
                  stk.pop();
              //System.out.println(stk);
          }
      }
      //System.out.println(stk);
      if(stk.isEmpty()&&ctrl==ctrr)
        System.out.println("true");
      else
        System.out.println("false");
      }
   }
}

Purity

Answer 20

This can be used. Passes all the tests.

static String isBalanced(String s) {

    if(null == s){
        return "";
    }

    Stack<Character> bracketStack = new Stack<>();


    int length = s.length();

    if(length < 2 || length > 1000){
        return "NO";
    }


    for(int i = 0; i < length; i++){
        Character c= s.charAt(i);
        if(c == '(' || c == '{' || c == '[' ){
            bracketStack.push(c);
        } else {
            if(!bracketStack.isEmpty()){
               char cPop = bracketStack.pop();

               if(c == ']' && cPop!= '['){
                  return "NO";
               }

               if(c == ')' && cPop!= '('){
                  return "NO";
               }

               if(c == '}' && cPop!= '{'){
                  return "NO";
               }
            } else{
                return "NO";
            }

        }
    }

    if(bracketStack.isEmpty()){
        return "YES";
    } else {
        return "NO";
    }

}

Pickford

Answer 21

Please try this I checked it. It works correctly

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map;
import java.util.Stack;
public class CloseBrackets {
    private static Map<Character, Character> leftChar = new HashMap<>();
    private static Map<Character, Character> rightChar = new HashMap<>();

    static {
        leftChar.put('(', '(');
        rightChar.put(')', '(');
        leftChar.put('[', '[');
        rightChar.put(']', '[');
        leftChar.put('{', '{');
        rightChar.put('}', '{');
    }

    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        String st = bf.readLine();
        System.out.println(isBalanced(st));
    }

    public static boolean isBalanced(String str) {

        boolean result = false;
        if (str.length() < 2)
            return false;
        Stack<Character> stack = new Stack<>();
        /* For Example I gave input 
         * str = "{()[]}" 
         */

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

            char ch = str.charAt(i);
            if (!rightChar.containsKey(ch) && !leftChar.containsKey(ch)) {
                continue;
            }
            // Left bracket only add to stack. Other wise it will goes to else case 
            // For both above input how value added in stack 
            // "{(" after close bracket go to else case
            if (leftChar.containsKey(ch)) {
                stack.push(ch);
            } else {
                if (!stack.isEmpty()) {
                    // For both input how it performs
                    // 3rd character is close bracket so it will pop . pop value is "(" and map value for ")" key will "(" . So both are same . 
                    // it will return true. 
                    // now stack will contain only "{" , and travers to next up to end.
                    if (stack.pop() == rightChar.get(ch).charValue() || stack.isEmpty()) {
                        result = true;
                    } else {
                        return false;
                    }
                } else {
                    return false;
                }
            }

        }
        if (!stack.isEmpty())
            return result = false;
        return result;
    }
}

Cough

Answer 22

Here is the Code. I have tested all the possible test case on Hacker Rank.

static String isBalanced(String input) {

    Stack<Character> stack = new Stack<Character>();
    for (int i = 0; i < input.length(); i++) {
        Character ch = input.charAt(i);
        if (input.charAt(i) == '{' || input.charAt(i) == '['
                || input.charAt(i) == '(') {
            stack.push(input.charAt(i));
        } else {
            if (stack.isEmpty() 
                    || (stack.peek() == '[' && ch != ']')
                    || (stack.peek() == '{' && ch != '}')
                    || (stack.peek() == '(' && ch != ')')) {
                return "NO";
            } else {
                stack.pop();
            }
        }
    }
    if (stack.empty())
        return "YES";
    return "NO";

}

Banksia

Answer 23

Using node reference we can check easily

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;



public class CloseBracketsBalance {
    private static final Map<String, String> closeBracket= new HashMap<>();
    private static final List<String> allBrac = new ArrayList<>();

    static {
        allBrac.add("[");
        allBrac.add("]");
        allBrac.add("{");
        allBrac.add("}");
        allBrac.add("(");
        allBrac.add(")");
        closeBracket.put("]", "[");
        closeBracket.put("}", "{");
        closeBracket.put(")", "(");
    }

    public static void main(String[] args) {
        System.out.println(checkSheetIsbalance("[{}({[]{}(dsfd)})]")); // return true
        System.out.println(checkSheetIsbalance("[{}({[]{}(dsfd}))]")); // return false
    }

    public static boolean checkSheetIsbalance(String c) {
        char[] charArr = c.toCharArray();
        Node node = null;
        for(int i=0,j=charArr.length;i<j;i++) {
            String ch = charArr[i]+"";
            if(!allBrac.contains(ch)) {
                continue;
            }

            if(closeBracket.containsKey(ch)) {
                // node close bracket               
                if(node == null) {
                    return false;
                }
                if(!(node.nodeElement).equals(closeBracket.get(ch))) {
                    return false;
                }
                node = node.parent; 
            } else {
                //make node for open bracket                
                 node = new Node(ch, node);
            }
        }       

        if(node != null) {
            return false;
        }

        return true;
    }
}


class Node {
    public String nodeElement;
    public Node parent;
    public Node(String el, Node p) {
        this.nodeElement = el;
        this.parent = p;
    }
}

Radionuclide

Answer 24

The improved method, from @Smartoop.

public boolean balancedParenthensies(String str) {
    List<Character> leftKeys = Arrays.asList('{', '(', '<', '[');
    List<Character> rightKeys = Arrays.asList('}', ')', '>', ']');

    Stack<Character> stack = new Stack<>();
    for (int i = 0; i < str.length(); i++) {
        char c = str.charAt(i);
        if (leftKeys.contains(c)) {
            stack.push(c);
        } else if (rightKeys.contains(c)) {
            int index = rightKeys.indexOf(c);
            if (stack.isEmpty() || stack.pop() != leftKeys.get(index)) {
                return false;
            }
        }
    }
    return stack.isEmpty();
}

Loudspeaker

Answer 25

public void validateExpression(){

    if(!str.isEmpty() && str != null){
        if( !str.trim().equals("(") && !str.trim().equals(")")){

            char[] chars = str.toCharArray();

            for(char c: chars){
                if(!Character.isLetterOrDigit(c) && c == '('  || c == ')') {
                    charList.add(c);
                }
            }

            for(Character ele: charList){                   
                if(operatorMap.get(ele) != null && operatorMap.get(ele) != 0){                      
                    operatorMap.put(ele,operatorMap.get(ele)+1);
                }else{
                    operatorMap.put(ele,1);
                }
            }

            for(Map.Entry<Character, Integer> ele: operatorMap.entrySet()){
                System.out.println(String.format("Brace Type \"%s\" and count is \"%d\" ", ele.getKey(),ele.getValue()));                   
            }

            if(operatorMap.get('(') == operatorMap.get(')')){
                System.out.println("**** Valid Expression ****");
            }else{
                System.out.println("**** Invalid Expression ****");
            }

        }else{
            System.out.println("**** Incomplete expression to validate ****");
        }

    }else{
        System.out.println("**** Expression is  empty or null ****");
    }       
}

Yearbook

Answer 26

Considering string consists only of '(' ')' '{' '}' '[' ']'. Here is a code method that returns true or false based on whether equation is balanced or not.

private static boolean checkEquation(String input) {

    List<Character> charList = new ArrayList<Character>();

    for (int i = 0; i < input.length(); i++) {

        if (input.charAt(i) == '(' || input.charAt(i) == '{' || input.charAt(i) == '[') {
            charList.add(input.charAt(i));
        } else if ((input.charAt(i) == ')' && charList.get(charList.size() - 1) == '(')
                || (input.charAt(i) == '}' && charList.get(charList.size() - 1) == '{')
                || (input.charAt(i) == ']' && charList.get(charList.size() - 1) == '[')) {
            charList.remove(charList.size() - 1);
        } else
            return false;

    }

    if(charList.isEmpty())
        return true;
    else
        return false;
}

Koski

Answer 27

///check Parenthesis
public boolean isValid(String s) {
    Map<Character, Character> map = new HashMap<>();
    map.put('(', ')');
    map.put('[', ']');
    map.put('{', '}');
    Stack<Character> stack = new Stack<>();
    for(char c : s.toCharArray()){
        if(map.containsKey(c)){
            stack.push(c);
        } else if(!stack.empty() && map.get(stack.peek())==c){
            stack.pop();
        } else {
            return false;
        }
    }
    return stack.empty();
}

Relume

Answer 28

package Stack;

import java.util.Stack;

public class BalancingParenthesis {

 boolean isBalanced(String s) {

    Stack<Character> stack = new Stack<Character>();

    for (int i = 0; i < s.length(); i++) {

        if (s.charAt(i) == '(' || s.charAt(i) == '{' || s.charAt(i) == '[') {

            stack.push(s.charAt(i)); // push to the stack

        }

        if (s.charAt(i) == ')' || s.charAt(i) == '}' || s.charAt(i) == ']') {

            if (stack.isEmpty()) {
                return false; // return false as there is nothing to match
            }

            Character top = stack.pop(); // to get the top element in the stack

            if (top == '(' && s.charAt(i) != ')' || top == '{' && s.charAt(i) != '}'
                    || top == '[' && s.charAt(i) != ']') {

                return false;
            }

        }

    }

    if (stack.isEmpty()) {
        return true; // check if every symbol is matched
    }

    return false; // if some symbols were unmatched
}

public static void main(String[] args) {

    BalancingParenthesis obj = new BalancingParenthesis();

    System.out.println(obj.isBalanced("()[]{}[][]"));

}

}

// Time Complexity : O(n)

Shyamal

Answer 29

import java.util.Objects;
import java.util.Stack;

public class BalanceBrackets {

    public static void main(String[] args) {
        String input="(a{[d]}b)";
        System.out.println(isBalance(input));  ;
    }

    private static boolean isBalance(String input) {
        Stack <Character> stackFixLength = new Stack();

        if(input == null || input.length() < 2) {
            throw  new IllegalArgumentException("in-valid arguments");
        }

        for (int i = 0; i < input.length(); i++) {

            if (input.charAt(i) == '(' || input.charAt(i) == '{' || input.charAt(i) == '[') {
                stackFixLength.push(input.charAt(i));
            }

            if (input.charAt(i) == ')' || input.charAt(i) == '}' || input.charAt(i) == ']') {

                if(stackFixLength.empty()) return false;

                char b = stackFixLength.pop();

                if (input.charAt(i) == ')' && b == '(' || input.charAt(i) == '}' && b == '{' || input.charAt(i) == ']' && b == '[') {
                    continue;
                } else {
                    return false;
                }
            }
        }

        return stackFixLength.isEmpty();
    }
}

Rozina

Answer 30

Code snippet for implementing matching parenthesis using java.util.Stack data structure -

    //map for storing matching parenthesis pairs
    private static final Map<Character, Character> matchingParenMap = new HashMap<>();

    //set for storing opening parenthesis
    private static final Set<Character> openingParenSet = new HashSet<>();

    static {
         matchingParenMap.put(')','(');
         matchingParenMap.put(']','['); 
         matchingParenMap.put('}','{'); 
         openingParenSet.addAll(matchingParenMap.values());  
    }

    //check if parenthesis match
    public static boolean hasMatchingParen(String input) {
      try {
         //stack to store opening parenthesis
         Stack<Character> parenStack = new Stack<>();

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

            //if an opening parenthesis then push to the stack
            if(openingParenSet.contains(ch)) {
                 parenStack.push(ch);
            } 

            //for closing parenthesis
            if(matchingParenMap.containsKey(ch)) {
                 Character lastParen = parenStack.pop();
                 if(lastParen != matchingParenMap.get(ch)) {
                    return false;
                 } 
            }
         }

         //returns true if the stack is empty else false
         return parenStack.isEmpty();
       }
         catch(StackOverflowException s) {}
         catch(StackUnderflowException s1) {}
         return false;
    }

I have explained the code snippet and the algorithm used on blog http://hetalrachh.home.blog/2019/12/25/stack-data-structure/

Asseveration

Answer 31

public class StackProb {

public static void main(String[] args) {

    Scanner sc = new Scanner(System.in);
    List<Boolean> list = new ArrayList<>();

    while (sc.hasNextLine()) {
        String s=sc.nextLine();
        if(!s.isEmpty()) {
            list.add(isBalanced(s));
            //System.out.println(isBalanced(s));
        }else {
            sc.close();
            break;
        }
    }

    for (int i = 0; i < list.size(); i++) {
        System.out.println(list.get(i) + " ");
    }

}

private static boolean isBalanced(String s) {
    boolean res = false;
    Stack<Character> stack = new Stack();
    int countA = 0;
    int countB = 0;
    for (int i = 0; i < s.length(); i++) {

        if(s.charAt(i)=='{' || s.charAt(i)=='(' || s.charAt(i)=='[') {

            stack.push(s.charAt(i));
            countA++;
        }


        if(s.charAt(i)=='}' || s.charAt(i)==')' || s.charAt(i)==']') {

            stack.push(s.charAt(i));
            countB++;
        }

        if(stack.firstElement()=='}' || stack.firstElement()==')' || stack.firstElement()==']') {
            countB++;
        }


    }
    if(countA==countB) {
        return true;
    }
    return false;

}

}

Kamerman

This is an easy approach to solve the Stack balanced problem. solved HackerRank hackerrank.com/challenges/java-stack/… problem and all test cases got passed – Kamerman

Answer 32

A slightly different approach I took to solve this problem, I have observed two key points in this problem.

1. Open braces should be accompanied always with corresponding closed braces.
2. Different Open braces are allowed together but not different closed braces.

So I converted these points into easy-to-implement and understandable format.

1. I represented different braces with different numbers
2. Gave positive sign to open braces and negative sign for closed braces.

For Example : "{ } ( ) [ ]" will be "1 -1 2 -2 3 -3" is valid parenthesis. For a balanced parenthesis, positives can be adjacent where as a negative number should be of positive number in top of the stack.

Below is code:

import java.util.Stack;

public class Main {
    public static void main (String [] args)
    {
        String value = "()(){}{}{()}";
        System.out.println(Main.balancedParanthesis(value));
       
    }

public static boolean balancedParanthesis(String s) {
        
        
        
        char[] charArray=s.toCharArray();
        
        int[] integerArray=new int[charArray.length];
        
        
        // creating braces with equivalent numeric values
        for(int i=0;i<charArray.length;i++) {
            
            if(charArray[i]=='{') {
                integerArray[i]=1;
            }
            else if(charArray[i]=='}') {
                integerArray[i]=-1;
            }
            else if(charArray[i]=='[') {
                integerArray[i]=2;
            }
            else if(charArray[i]==']') {
                integerArray[i]=-2;
            }
            else if(charArray[i]=='(') {
                integerArray[i]=3;
            }
            else  {
                integerArray[i]=-3;
            }
        }
        
        Stack<Integer> stack=new Stack<Integer>();
        
        for(int i=0;i<charArray.length;i++) {
            
            if(stack.isEmpty()) {
                if(integerArray[i]<0) {
                    stack.push(integerArray[i]);
                    break;
            }
                    stack.push(integerArray[i]);
            }
            else{
                if(integerArray[i]>0) {
                    stack.push(integerArray[i]);
                }
                else {
                    if(stack.peek()==-(integerArray[i])) {
                        stack.pop();
                    }
                    else {
                        break;
                    }
                }
            }
        }
        return stack.isEmpty();
    }
}

Quintan

Hello Nava Chaitanya, welcome to stackoverflow. People will appreciate if you post some explanations along with your code. – Oligosaccharide

Answer 33

static void checkBalanceParan(String s){
Stack<Character>stk=new Stack<>();

int i=0;
int size=s.length();
while(i<size){
    if(s.charAt(i)=='{'||s.charAt(i)=='('||s.charAt(i)=='['){
        stk.push(s.charAt(i));
        i++;
    }
    else if(s.charAt(i)=='}'&&!stk.empty()&&stk.peek()=='{'){
            int x=stk.pop();
            i++;
    }else if(s.charAt(i)==')'&&!stk.empty()&&stk.peek()=='(')
        {
        int x=stk.pop();
        i++;
        }
    else if(s.charAt(i)==']'&&!stk.empty()&&stk.peek()=='['){
        int x=stk.pop();
        i++;
}
    else{
    System.out.println("not Balanced");
        return;
        }
    }
System.out.println("Balanced");}

Gustie

Answer 34

I call this brute force type approach we are replacing every () or {} or [] from the string with "" so therefore length of String is decreasing and if length of String doesn't change then i am simply breaking the loop otherwise if length of String gets down to 0 then it means everything in String is balanced otherwise not.

public class Question{
public static void main(String[] args) {
    String target="{ [ ( ) ] }",target2="( ) [ ] { }",target3="[ ( ) ] ( ( ) )",target4="( { [ )";
    target=target.replaceAll(" ","");
    target2=target2.replaceAll(" ", "");
    target3=target3.replaceAll(" ", "");
    target4=target4.replaceAll(" ", "");
    System.out.println(CheckExp(target));
    System.out.println(CheckExp(target2));
    System.out.println(CheckExp(target3));
    System.out.println(CheckExp(target4));
}
public static Boolean CheckExp(String target) {
    boolean flag = false;
    if (target.length() < 2 || target.length()%2!=0 ) {
        return flag;
    }
    int first,last;
    while(true) {
        first=target.length();
            target = target.replace("()", "");
            target = target.replace("{}","");
            target = target.replace("[]","");
            last=target.length();
            if(first==last)
                break;
            flag= target.length() == 0;
    }
    return flag;
}

}

Moot

Answer 35

we are using the deque for easy and quickly way to find balanced string or not. In this we are checking string contains equals number of closing and opening these'()','{}' and '[]'. In this we are also checking the closing beckets should be after the opening brackets.

import java.util.Deque;
import java.util.LinkedList;
public class TestPattern{

    public static String pattern(String str){
        Deque<Character> deque = new LinkedList<>(); 
    for (char ch: str.toCharArray()) {
    if (ch == '{' || ch == '[' || ch == '(') {
        deque.addFirst(ch);
    } else {
        if (!deque.isEmpty() && ((deque.peekFirst() == '{' && ch == '}')
            || (deque.peekFirst() == '[' && ch == ']')
            || (deque.peekFirst() == '(' && ch == ')'))) {
            deque.removeFirst();
        } else {
            return "Not Balanced";
        }}}return "Balanced";}

// the above method is retur balanced or not balanced string.


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

Edwardedwardian

Answer 36

Balanced Parentheses Got this question on one of my technical interview. Should to solve by using array only. JAVA

public class Test1 {
        public static void main(String[] args) {
            
            String arr = "()()()(((12())1()))()()()"; //true
            //String arr = "()()()(((12())1()))()()("; //false
            System.out.println(isValid(arr)); 
        }
        
        static boolean isValid(String s){
            
            boolean valid;
            char[] array = s.toCharArray();
            char[] tempArray = new char[array.length];
            int parentesisCounter = 0;
            int tempCount = 0;
            
            for( int i = 0, m = 0; i < array.length; i++){
                if( array[i] == '(' || array[i] == ')' ){
                    tempArray[m] = array[i];
                    m++;     
                }
            }
            
            for(int i = 0; i < tempArray.length; i++){
                if( tempArray[i] == '(' || tempArray[i] == ')'){
                    tempCount++;
                }
            }
            
            char[] finalArray = new char[tempCount];
       
            System.arraycopy(tempArray, 0, finalArray, 0, tempCount);
            
            
            int countR = finalArray.length;
            int countL = 0;
            
            if((countR)%2 != 0){               
                return valid = false;
            }else if(finalArray[0] == ')' || finalArray[countR-1] == '(' ){
                return valid = false;
            }
            
            for( int i = 0; i < finalArray.length; i++ ){
                
                if( finalArray[countL] == '(' && finalArray[countL+1] == ')' ){
                   countL+=2;
                   i++;
                   if(countL == countR){
                       return valid = true;
                   }
                }else if( finalArray[countR-1] == ')' && finalArray[countR-2] == '(' ){
                   countR-=2;
                   if(countL == countR){
                       return valid = true;
                   }
                }else if( finalArray[countR-1] == ')' && finalArray[countR-2] == ')' ){
                   countR--;
                   parentesisCounter--;
                   if(countL == countR){
                       return valid = true;
                   } 
                }else if( finalArray[countL] == '(' && finalArray[countL+1] == '(' ){
                   countL++;
                   parentesisCounter++;
                   if(countL == countR){
                       return valid = true;
                   }
                }else if( finalArray[countL] == ')' ){
                   if(countL == countR+1){
                       return valid = true;
                   }
                   parentesisCounter--;
                }
            } 
            if(parentesisCounter == 0){
                valid = true;
            }else valid = false;
            return valid;         
        }   
    }

Exhibit

This question is old, and today would be considered off-topic. There are already several solutions to this problem in Java. How is yours different? Please read How to Answer. – Wellintentioned

Why this will be considered off-topic @Wellintentioned ? It's well programming related – Centiliter

@Elikill58, it doesn't say what's wrong with that code. An on-topic question would explain what the code should do, show the attempt, and clearly explain the problem with the code so answers could correct a specific error. This question does not do that and has therefore attracted a whole bunch of "here's my solution" code dumps that have no value. SO isn't about showing off your code or providing code to be blindly copied. It's about helping users learn. Being "programming related" is not sufficient to be on-topic. See the help center for details. – Wellintentioned

@Wellintentioned oh yes, you mean it should be closed as need more focus/details & clarity. I through you was talking about off-topic question which should be on another site of SE network – Centiliter

Hi everybody. Thank's for the comments and reviews. Although the question is old but still relevant on the technical interviews. I got it in 2021 and felt a commitment to share it. The internet is full of using Stack solutions but thin choice of different data structures. – Exhibit

Answer 37

**// balanced parentheses problem (By fabboys)**
#include <iostream>
#include <string.h>

using namespace std;

class Stack{

char *arr;
int size;
int top;

public:

Stack(int s)
{
  size = s;
  arr = new char[size];
  top = -1;
}

bool isEmpty()
{
  if(top == -1)
    return true;
 else
    return false;
 }

 bool isFull()
 {
  if(top == size-1)
    return true;
 else
    return false;
 }


 void push(char n)
 {
 if(isFull() == false)
 {
     top++;
     arr[top] = n;
 }
}

char pop()
{
 if(isEmpty() == false)
 {
     char x = arr[top];
     top--;
     return x;
 }
 else
    return -1;
}

char Top()
{
 if(isEmpty() == false)
 {
    return arr[top];
 }
 else
    return -1;
}
Stack{
 delete []arr;
 }

};

int main()
{
int size=0;


string LineCode;
cout<<"Enter a String : ";
  cin >> LineCode;



    size = LineCode.length();

    Stack s1(size);


    char compare;

    for(int i=0;i<=size;i++)
    {

 if(LineCode[i]=='(' || LineCode[i] == '{' || LineCode[i] =='[')

 s1.push(LineCode[i]);

 else if(LineCode[i]==']')
 {
     if(s1.isEmpty()==false){
                    compare =  s1.pop();
                if(compare == 91){}
                    else
                        {
                        cout<<" Error Founded";
                            return 0;}
        }
            else
            {
               cout<<" Error Founded";
               return 0;
            }

 } else if(LineCode[i] == ')')
 {
     if(s1.isEmpty() == false)
     {
         compare = s1.pop();
         if(compare == 40){}
         else{
            cout<<" Error Founded";
                            return 0;
         }
     }else
     {
        cout<<"Error Founded";
               return 0;
     }
 }else if(LineCode[i] == '}')
 {
       if(s1.isEmpty() == false)
     {
         compare = s1.pop();
         if(compare == 123){}
         else{
            cout<<" Error Founded";
                            return 0;
         }
     }else
     {
        cout<<" Error Founded";
               return 0;
     }


 }
}

if(s1.isEmpty()==true)
{
    cout<<"No Error in Program:\n";
}
else
{
     cout<<" Error Founded";
}

 return 0;
}

Metternich

The question was about java, why did you post an answer with c++? – Jamnes