Question

Java Programming

Using the class below, please

1. ), 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

WORKING OF THE CODE IS EXPLAINED IN SUMMARY

CODE:

import java.util.*;
public class BalancedString
{
public static int parse(String s)
{
Deque<Character> stack = new ArrayDeque<Character>();
for(int i=0;i<s.length();i++)
{
char c=s.charAt(i);
if(c=='{' || c=='(' || c=='[') //Push all the opening parantheses in the stack
{
stack.push(c);
}
else if((c==')' || c=='}' || c==']') && stack.isEmpty()) //Check if an extra closing parantheses encountered
{
return i+1;
}
else if(c==')') //Check if the ending parantheses was started by its balanced opening parantheses
{
char x=stack.pop();
if(x!='(')
return i+1;
}
else if(c=='}') //Check if the ending parantheses was started by its balanced opening parantheses
{
char x=stack.pop();
if(x!='{')
return i+1;
}
else if(c==']') //Check if the ending parantheses was started by its balanced opening parantheses
{
char x=stack.pop();
if(x!='[')
return i+1;
}
}
if(stack.isEmpty()) //If stack is empty than the string was correct
return -1;
else //If the stack contains any brackets than the string is incorrect
return s.length(); //The closing bracket was required at last position
}
   public static void main(String[] args) {
       int balance;
       balance=parse("{3+{4/2}}");
       if(balance==-1)
       System.out.println("No Errors found in the string");
       else
       System.out.println("Error occurred at position: "+balance);
       balance=parse("{{4*X}");
       if(balance==-1)
       System.out.println("No Errors found in the string");
       else
       System.out.println("Error occurred at position: "+balance);
       balance=parse("{3+4}}");
       if(balance==-1)
       System.out.println("No Errors found in the string");
       else
       System.out.println("Error occurred at position: "+balance);
   }
}

OUTPUT:

No Errors found in the string                                                                                                 

Error occurred at position: 6                                                                                                 

Error occurred at position: 6

Note: If you have any queries than let me know in the comments. If you find it helpful than a Like would be appreciated.

SUMMARY:

The above code is implemented as instructed. The working of code is explained in comments of the code. We push all the strating brackets like (,{,[ in the stack and search for their closing brackets in the string. If the closing bracket is found than the element from the stack is popped. If the stack is empty and the closing bracket appears than the error occurs at that index. If the string has been traversed and yet the stack is not empty that means closing bracket is not encountered for any of the starting bracket which returns that index. If the closing bracket is not matched with the top element in stack to be popped, it means there is missing closing bracket for it and therefore return that index. For example if '(' is encountered and pushed, than ')' should be encountered. But if any other closing bracket like '}' or ']' is found than it is error and hence return that index.