30 points) Suppose you are given a string containing only the characters ( and ). In this problem, you will write a function to
determine whether the string has balanced parentheses. Your algorithm should use no more than O(1) space beyond the input; any algorithms that use space not in O(1) will receive half credit at most. Any solutions that always return true (or always return false) or otherwise try to game the distribution of test cases will receive zero credit. Balanced parentheses means that every open parenthesis has exactly one close parenthesis corresponding to it and vice versa, and that for each pair the opening parenthesis precedes the closed parenthesis. The follow- ing strings have balanced parentheses: () (()()) ((())()) 1 The following strings do not have balanced parentheses: )( (() ())(()))()) We consider the empty string to have balanced parentheses, as there is no imbalance. The input to hasBalancedParantheses will always be a string only containing "(" or ")". Your task is to complete the has Balanced Parentheses() method. Note: this can be done both iteratively or recursively, but I be- lieve most people will find the iterative version much easier. Hint: There’s a pattern for how to determine if parentheses are balanced. Try to see if you can find that pattern first before coding this method up.
1 answer:
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:
You might be interested in