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

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 ****");
}       

}

Answer 2

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

Answer 3

    import java.io.IOException;
    import java.util.ArrayList;
    import java.util.List;
    import java.util.Scanner;
    import java.util.Stack;
    public class BalancedParenthesisWithStack {

    /*This is purely Java Stack based solutions without using additonal 
      data structure like array/Map */

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

        Scanner sc = new Scanner(System.in);

        /*Take list of String inputs (parenthesis expressions both valid and 
         invalid from console*/

        List<String> inputs=new ArrayList<>();
        while (sc.hasNext()) {

            String input=sc.next();
            inputs.add(input);

        }

        //For every input in above list display whether it is valid or 
         //invalid parenthesis expression

        for(String input:inputs){



        System.out.println("\nisBalancedParenthesis:"+isBalancedParenthesis
        (input));
        }
    }

    //This method identifies whether expression is valid parenthesis or not

    public static boolean isBalancedParenthesis(String expression){

        //sequence of opening parenthesis according to its precedence
         //i.e. '[' has higher precedence than '{' or '('
        String openingParenthesis="[{(";

        //sequence of closing parenthesis according to its precedence
        String closingParenthesis=")}]";

        //Stack will be pushed on opening parenthesis and popped on closing.
        Stack<Character> parenthesisStack=new Stack<>();


          /*For expression to be valid :
          CHECK :
          1. it must start with opening parenthesis [()...
          2. precedence of parenthesis  should be proper (eg. "{[" invalid  
                                                              "[{(" valid  ) 


          3. matching pair if(  '(' => ')')  i.e. [{()}(())] ->valid [{)]not 
          */
         if(closingParenthesis.contains
         (((Character)expression.charAt(0)).toString())){
            return false;
        }else{
        for(int i=0;i<expression.length();i++){

        char ch= (Character)expression.charAt(i);

        //if parenthesis is opening(ie any of '[','{','(') push on stack
        if(openingParenthesis.contains(ch.toString())){
                parenthesisStack.push(ch);
            }else if(closingParenthesis.contains(ch.toString())){
        //if parenthesis is closing (ie any of ']','}',')') pop stack
        //depending upon check-3 
                if(parenthesisStack.peek()=='(' && (ch==')') || 
                    parenthesisStack.peek()=='{' && (ch=='}') ||    
                    parenthesisStack.peek()=='[' && (ch==']')
                        ){
                parenthesisStack.pop();
                }
            }
        }

        return (parenthesisStack.isEmpty())? true : false;
        }
    }

Answer 4

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

Answer 5

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 BalancedBracket {
    public static void main(String[] args) {
        String braces = "{{}(";
        if(isBalanced(braces)){
            System.out.println("YES");
        }else{
            System.out.println("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();
    }
}