eCheck11B

There are many examples of structures that nest.

• parentheses in a mathematical expression
• parentheses in a Java method invocation
• braces in a Java program
• for loops (or any loops for that matter)
• HTML (sort of) and many other markup languages

eCheck11B asks you to write a program that checks if a mathematical expression involving (), [], and {} is nested correctly. The problem calls (), [], and {} precedence characters.

Examples

Correctly nested:

(a + b) * (c + d)
a * (b * [c + d] + e)
(([[a + b] / c] + d) * e) + f
f * [g - h * {i + j * k}]

Incorrectly nested:

imbalanced    (a + b) * (c + d
overlapping    a * (b * [c + d) + e]
imbalanced    (([[a + b] / c + d) * e) + f
overlapping    f * [g - h * {i + j * k]}

Stack

A stack is a collection where the client can add and retrieve elements only from the "top" (beginning) of the collection. Adding an element is called a push and retrieving an element is called a pop. Popping an element effectively removes the element from the collection.

Stack 1

push "A"

Stack 2

push "B"

Stack 3

push "C"

Stack 4

pop

Stack 5

push "D", push "E", push "F", push "G"

Java Stack

Java provides a Stack class:

Critique this implementation based on your knowledge of what a stack is and inheritance in Java.

Using a Stack to Check Nested Structures

We can make two observations about valid expressions:

1. the number of opening precedence characters (, [, { must be the same as the number of closing precedence characters ), ], }.
2. looking at the string from left to right
   • the first closing precedence character indicates the end of the innermost nested precedence character pair
   • the second closing precedence character indicates the end of the second innermost nested precedence character pair
   • the third closing precedence character indicates the end of the third innermost nested precedence character pair
   • and so on

Using a Stack to Check Nested Structures

for each character c in the string
{
   if c is an opening precedence character
   {
      push c onto a stack
   }
   else if c is a closing precedence character
   {
      pop the stack
      if the popped character does not pair with c
      {
         string is not valid
      }
   }
}
if the stack is not empty
{
   string is not valid
}
else
{
   string is valid
}

Solution Using java.util.Stack

Note: this doesn't quite solve the eCheck. The eCheck tells you to use type.lib.CharStack which implements a fixed-size stack.

import java.util.*;
import java.io.*;
import java.nio.*;

public class Check11B
{
   public static void main(String [] args)
   {
      PrintStream output = System.out;
      Scanner input = new Scanner(System.in);
      
      output.println("Enter expression");
      String expression = input.next().trim();
      
      Stack<Character> precedenceChars = new Stack<Character>();
      try
      {
         for (int i = 0; i < expression.length(); i++)
         {
            char c = expression.charAt(i);
            if (c == '(' || c == '[' || c == '{')
            {
               precedenceChars.push(c);
            }
            else if (c == ')' || c == ']' || c == '}')
            {
               char top = precedenceChars.pop();
               if ((c == ')' && top != '(') ||
                   (c == ']' && top != '[') ||
                   (c == '}' && top != '{'))
               {
                  throw new UnsupportedOperationException("Mismatched precedence character");
               }
            }
         }
         if (precedenceChars.size() != 0)
         {
            output.println("Imbalanced");
         }
         else
         {
            output.println("OK");
         }
      }
      catch (EmptyStackException ex)
      {
         output.println("Imbalanced");
      }
      catch (UnsupportedOperationException ex)
      {
         output.println("Overlapping");
      }
   }
}