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

public class XToken
{
  private static Hashtable htPrefix = new Hashtable();
  private static Hashtable htNormal = new Hashtable();

  private String text;
  private int id;
  private int priority;
  private int valency;
  private int category;
  private boolean groupsRtoL;

  private double value;
  private static double[] valstk = new double[0x100];

  public static final int EQUALS = 0;
  public static final int UNARYPLUS = 1;
  public static final int UNARYMINUS = 2;
  public static final int SQR = 3;
  public static final int CUBE = 4;

  public static final int ABS = 0x100;
  public static final int ACOS = 0x101;
  public static final int ASIN = 0x102;
  public static final int ATAN = 0x103;
  public static final int ATAN2 = 0x104;
  public static final int CEIL = 0x105;
  public static final int COS = 0x106;
  public static final int EXP = 0x107;
  public static final int FLOOR = 0x108;
  public static final int IEEEREM = 0x109;
  public static final int LOG = 0x10A;
  public static final int MAX = 0x10B;
  public static final int MIN = 0x10C;
  public static final int RANDOM = 0x10F;
  public static final int RINT = 0x110;
  public static final int ROUND = 0x111;
  public static final int SIN = 0x112;
  public static final int SQRT = 0x113;
  public static final int TAN = 0x114;
  public static final int E = 0x120;
  public static final int PI = 0x121;

  public static final int ATOMIC    = 0;
  public static final int PREFIX    = 1;
  public static final int POSTFIX   = 2;
  public static final int BINARY    = 3;
  public static final int VARIADIC  = 4;
  public static final int BRA = 5;
  public static final int KET = 6;
  public static final int COMMA  = 7;
  public static final int CONSTANT  = 8;
  public static final int VARIABLE  = 9;

  public static final XToken XTBRA
    = new XToken( "(", '(', 0, 0, BRA );
  public static final XToken XTKET
    = new XToken( ")", ')', 0, 0, KET );
  public static final XToken XTCOMMA
    = new XToken( ",", ',', 0, 0, COMMA );

  private static final String catName[] =
    { "Atomic", "Prefix", "Postfix", "Binary",
        "Variadic", "(", ")", "Comma", "Constant", "Variable" };

  private XToken( double v )
  {
    this( null, v );
  }
  private XToken( String text, double value )
  {
    this.text = text;
    this.category = CONSTANT;
    this.value = value;
  }
  private XToken( String text, int id, int priority,
                    int valency, int category )
  {
    this( text, id, priority, valency, category, false );
  }
  private XToken( String text, int id, int priority,
                    int valency, int category, boolean groupsRtoL )
  {
    this.text = text;
    this.id = id;
    this.priority = priority;
    this.valency = valency;
    this.category = category;
    this.groupsRtoL = groupsRtoL;
    if( category == PREFIX )
      htPrefix.put( text, this );
    else
      htNormal.put( text, this );
    if( category == ATOMIC )
      htPrefix.put( text, this );
  }

  public String getText()
  {
    return text;
  }

  public int getID()
  {
    return id;
  }

  public int getPriority()
  {
    return priority;
  }

  public int getValency()
  {
    return valency;
  }

  public int getCategory()
  {
    return category;
  }

  public double getValue()
  {
    return value;
  }

  public void setValue( double v )
  {
    value = v;
  }

  public String toString()
  {
    if( category == CONSTANT )
      return "" + value;
    if( category == VARIABLE )
      return catName[category]+ ":" + text;
      // return catName[category]+ ":" + text + ": Value=" + value;
    if( category == BINARY )
      return catName[category]+ ":" + text;
      // return catName[category]+ ":" + text + ": ID=" + id;
             // + " Priority=" + priority + " GroupsRtoL:" + groupsRtoL ;
    if( ( category == PREFIX ) || ( category == POSTFIX ) )
      return catName[category]+ ":" + text;
      // return catName[category]+ ":" + text + ": ID=" + id;
             // + " Priority=" + priority;
    if( category == ATOMIC )
      return catName[category]+ ":" + text;
      // return catName[category]+ ":" + text + ": ID=" + id;
    if( ( category == BRA ) || ( category == KET )
        || ( category == COMMA ) )
      return text;

    return catName[category]+ ":" + text + ": ID=" + id
             + " Priority=" + priority + " Valency=" + valency;
  }

  static {
    XToken o;

    o = new XToken( "=", '=', 10, 2, BINARY, true );
    o = new XToken( "+", '+', 10, 2, BINARY );
    o = new XToken( "-", '-', 10, 2, BINARY );
    o = new XToken( "*", '*', 20, 2, BINARY );
    o = new XToken( "/", '/', 20, 2, BINARY );
    o = new XToken( "MAX", MAX, 20, 2, BINARY );
    o = new XToken( "MIN", MIN, 20, 2, BINARY );
    o = new XToken( "ARG", ATAN2, 20, 2, BINARY );
    o = new XToken( "%", IEEEREM, 20, 2, BINARY );
    o = new XToken( "^", '^', 30, 2, BINARY, true );

    o = new XToken( "+", UNARYPLUS, 50, 1, PREFIX );
    o = new XToken( "-", UNARYMINUS, 50, 1, PREFIX );
    o = new XToken( "abs", ABS, 50, 1, PREFIX );
    o = new XToken( "acos", ACOS, 50, 1, PREFIX );
    o = new XToken( "asin", ASIN, 50, 1, PREFIX );
    o = new XToken( "atan", ATAN, 50, 1, PREFIX );
    o = new XToken( "ceil", CEIL, 50, 1, PREFIX );
    o = new XToken( "cos", COS, 50, 1, PREFIX );
    o = new XToken( "exp", EXP, 50, 1, PREFIX );
    o = new XToken( "floor", FLOOR, 50, 1, PREFIX );
    o = new XToken( "log", LOG, 50, 1, PREFIX );
    o = new XToken( "rint", RINT, 50, 1, PREFIX );
    o = new XToken( "round", ROUND, 50, 1, PREFIX );
    o = new XToken( "sin", SIN, 50, 1, PREFIX );
    o = new XToken( "sqrt", SQRT, 50, 1, PREFIX );
    o = new XToken( "tan", TAN, 50, 1, PREFIX );

    o = new XToken( "sqr", SQR, 50, 1, POSTFIX );
    o = new XToken( "cube", CUBE, 50, 1, POSTFIX );

    o = new XToken( "?", RANDOM, 100, 0, ATOMIC );
    o = new XToken( "E", E, 100, 0, ATOMIC );
    o = new XToken( "PI", PI, 100, 0, ATOMIC );

  }

  public static XToken findPrefixOperator( String txt )
  {
    return findOperator( txt, true );
  }
  public static XToken findNormalOperator( String txt )
  {
    return findOperator( txt, false );
  }
  public static XToken findOperator( String txt, boolean prefix )
  {
    Object o;

    if( prefix )
      o = htPrefix.get( txt );
    else
      o = htNormal.get( txt );

    if( o instanceof XToken )
      return (XToken) o;

    return null;
  }

  public static boolean getCanEnd( Object o )
  {
    if( o instanceof XToken ) {
      XToken xt = (XToken) o;
      switch( xt.category ) {
        case PREFIX:
        case BINARY:
        case BRA:
        case COMMA:
          return false;
      }
    }
    return true;
  }

  public static Vector processInputStream( InputStream in )
    throws IOException
  {
    Vector v = new Vector();
    boolean canEnd = false;

    StreamTokenizer T = new StreamTokenizer( in );
    T.eolIsSignificant( true );
    T.ordinaryChar( '/' );
    T.ordinaryChar( '-' );

    for(;;) {
      Object xt;
      int ttype = T.nextToken();
      if( ttype == T.TT_EOF )
        break;
      String txt = "";
      xt = null;
      switch( ttype ) {
        case StreamTokenizer.TT_NUMBER:
          // txt = "NUMBER: " + T.nval;
          xt = new Value( T.nval );
          break;
        case StreamTokenizer.TT_EOL:
          txt = "EOL";
          continue;
          // break;
        case '(':
          xt = XTBRA;
          break;
        case ')':
          xt = XTKET;
          break;
        case ',':
          xt = XTCOMMA;
          break;
        case '=':
        case '*':
        case '/':
        case '^':
        case '?':
        case '%':
          xt = findNormalOperator( ""+(char)ttype );
          break;
        case '+':
        case '-':
          xt = findOperator( ""+(char)ttype, !canEnd );
          break;
        case StreamTokenizer.TT_WORD:
          xt = findOperator( T.sval, !canEnd );
          if( xt == null )
          {
            xt = Variable.get( T.sval );
            if( xt == null )
              xt = Variable.create( T.sval, 0.0 );
          }
          break;
        default:
          continue;
      }

      v.addElement( xt );
      // System.out.println( txt );
      canEnd = getCanEnd( xt );
    }
    return v;
  }

  public static Vector toPostFix( Vector toks )
  {
    int i, n;
    Vector pf;
    Stack opStack;
    opStack = new Stack();
    pf = new Vector();

    n = toks.size();
    for( i = 0; i < n; i++ )
    {
      Object o = toks.elementAt( i );
      if( o instanceof Value )
      {
        pf.addElement( o );
        continue;
      }
      if( !(o instanceof XToken) )
        continue;
      XToken xt = (XToken) o;
      if( ( xt.category == ATOMIC ) || ( xt.category == POSTFIX ) )
      {
        pf.addElement( xt );
        continue;
      }
      if( xt == XTBRA )
      {
        opStack.push( xt );
        continue;
      }
      if( xt == XTKET )
      {
        o = null;
        for( ;!opStack.empty(); )
        {
          o = opStack.pop();
          if( o == XTBRA )
            break;
          pf.addElement( o );
        }
        if( o != XTBRA )
          System.out.println( "ERROR:EXTRA KET" );
        continue;
      }
      o = null;
      for( ;!opStack.empty(); )
      {
        XToken xtop;
        xtop = (XToken)opStack.peek();
        if( xtop == XTBRA )
          break;
        if( xt.priority > xtop.priority )
          break;
        if( xt == xtop )
        {
          if( xt.groupsRtoL )
            break;
        }
        if( xt.priority <= xtop.priority )
          pf.addElement( opStack.pop() );
      }
      opStack.push( xt );
    }
    while( !opStack.empty() )
      pf.addElement( opStack.pop() );
    return pf;
  }

  public static double eval( Vector pfExp )
  {
    int i, n;
    int istk;

    istk = -1;

    n = pfExp.size();
    for( i = 0; i < n; i++ )
    {
      Object o = pfExp.elementAt( i );
      if( o instanceof Value )
      {
        Value V = (Value)o;
        istk++;
        if( istk >= valstk.length ) {
          System.out.println( "STACK UNDERFLOW" );
          return 0.0;
        }
        valstk[istk] = V.getValue();
        continue;
      }
      if( !( o instanceof XToken ) )
        continue;
      XToken xt = (XToken) o;
      if( xt.valency > istk + 1 ) {
        System.out.println( "STACK UNDERFLOW" );
        return 0.0;
      }
      if( xt.valency == 2 ) {
        double v2 = valstk[istk];
        double v1 = valstk[--istk];
        switch( xt.id ) {
          case '+':
            valstk[istk] = v1 + v2;
            break;
          case '-':
            valstk[istk] = v1 - v2;
            break;
          case '*':
            valstk[istk] = v1 * v2;
            break;
          case '/':
            valstk[istk] = v1 / v2;
            break;
          case '^':
            valstk[istk] = Math.pow( v1, v2 );
            break;
          case MAX:
            valstk[istk] = Math.max( v1, v2 );
            break;
          case MIN:
            valstk[istk] = Math.min( v1, v2 );
            break;
          case ATAN2:
            valstk[istk] = Math.atan2( v1, v2 );
            break;
          case IEEEREM:
            valstk[istk] = Math.IEEEremainder( v1, v2 );
            break;
        }
        continue;
      }
      switch( xt.id ) {
        case E:
          valstk[++istk] = Math.E;
          break;
        case PI:
          valstk[++istk] = Math.PI;
          break;
        case RANDOM:
          valstk[++istk] = Math.random();
          break;
        case UNARYMINUS:
          valstk[istk] = - valstk[istk];
          break;
        case ABS:
          valstk[istk] = Math.abs( valstk[istk] );
          break;
        case ACOS:
          valstk[istk] = Math.acos( valstk[istk] );
          break;
        case ATAN:
          valstk[istk] = Math.atan( valstk[istk] );
          break;
        case CEIL:
          valstk[istk] = Math.ceil( valstk[istk] );
          break;
        case COS:
          valstk[istk] = Math.cos( valstk[istk] );
          break;
        case EXP:
          valstk[istk] = Math.exp( valstk[istk] );
          break;
        case FLOOR:
          valstk[istk] = Math.floor( valstk[istk] );
          break;
        case LOG:
          valstk[istk] = Math.log( valstk[istk] );
          break;
        case RINT:
          valstk[istk] = Math.rint( valstk[istk] );
          break;
        case ROUND:
          valstk[istk] = Math.round( valstk[istk] );
          break;
        case SIN:
          valstk[istk] = Math.sin( valstk[istk] );
          break;
        case SQRT:
          valstk[istk] = Math.sqrt( valstk[istk] );
          break;
        case TAN:
          valstk[istk] = Math.tan( valstk[istk] );
          break;
        case SQR:
          valstk[istk] *= valstk[istk];
          break;
        case CUBE:
          valstk[istk] *= valstk[istk] * valstk[istk];
          break;
      }
    }
    return valstk[0];
  }

  public static Vector compileToPostFix( String expr )
  {
    Vector pf = null;
    try {
      InputStream in = new StringBufferInputStream( expr );
      Vector toks = processInputStream( in );
      pf = toPostFix( toks );
      in.close();
    } catch( IOException iex ) {
    }
    return pf;
  }

  public static void main( String args[] )
  {
    if( args.length > 0 ) {
      // String fileName = args[0];

      Vector pfExp = compileToPostFix( args[0] );
      // System.out.println( pfExp );
      // System.out.println( eval( pfExp ) );
    }
  }
/*
  public static void main( String[] args )
  {
    int i;
    XToken o;

    for( i = 0; i < args.length; i++ )
    {
      o = XToken.findPrefixOperator( args[i] );
      if( o != null )
        System.out.println( o );
      o = XToken.findNormalOperator( args[i] );
      System.out.println( o );
    }
  }
*/
}