stack example

Stack Example 2: Delimiter Matching

In previous article Stack introduction and implementation we had learnt how to implement stack in java and in our first example Stack Example 1 we have seen how to use stack to reverse a word or a string.

Stacks are commonly used to parse certain kind of text strings. For example, the below program uses stack to check the matching delimiters typed by the user.

Here are some examples:

c[d]       // correct
a{b[c]d}e  // correct
a{b(c]d}e  // not correct; ] doesn’t match (
a[b{c}d]e} // not correct; nothing matches final }
a{b(c)     // not correct; nothing matches opening {

Stack Example: Delimiter Matching

package com.sneppets.dsalgo;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

class StackDelimiterMatchingChecker
{
	private String inputStr;
	
	public StackDelimiterMatchingChecker(String inStr)
	{
		inputStr = inStr;
	}
	
	public void checkDelimitersMatching()
	{
		int maxStackSize = inputStr.length();
		MyStackImpl myStack = new MyStackImpl(maxStackSize);
				
		for (int i=0; i<inputStr.length(); i++)
		{
			char ch = inputStr.charAt(i);
			
			//start switch
			switch(ch)
			{
				//opening delimiters
				case '{':
				case '[':
				case '(':
					//push delimiters to stack
					myStack.push(ch);
					break;
				
				//closing delimiters
				case '}':
				case ']':
				case ')':
					//if there are delimiter elements in the stack and stack is not empty
					if(!myStack.isEmpty())
					{
						//pop the delimiter elements from stack and check
						char c = myStack.pop();
						if((ch == '}' && c != '{') ||
						   (ch == ']' && c != '[') ||
						   (ch == ')' && c != '('))
							System.out.println("Mismatch found: "+ ch + " at " + i);							
					}
					else 
						//There are no match found because it's prematurely empty
						System.out.println("Mismatch found: "+ ch + " at " + i);	
					break;
					
				default:
					//no need to do anything if any other delimiters or characters present
					break;					
			}//end of switch			
		}//end of for
		
		//at this point all the delimiters in the stack are processed.
		if(!myStack.isEmpty())
		{
			System.out.println("Error: String missing right delimiters");
		}
		
	}

	public String getInputStr() {
		return inputStr;
	}

	public void setInputStr(String inputStr) {
		this.inputStr = inputStr;
	}
	
}

/**
 * 
 * @author sneppets.com
 *
 */
public class StackDelimiterMatchingCheckerExample {
	
	public static void main (String[] args) throws IOException
	{
		String inStr;
		
		while(true)
		{
			System.out.println("Enter a string that contains delimiters, " +
					"for example a{b(c)d}");
			System.out.flush();
			inStr = getInputString();
			
			if(inStr.equals(""))
				break;
			
			StackDelimiterMatchingChecker stackDelimiterMatchingChecker = new StackDelimiterMatchingChecker(inStr);
			stackDelimiterMatchingChecker.checkDelimitersMatching();
		}
	}

	public static String getInputString() throws IOException {
		
		InputStreamReader isr = new InputStreamReader(System.in);
		BufferedReader br = new BufferedReader(isr);
		String inStr = br.readLine();
		
		return inStr;
	}

}

The above program reads characters from the string one at a time and pushes opening delimiters on to stack when if finds them.

Once it reads a closing delimiter from the input, then it pops the opening delimiter from the top of the stack and attempts to match it with the closing delimiter. If it did not find the matching type then it will show error.

Try running the above program with correct and in-correct strings and see what happens.

Output

Enter a string that contains delimiters, for example a{b(c)d}
c[d]
Enter a string that contains delimiters, for example a{b(c)d}
a{b(c]d}e
Mismatch found: ] at 5

Recommended Posts

References

Leave a Reply

avatar
  Subscribe  
Notify of