Parenthesis Matching using stack

Problem is given a string of parenthesis ‘(‘ and ‘)’ ,'{' and '}' , '[' and ']'  find out if there are matching pairs or not, typically this known as parenthesis matching problem.

For example : ‘((()))’ input will return TRUE, but ‘)(())’ will return FALSE.

Algorithm for parenthesis matching

• Whenever we see a opening parenthesis, we push it on stack.
• When we see closing parenthesis, we check what is at the top of the stack, if we have corresponding parenthesis, we are good. Remove it from the top of the stack. And move on.
• If parenthesis at the top of the stack is not corresponding opening parenthesis, we return false, as there is no point check the string further.
• Again, when we reach at end of the string, we need to check if stack is empty or not. If the stack is empty, we are good. If stack is not empty, parenthesis do not match.

Implementation 

	/*
	* To change this license header, choose License Headers in Project Properties.
	* To change this template file, choose Tools | Templates
	* and open the template in the editor.
	*/
	package algorithm;
	/**
	*
	* @author sutha
	*/
	import java.util.*;
	public class braceChecker
	{
	/**
	*
	* @param args
	*/
	public static void main(String [] args)
	{
	Scanner sc=new Scanner(System.in);
	String s;
	boolean a=true;
	System.out.println("Please enter the braces");
	s=sc.next();
	int length=s.length();
	stack br=new stack (length);
	for(int i=0;i<length;i++)
	{
	char c=s.charAt(i);
	if(c=='(' || c=='{' || c=='[')
	{
	br.push(c);
	}
	else if( c==')' || c==']' || c=='}')
	{
	if(!br.isEmpty())
	{
	char pope;
	switch(c)
	{
	case ')':
	pope=br.pop();
	if(pope!='(')
	{
	a=false;
	}
	case ']':
	pope=br.pop();
	if(pope!=']')
	{
	a=false;
	}
	case '}':
	pope=br.pop();
	if(pope!='{')
	{
	a=false;
	}
	}
	}
	else
	{
	a=false;
	}
	}
	}
	if(a==true && br.isEmpty() )
	System.out.println("parenthesis matching ");
	else
	{
	System.out.println("parenthesis not matching ");
	}
	}
	}

view raw braceChecker.java hosted with ❤ by GitHub

	/*
	* To change this license header, choose License Headers in Project Properties.
	* To change this template file, choose Tools | Templates
	* and open the template in the editor.
	*/
	package algorithm;
	/**
	*
	* @author sutha
	*/
	public class stack
	{
	int size;
	char[] array;
	int top;
	public stack(int s)
	{
	size=s;
	top=0;
	array=new char[s];
	}
	public void push(char elt)
	{
	top=top+1;
	array[top]=elt;
	}
	public char pop()
	{
	char mypopped=array[top];
	top=top-1;
	return mypopped;
	}
	public boolean isEmpty()
	{
	return (top==0);
	}
	public boolean isFull()
	{
	return (top==size-1);
	}
	}

view raw stack.java hosted with ❤ by GitHub

Browse More Articles

Tweet

Written by sutha

We are Creative Blogger Theme Wavers which provides user friendly, effective and easy to use themes. Each support has free and providing HD support screen casting.