Consider the following Stack operations:
1 answer:
You might be interested in
Answer:
The screenshot is attached below
Explanation:
The below program check balence of paranthesis using stack.
if the input charecter is ( then push to stack
if the input charecter is ) then pop top element and compair both elements for match.
Program:
public class Main
{
static class stack // create class for stack
{
int top=-1; // initialy stack is empty so top = -1
char items[] = new char[50]; // Create an array for stack to store stack elements
void push(char a) // Function push element to stack
{
if (top == 49) // chack stack is full ?
{
System.out.println("Stack full");
}
else
{
items[++top] = a; // increment the array index and store the element
}
}
char pop() // function to return the elements from stack
{
if (top == -1) // check the stack is empty
{
System.out.println("Empty stack");
return '\0';
}
else
{
char element = items[top]; // return the top element
top--; // Decrement the array index by one
return element;
}
}
boolean isEmpty() // Check the stack is empty or not
{
return (top == -1) ? true : false;
}
}
static boolean isMatch(char character1, char character2) // Check the input charecters are matching pairs or not
{
if (character1 == '(' && character2 == ')') // If they match return true
return true;
else
return false;
}
static boolean isBalanced(String parantheses) // check the input string is balenced or not
{
char[] exp = new char[parantheses.length()]; // Create a charecter array
for (int i = 0; i < parantheses.length(); i++) { // Convert the string parantheses to charecter array
exp[i] = parantheses.charAt(i);
}
stack st=new stack(); // Declare an empty character stack
for(int i=0;i<exp.length;i++)
{
if (exp[i] == '(')) // if input charecter is '(' push to stack
st.push(exp[i]);
if (exp[i] == ')') // if input charecter is ')' pop top element from stack
{
if (st.isEmpty())
{
return false;
}
else if ( !isMatch(st.pop(), exp[i]) ) // Call isMatch function
{
return false;
}
}
}
if (st.isEmpty())
return true; //balanced
else
{
return false; //not balanced
}
}
public static void main(String[] args)
{
System.out.println(isBalanced("()()()")); // Output true if string is balenced
}
}
Screenshot:
