/* Scrivere un metodo Java che, data una stringa alfanumerica
   contenente anche parentesi tonde, quadre, e graffe, decida
   se tutte le parentesi sono correttamente accoppiate e se
   sono poste nel giusto ordine.
*/
public class Esame_18_06_2002_1a {
  public static void main(String[] args) {
    System.out.println(isCorrect("a[] + ( io siadosi( sd0'99 [ weqwe (b*c - [4+1])]))"));
  }
  
  public static boolean isCorrect(String par) {
    myPila p = new myPila();
    char car, cp;
    for (int k = 0; k < par.length(); k++) {
      car = par.charAt(k);
      if (car == '(' || car == '[' || car == '{')
        p.push(new Character(car));
      else if (car == ')' || car == ']' || car == '}') {
        if (p.isEmpty()) return false;          //pila vuota? errore!
        cp = ((Character)p.pop()).charValue();  //convers.in char
        if ( (cp == '(' && car != ')') ||
             (cp == '[' && car != ']') ||
             (cp == '{' && car != '}') ) {
          return false;
        }
      }
    }
    if (p.isEmpty()) return true;
    else return false;
  }
}

//Mini pila dinamica per esercizio
class myPila {
  private MiniLista elem;
  //builder
  public myPila() {
    elem = new MiniLista();
  }
  //public method
  public boolean isEmpty() {
    return elem.isEmpty();
  }
  public void push(Object o) {
    elem.insertHead(o);
  }
  public Object pop() {
    if (elem.isEmpty())
      throw new EmptyStackException();
    else
      return elem.deleteHead();
  }
  public Object topElem() {
    if (elem.isEmpty())
      throw new EmptyStackException();
    else
    return elem.getHead().getInfo();
  }
}

//*******************CLASSI ACCESSORIE**************************
//Mini lista ad oggetti (serve a MiniCoda)
class MiniLista {
  private Nodo head;
  public MiniLista() {
    head = null;
  }
  public Nodo getHead() {
    return head;
  }
  public boolean isEmpty() {
    return (head == null);
  }
  
  public void insertTail(Object val) {
    if (isEmpty())
      head = new Nodo(val);
    else {
      Nodo aux = head;
      for (; aux.getNext() != null; aux = aux.getNext());
      aux.setNext(new Nodo(val));
    }
  }
  public Object deleteHead() {
    if (isEmpty())
      throw new EmptyListException();
    else {
      Object val = head.getInfo();
      head = head.getNext();
      return val;
    }
  }
  
  public void insertHead(Object o) {
    head = new Nodo(o, head);
  }
}

class Nodo {
  private Object info;
  private Nodo next;
  //costruttori
  public Nodo(Object val) {this(val, null);}
  public Nodo(Object val, Nodo n) {
    info = val;
    next = n;
  }
  //metodi pubblici
  public void setInfo(Object val) {info = val;}
  public Object getInfo() {return info;}
  
  public void setNext(Nodo n) {next = n;}
  public Nodo getNext() {return next;}  
}

class EmptyStackException extends RuntimeException {
  public EmptyStackException() {
    super("Pila vuota!");
  }
}