Code in java language please. Write a program that uses Stacks to determine if a
ID: 3733626 • Letter: C
Question
Code in java language please.
Write a program that uses Stacks to determine if a line written with parentheses is well-formed or not. This is a subtask that is similar to the techniques that compilers use to determine if you are missing (or have too many) curly braces or parentheses or brackets. The program should read the user input, and should push an open (when it is encountered, and perform a pop when a closed) is encountered. This way, if at the end of the program run, the stack is empty, then the line is well-formed. If the end of the input is reached and the stack is not empty, that means there were too many open parentheses, If at any time, the program sees a closed parenthesis, ), and the stack is empty already, then an exception will be thrown and this is an indicator that there are too many, or at least a misplaced, closed parenthesis. Either situation should cause the program to indicate it is not well formed. An example run might look like the following: Please input a set of parentheses 0(O)XO) Input is well-formed Another example run might look like the following: Please input a set of parentheses > Sorry, input is NOT well-formedExplanation / Answer
Implementing this program using stack , we can use push-pop methods for pushing the opening parenthesis when we encounter it , and popping the last opening parenthesis when we encounter a closing parenthesis.
1. Create a stack of upto MAX elements (Here, we have taken MAX as 1000 , that means we are assuming to keep the number of opening parenthesis in a series ,to be below or equal to 1000).
2.Create a push method- This push method will inject a opening parenthesis '(' into the stack , and increment the top as required.
3. Create a pop method- This pop method will remove an opening parenthesis from the stack.
The pop() will throw an exception ,in the case if the stack cannot be popped at this point meaning the parenthesis are not well formed .
4. At the end, the stack should be empty meaning all the opening parenthesis should be popped from the stack by equal closing parenthesis. If the stack is not empty, the parenthesis are not well formed.
import java.util.*;
class myClass {
public static void main(String args[]) {
char[] stack=new char[1000];
int top=-1; // when the stack is empty
Scanner Scn=new Scanner(System.in);
String parenthesis=Scn.nextLine(); // taking the input
boolean isWellformed=true; // by default, the parenthesis are assumed well formed unless we encounter some anomaly while processing them
for(int i=0;i<parenthesis.length();i++)
{
if(parenthesis.charAt(i)=='(') // if the opening parenthesis is encountered , push it into the stack
top=push(stack,'(',top);
try {
if(parenthesis.charAt(i)==')') // if the closing parenthesis is encountered , pop the last opening parenthesis from the stack
top=pop(stack,top);
}
catch(IllegalStateException e) // In the case, the pop returns IllegalStateException , that means the stack cannot be popped, and the parenthesis are not well formed.
{
isWellformed=false;
top=-2;
break;
}
}
if(top==-1) // if the stack is empty, the parenthesis are balanced
{
isWellformed=true;
}
else // if the stack is not empty or the top is illegal with -2 value, the parenthesis are not balanced
isWellformed=false;
if(!isWellformed)
System.out.println("Input is NOT well formed");
else
System.out.println("Input is well formed");
}
static int push(char[] stack,char ch,int top)
{
top++; // increment the top , and then push the char into the stack
stack[top]=ch;
return top;
}
static int pop(char[] stack,int top) throws IllegalStateException
{
if(top>=0) // if the stack is not empty, only then pop the last element
{
top--;
return top;
}
throw new IllegalStateException(); // if the stack is empty, it cannot be popped anymore, return an exception in this case
}
}