Question

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 following strings have balanced parentheses: () (()()) ((())())

The following strings do not have balanced parentheses: )( (() ())(()))())

We consider the empty string to have balanced parentheses, as there is no imbalance. Your program should accept as input a single string containing only the characters ) and (, and output a single line stating true or false .

The functionality for reading and printing answers is written in the class; your task is to complete the hasBalancedParentheses() method.

Answer 1

Source Code in Java:

class Parenthesis
{
boolean hasBalancedParentheses(String eq) //method to check and return if a set of parenthesis is balanced or not
{
int count=0; //to store count of current unclosed opening brackets
for(int i=0;i<eq.length();i++)
{
if(eq.charAt(i)=='(')
count++;
else if(eq.charAt(i)==')')
count--;
if(count<0) //if count falls below zero, there were more closing brackets than opening brackets till this point
return false;
}
if(count>0) //if count is still more than zero, there were less closing brackets than opening brackets
return false;
return true; //if program reaches this point, it has passed all the tests
}
public static void main(String args[])
{
//testing the function
Parenthesis ob=new Parenthesis();
System.out.println(ob.hasBalancedParentheses("()(()())((())())"));
System.out.println(ob.hasBalancedParentheses(")((()())(()))())"));
}
}

Output: