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.


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
            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;
            default: // no action on other characters
         } // 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) {
          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;
              System.out.println("Missing right delimeter"); break;
              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(;
     String s = scanner.nextLine();
     boolean isValid = dc.isValid(s);
     System.out.println( (! isValid ? "An error was found" : "No errors were found"));