Question

Programming language is Java:

Write a pseudocode method to determine if a set of parentheses and brackets is balanced. For example, such a method should return true for the string, "[()]{}{[()()]()}" and false for the string "[(])".

Also please discuss how the algorithm will perform and how much space in memory it will take if somebody passes a massive string as input.

Answer 1

static boolean check(String str){
       Stack<Character> ch=new Stack<Character>();
       int flag=0;
       // To check if a particular character is an opening bracket
       Set<Character> opening=new HashSet<>();
       opening.add('{');
       opening.add('(');
       opening.add('[');
       // To check if a particular character is a closing bracket and what is it's corresponding opening bracket
       HashMap<Character,Character> pair=new HashMap<>();
       pair.put('}','{');
       pair.put(')','(');
       pair.put(']','[');
       for(int i=0;i<str.length();i++){
           if(opening.contains(str.charAt(i))){
               ch.push(str.charAt(i));
           }
           else if(pair.containsKey(str.charAt(i))){
               if(!ch.isEmpty() && pair.get(str.charAt(i))==ch.peek()){
                   ch.pop();
               }
               else{
                   flag=1;
                   break;
               }      
           }
           else{
               // If any other characher is present, string is unbalanced
               flag=1;
               break;
           }          
       }
       if(ch.isEmpty() && flag==0)
           return true;
       else
           return false;
   }

The function takes O(n) time and O(n) space for an input string of length n.

O(n) time: Iterates over each Character of the string once

O(n) space: stores the characters in a stack. It will store all the characters of the string in worst case (all opening brackets or opening parentheses).