Hello! So I’m doing a 30 day coding challenge where I solve around 3-5 questions per day and thought of posting them here on my blog so that you guys can join the challenge too!
Welcome to Coding challenge Day 1: Problem one! Be sure to post your answers, queries etc in the comments!!
Problem 1: To check if an expression is balanced or not
Sample input: {}[]()
Output: Expression is balanced
Sample input: {()} {)
Output: Expression is not balanced
Sample input: {()()}[()]
Output: Expression is balanced
Solution:
- So I’ve made use of Stack Data Structure to solve this problem.
- So we can start with putting the expression in a character array
- run a loop along the entire length of the array and push the open brackets ‘(‘, ‘{‘, ‘[‘ into a stack
- if we come across any close brackets ‘)’,’}’,’]’ then pop from the stack
- compare pop element with the closed bracket and see if they match (i.e. pop_element='(‘ and closed_bracket=’)’ or pop_element='{‘ and closed_bracket=’}’ or pop_element='[‘ and closed_bracket=’]’ )
- If all pop elements match the coressponding closed bracket then your expression is balanced.
//to check if expression is balanced or not
public class Program003balanced_expression_check {
static class Stack{
//array implementation of stack
final int Max=10;
char data[]= new char[Max];
int top=-1;
public void push (char element){
if(top<Max-1){
data[++top]= element;
}
else
System.out.println("Stack is full");
}
public Character pop (){
if(top==-1){
System.out.println("Stack is empty");
return null;
}
return data[top--];
}
}
public static int check_balance (char exp[]){
Stack S= new Stack();
int count=0;
int length= exp.length;
for(int i=0; i<length; i++){
char a= exp[i];
if(a=='(' || a=='{' || a=='['){
S.push(a);
}
if(a==')' || a=='}' || a==']'){
int t=S.pop();
if(t=='(' && a==')'){
count+=2;
}
if(t=='{' && a=='}'){
count+=2;
}
if(t=='[' && a==']'){
count+=2;
}
}
}
return count;
public static void main(String[] args){
char exp[]={'{','}','(',')','[',']'};
int count= check_balance(exp);
if (count==exp.length)
System.out.println("Expression is balanced");
else
System.out.println("Expression is not balanced");
}
}
HAPPY LEARNING!!
//to check if expression is balanced or not
public class Program003balanced_expression_check {
static class Stack{
//array implementation of stack
final int Max=10;
char data[]= new char[Max];
int top=-1;
public void push (char element){
if(top<Max-1){
data[++top]= element;
}
else
System.out.println("Stack is full");
}
public Character pop (){
if(top==-1){
System.out.println("Stack is empty");
return null;
}
return data[top--];
}
}
public static int check_balance (char exp[]){
Stack S= new Stack();
int count=0;
int length= exp.length;
for(int i=0; i<length; i++){
char a= exp[i];
if(a=='(' || a=='{' || a=='['){
S.push(a);
}
if(a==')' || a=='}' || a==']'){
int t=S.pop();
if(t=='(' && a==')'){
count+=2;
}
if(t=='{' && a=='}'){
count+=2;
}
if(t=='[' && a==']'){
count+=2;
}
}
}
return count;
}
public static void main(String[] args){
char exp[]={'{','}','(',')','[',']'};
int count= check_balance(exp);
if (count==exp.length)
System.out.println("Expression is balanced");
else
System.out.println("Expression is not balanced");
}
}
HAPPY LEARNING!!