/* Program written in class 10/5/99, with stack class modified to
   be a list of "stackelements" consisting of a char and an int.
*/

public class oct5
{

stack tos;       // front  
public void push(char newchar,int pos)
 { // puts new stackelement at front of stack list
   tos = new stack( (new stackelement(newchar,pos)) , tos);  
 }

public stackelement pop()
{ if (tos != null)
   { stackelement temp = tos.element;  // datum to return
     tos = tos.below;
     return temp;
   }
  else {  System.err.println("Stack Empty");
          return  null;
       }
}  // pop

public stackelement peek()
{ if (tos != null) return tos.element;
  else {  System.err.println("Stack Empty");
          return  null;
       }
}  

public boolean empty() { return (tos == null); }

public static void main(String[] args)
{ 
  try { java.io.InputStreamReader lr =    // set up keyboard input
          new java.io.InputStreamReader(System.in);
        java.io.BufferedReader lineinput =
          new java.io.BufferedReader(lr);

  String S;    // string containing expression to be processed.
  System.out.print("Enter an expression: ");
  S = lineinput.readLine();

  oct5 parenstack = new oct5();
  int length = S.length();
  int pos = 0;   // current char position in string
  while (pos < length)
  {  char currentchar = S.charAt(pos);
     if (currentchar == '(') parenstack.push('(',pos);
     if (currentchar == ')')
       { if (parenstack.empty()) 
           System.out.println("Umatched ) at position " + pos);
         else parenstack.pop();  // note here the value returned is discarded
       }
     pos++;  // go to next char in string
  } // end while loop

  while (!(parenstack.empty())) 
    System.out.println("Unmatched ( at position " + 
      parenstack.pop().position);


      } catch (Exception e) {}   // closes try
}  // main

} // end public class oct5


class stack
{
//  char element;   // quick but wrong way
//  int position;
  stackelement element;
  stack below;    // tail
  public stack(stackelement h, stack t)
   { element = h;  below = t; }
}


// data type stored in stack:
class stackelement
{
   char c;
   int position;
   stackelement(char e, int p) { c = e; position = p; }
}