Coding Challenge Day-1: Problem 1: Check Balanced Expression

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");
		
	}

}

Download Code

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");
		
	}

}

Download Code

HAPPY LEARNING!!

Leave a Reply

PHP JS HTML CSS BASH PYTHON CODE

Your email address will not be published.

This site uses Akismet to reduce spam. Learn how your comment data is processed.

%d bloggers like this: