Here’s an function implemented in Java to check whether a string contains balanced parentheses.
Examples
isBalanced("((()))")returnstrueisBalanced("(()()())")returnstrueisBalanced("(()()()")returnsfalseisBalanced("()())")returnsfalse
Implementation
/**
* Checks if the specified string has balanced parentheses.
*
* @param str
*
* @return True, if the parentheses are balanced, false otherwise.
*/
public static boolean isBalanced(String str) {
// Define the sum of the brackets.
int sum = 0;
// Loop through each character in the string.
for(int i=0; i < str.length(); i++) {
// If the character is an open bracket, add 1.
// If the character is a closed bracket, remove 1.
if(str.charAt(i) == '('){
sum += 1;
} else if(str.charAt(i) == ')'){
sum -= 1;<br />
}
}
// The total sum must be 0, if the brackets are balanced.
// Otherwise, they are not balanced.
return sum == 0;
}
Will it work for “((a))))((“? I doubt.
Thanks for pointing that out Miral. It wouldn’t work in that case. Pushing and popping on a stack is probably the only/best way of going about it then.
You actually may not only need a stack. You could use your sum implementation but if the value of the sum is ever less than 0, you know it is not balanced:
“((a))))((”
Would break at:
[0], ( : [1], ( : [2], a : [2], ) : [1], ) : [0], ) : [-1]
So modify your else to look like:
else if(str.charAt(i) == ‘)’){
if(sum == 0)
return false;
sum -= 1;
}