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