Java program to check the balance of parenthesis
Balanced Parenthesis
To check balanced parenthesis is a basic interview question where we are asked to find whether the given string(of brackets) is balanced or not. To do this , the traditional way of doing is using stacks but we can also find by using normal programming techniques. Different brackets are ( ) , [ ] , { }. Question can be asked on any type of bracket or of all types of brackets.
Algorithm :
- Declare a character stack.
- Now traverse the expression string exp.
- If the current character is a starting bracket (‘(‘ or ‘{‘ or ‘[‘) then push it to stack.
- If the current character is a closing bracket (‘)’ or ‘}’ or ‘]’) then pop from stack and if the popped character is the matching starting bracket then fine else brackets are not balanced.
- After complete traversal, if there is some starting bracket left in stack then “not balanced”
Example Code in Java :
import java.util.*;
public
class Main {
public
static boolean balancedParenthesis(String str) {
Stack stack = new Stack();
for (int i = 0; i < str.length(); i++) {
char x = str.charAt(i);
if (x == '(' || x == '[' || x == '{') {
stack.push(x);
continue;
}
if (stack.isEmpty()) return false;
char check;
switch (x) {
case ')':
check = stack.pop();
if (check == '{' || check == '[') return false;
break;
case '}':
check = stack.pop();
if (check == '(' || check == '[') return false;
break;
case ']':
check = stack.pop();
if (check == '(' || check == '{') return false;
break;
}
}
return (stack.isEmpty());
}
public
static void main(String[] args) {
String str = "()(())";
if (balancedParenthesis(str))
System.out.println("True");
else
System.out.println("False");
}
}Output :
True
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
Get over 200+ course One Subscription
Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others
Login/Signup to comment
The following solution is o(n) and easy to remember
import java.util.Stack;
class Solution {
public boolean isValid(String s) {
Stack stack = new Stack();
for (char ch : s.toCharArray()) {
switch (ch) {
case ‘(‘: case ‘{‘: case ‘[‘:
stack.push(ch);
break;
case ‘)’:
if (stack.isEmpty() || stack.pop() != ‘(‘) return false;
break;
case ‘}’:
if (stack.isEmpty() || stack.pop() != ‘{‘) return false;
break;
case ‘]’:
if (stack.isEmpty() || stack.pop() != ‘[‘) return false;
break;
default:
return false;
}
}
return stack.isEmpty();
}
}
import java.util.*;
public class Main
{
public static void main(String[] args) {
Scanner scn=new Scanner(System.in);
String str=”()(())”;
System.out.println(balance_bracket(str));
}
public static boolean balance_bracket(String str){
Stack st=new Stack();
st.push(str.charAt(0));
for(int i=1;i<str.length();i++){
char ch=str.charAt(i);
if(ch=='[' || ch=='{' || ch=='('){
st.push(ch);
}
if(ch==')'){
if(st.peek()=='(')
st.pop();
else
return false;
}
else if(ch=='}'){
if(st.peek()=='{')
st.pop();
else
return false;
}
else if(ch==']'){
if(st.peek()=='[')
st.pop();
else
return false;
}
}
if(st.size()!=0)
return false;
return true;
}
}