Given a list of strings of bracket characters: {}(), the string of brackets is balanced under the following conditions:
- It is the empty string.
- If strings a and b are balanced, then ab is balanced.
- If string a is balanced, then (a) and {a} are balanced.
Write a class that determines whether the brackets in each string are balanced and returns true if the string is balanced, or false if it is not.
Example 0
s = [ “{}()”, “{()}”, “({()})” ]
s[0] exhibits condition 2 above. “{}” and “()” are balanced, so “{}()” is balanced. Return true.
s[1] exhibits condition 3 above. “()” is balanced, so “{()}” is balanced. Return true.
s[2] exhibits condition 3 above. “()” is balanced, so “{()}” is balanced and “({()})” is balanced. Return true.
Example 1
s = [“{}(“, “({)}”, “((“, “}{” ]
s[0] → ‘“{}(“ is an unbalanced string due to the open “(“. Return false.
s[1] → “({)}” is an unbalanced string due to “)” before “{” has been closed. Return false.
s[2] → “((“, is an unbalanced string because neither “(” is closed. Return false.
s[2] → “}{“ is an unbalanced string because “}” comes before a “{” and because the final “{” is not closed. Return false.
Function Description
The provided code contains the declaration for a class named Solution with a main method that does the following:
- Creates a Parser object.
- Reads an unknown number of strings from stdin.
- Passes each string as an argument to the Parser object’s isBalanced method and prints value returned by the method on a new line.
Complete the function an isBalanced in the editor below.
isBalanced has the following parameter(s):
string s: a string of characters to check for balance
Returns :
string : a string that denotes whether the string is balanced: true if the string is balanced, or false if it is not
Constraints
- Each string consists only of the characters {, }, (, and ).
- Each string has fewer than 50 characters.
SOLUTION:
import java.util.*;
class Solution
{
public static void main(String args[])
{
Parser parser=new Parser();
Scanner in=new Scanner(System.in);
while(in.hasNext())
{
System.out.println(parser.isBalanced(in.next()));
}
in.close();
}
}
class Parser
{
public boolean isBalanced(String str)
{
Stack<Character> stack=new Stack<Character>();
for(int i=0;i<str.length();i++)
{
char ch=str.charAt(i);
if(ch=='(' || ch=='{' || ch=='[')
{
stack.add(ch);
}
else if(ch==')' || ch=='}' || ch==']')
{
if(stack.isEmpty() || ch==')' && stack.peek()!='(' || ch=='}' && stack.peek()!='{' || ch==']' && stack.peek()!='[' )
{
return false;
}
stack.pop();
}
}
return stack.isEmpty();
}
}