Question

in Java language, in most simple algorithm

1. Using a stack class, write a static method called parse that parses a String for balanced parentheses. we seek only to determine that the symbol ‘{‘ is balanced with ‘}’. parse accepts a single String parameter and returns an int. If parse returns a minus 1, then there are no errors, otherwise, parse should return the position within the String where an error occurred. For example

parse(“{3 + {4/2} }”)   would return -1

parse(“{ { 4*X}”) would return 6 since at position 6 we expected another “}”

parse(“{3+4}}”) would also return a 6

Answer 1

The program is written as per the requirements. The comments are provided in the code for better understanding of how the logic works.

import java.util.*;

class Test{
   public static void main(String[] args) {
       int result = parse("{3+4}}");
       System.out.println(result);
   }
  
   static int parse(String expression) {
       //Declare a stack
       Stack<String> expressionStack = new Stack<String>();
      
       //Add each characters of the expression variable to the stack.
       for(int i = 0; i < expression.length(); i++) {
           expressionStack.push(Character.toString(expression.charAt(i)));
       }
      
       //These variables are used for counting the left and right braces.
       int leftBracesCount = 0;
       int rightBracesCount = 0;
      
       //Initializing the variable i to the stack size. This is decreased by 1 inside the loop in each iteration to find out the bad position of the braces.
       int i = expressionStack.size();
       int result = -1;
       //Get each character from the stack inside the loop.
       while(!expressionStack.empty()) {
           String characterExtracted = expressionStack.pop();
           switch(characterExtracted) {
               case "{":
                   leftBracesCount++;
                   if(result == -1)
                       result = i;
                   break;
               case "}":
                   rightBracesCount++;
                   if(result == -1)
                       result = i;
                   break;
           }

           i--;
       }
      
       if(leftBracesCount == rightBracesCount)
           result = -1;

       return result;
   }
}