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;
    }
  }


}

Answer 1

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();
}

Answer 2

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;
    }
}

Answer 3

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

Answer 4

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";

}

Answer 5

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;
        }

Answer 6

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;
    }
}