# Delimiter Matching

We are doing delimiter matching when we check to see if the parentheses in an expression -- like the one shown below -- are balanced.

$$( w \times ( x + y ) \,/\, z - ( p \,/\, ( r - q ) ) )$$

Of course, we are not limited to parentheses. We may have to ensure that several different types of delimiters are balanced (e.g., braces {}, brackets[], parentheses(), angle brackets<>). In doing so, we must ensure that:

• Each opening on the left delimiter must be matched by a closing (right) delimiter.
• Left delimiters that occur later should be closed before those occurring earlier.

## Examples

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


## Delimeter Matching by Using Stacks

The below gives a simple algorithm that uses a stack to determine if the delimeters in an expression match:

1. Read the characters from the string.

2. Whenever you see a left (opening) delimiter, push it to the stack.

3. Whenever you see a right (closing) delimiter, pop the (hopefully matching) opening delimiter from the stack, and

1. If they don't match, report a matching error
2. If you can't pop the stack because it is empty, report a missing left delimiter error
4. If the stack is non-empty after all the characters of the expression have been processed, report a missing right delimeter error.

A Java implementation of this algorithm appears in the code shown below:

import java.util.Scanner;
import java.util.Stack;

public class DelimeterChecker {

public static final int NO_ERROR = 0;
public static final int MATCHING_ERROR = 1;
public static final int MISSING_RIGHT_DELIMETER_ERROR = 2;
public static final int MISSING_LEFT_DELIMETER_ERROR = 3;

public boolean isValid(String inputStr) {

Stack stack = new Stack();

//get chars in turn...
for(int j=0; j<inputStr.length(); j++) {
char ch = inputStr.charAt(j); // get char
switch(ch) {
case '{': // opening symbols
case '[':
case '(':
stack.push(ch); // push them
break;
case '}': // closing symbols
case ']':
case ')':
if ( !stack.isEmpty() ) {
char chx = stack.pop(); // pop and check
if ( (ch=='}' && chx!='{') ||
(ch==']' && chx!='[') ||
(ch==')' && chx!='(')    ) {
printError(inputStr, j, MATCHING_ERROR);
return false;
}
}
else { // prematurely empty
printError(inputStr, j, MISSING_LEFT_DELIMETER_ERROR);
return false;
}
break;
default: // no action on other characters
break;
} // end switch
} // end for

// at this point, all characters have been processed
if ( !stack.isEmpty() ) {
printError(inputStr, inputStr.length(), MISSING_RIGHT_DELIMETER_ERROR);
return false;
}

printError(inputStr, 0, NO_ERROR);
return true;

} // end isValid()

private void printError(String inputStr, int posOfError, int typeOfError) {

if (typeOfError != NO_ERROR) {
System.out.println(inputStr);

for (int i=0; i < posOfError; i++) {
System.out.print(" ");
}
System.out.println("^");  // a visual marker of where the error has occurred
}

switch (typeOfError) {
case MATCHING_ERROR                :
System.out.println("Paired delimeters do not match"); break;
case MISSING_RIGHT_DELIMETER_ERROR :
System.out.println("Missing right delimeter"); break;
case MISSING_LEFT_DELIMETER_ERROR  :
System.out.println("Missing left delimter"); break;
}
}

public static void main(String[] args) {
DelimeterChecker dc = new DelimeterChecker();
System.out.println("Enter an expression to check..");
Scanner scanner = new Scanner(System.in);
String s = scanner.nextLine();
scanner.close();
System.out.println();
boolean isValid = dc.isValid(s);
System.out.println( (! isValid ? "An error was found" : "No errors were found"));
}

}