/*****************************************************************************/
/*                                                                           */
/*                   Evaluating a Matching Expression                        */
/*                                                                           */
/*                    December 1997, Toshimi Minoura                         */
/*                     October 1999, Jacob Lundberg                          */
/*                                                                           */
/*****************************************************************************/

// The expression stored in exp[] defined in class Matching is evaluated.
// An element of exp[] is '[', '(', ')', or ']'.

class CharStack  {
  private char data[];           // storage for data stacked
  private int top;              // index to top of stack

  public CharStack() {              // constructor
    data = new char[100];
    top = -1;                   // initially, stack is empty
  }

  public void push(char x) {
    top++;
    data[top] = x;
  }

  public char pop() {
    return data[top--];
  }

  public char peek() { 
    if( top == -1 )
      return (char)0;
    else
      return data[top];
  }

  public void clear() {
    top = -1;
  }

  public void dataPrint() {                    // print stack content
    System.out.print("Stack: top = " + top + ", data = ");
    for (int i = 0; i <= top; i++) {
      System.out.print(data[i]);    // print every value in data[
      if (i < top) System.out.print(", ");
    };
    if( top == -1 )
      System.out.print("-empty-");
    System.out.println("");
  }
}

class Matching {
  static char exp[] =  { '[', '(', ')', '[', '(', ')', ']', ']' };
  static CharStack stack = new CharStack();

  public static void main(String argv[]) { 
    boolean matchOK = true;
    System.out.println("Evaluation (re)started");
    stack.clear();                        // clear stack
    int currentIdx = 0;                   // set index to start of expression
    for ( ; currentIdx < exp.length; currentIdx++) { 
      System.out.println("exp[" + currentIdx + "] = " + exp[currentIdx]); // print element
      if (exp[currentIdx] == '[' || exp[currentIdx] == '(') { 
         System.out.println("" + exp[currentIdx] + " found.");  // opening type char found
         stack.push(exp[currentIdx]);               // push exp[currentIdx] onto stack
         System.out.println( "" + exp[currentIdx] + " pushed onto stack"); 
      } else if (exp[currentIdx] == ']' || exp[currentIdx] == ')') {
         System.out.println("" + exp[currentIdx] + " found");   // closing type char found
         if( ( stack.peek() == '[' && exp[currentIdx] == ']' ) ||
             ( stack.peek() == '(' && exp[currentIdx] == ')' ) ) { 
           System.out.println("Matching " + stack.peek() + " and " + exp[currentIdx] + " found.");
         } else { 
           System.out.println(" ** Invalid match of " + stack.peek() + " to " + exp[currentIdx] + ". ** ");
           matchOK = false;
         }
         stack.pop();
      } else {
         System.out.println("Unimportant char '" + exp[currentIdx] + "' ignored.");
      }
      System.out.println("One element processed");
      stack.dataPrint();                  // print stack content
    }
    System.out.println("Evaluation completed");
    if( matchOK == true && stack.peek() == (char)0 )
      System.out.println("Expression acceptable.");
    else
      System.out.println("Expression unacceptable.");
  }  
}