#include <gmp.h>
#include <stdio.h>
#include <ctype.h>
#include <limits.h>
#include <stdlib.h>
#include <stdarg.h>
#include <strings.h>

extern const char *__progname;

/*
 * Some fundamental constants and related types.
 *
 * IOBASE is the base numbers are read and printed in.
 */

#define IOBASE 10

/*
 * Internal data structure types and constants.
 *
 * Enum types:
 *	BINARYOP - a binary operation (eg, *)
 *	UNARYOP - a unary operation (eg, -)
 *	NODETYPE - the type field of a `NODE'
 *	TOKTYPE - the type of a `token'
 *
 * Struct types:
 *
 *	FXN
 *		Describes a built-in function.  Just a name, a flags
 *		field, and an implementation function pointer.
 *
 *	NODE
 *		Recursive data structure used to store an expression's
 *		parse tree.  It is a discriminated union, with a
 *		NODETYPE giving its general type (constant, binary
 *		operator, etc) and a union giving type-specific details
 *		(constant's value, operation and operands, etc).
 *
 *	NUM
 *		A number.  A number's value is just a gmp MP_INT.
 *		Numbers also have reference counts (see below).
 *
 *	NUMLIST
 *		A list of NUMs, with small integers (ints) attached.
 *		This is used for the value history list.
 *
 *	VAR
 *		A variable.  Just a name/value pair, with a link field
 *		to chain them together in the rudimentary symbol table
 *		we keep them in.
 */

enum nodetype {
  NT_CONST,	/* constant (ie, a number) */
  NT_VAR,	/* a variable */
  NT_HIST,	/* a reference to the history */
  NT_UNARY,	/* a unary operation */
  NT_BINARY,	/* a binary operation */
  NT_FUNCTION	/* a function call */
  } ;

enum unaryop {
  U_PLUS,	/* Monadic + */
  U_MINUS	/* Mondaic - */
  } ;

enum binaryop {
  B_PLUS,	/* Dyadic + */
  B_MINUS,	/* Dyadic - */
  B_TIMES,	/* * */
  B_DIVIDE,	/* / */
  B_MOD,	/* % */
  B_ASSIGN	/* = */
  } ;

enum toktype {
  TOK_EOF,	/* Saw EOF on input */
  TOK_EOL,	/* End-of-line */
  TOK_ERR,	/* Error condition */
  TOK_NUMBER,	/* Number */
  TOK_VAR,	/* Variable name */
  TOK_CHAR	/* Otherwise unclassifiable single character */
  } ;

typedef enum binaryop BINARYOP;
typedef enum nodetype NODETYPE;
typedef enum toktype TOKTYPE;
typedef enum unaryop UNARYOP;
typedef struct fxn FXN;
typedef struct node NODE;
typedef struct num NUM;
typedef struct numlist NUMLIST;
typedef struct var VAR;

/*
 * Numbers have reference counts.  This is done in order to permit
 *  functions to modify NUMs passed to them, to avoid creating lots of
 *  very-transient NUMs, while still allowing pointers to them to be
 *  saved in places like the history list without having those NUMs
 *  getting modified unexpectedly.  See num_modify for more.
 */
struct num {
  unsigned int refcnt;
  MP_INT v;
  } ;

struct numlist {
  NUMLIST *link;
  int n;
  NUM *value;
  } ;

struct node {
  NODETYPE type;
  union {
    NUM *c;		/* if NT_CONST */
    char *var;		/* if NT_VAR */
    int hist;		/* if NT_HIST */
    struct {		/* if NT_UNARY */
      UNARYOP op;		/* operation */
      NODE *arg;		/* operand */
      } u;
    struct {		/* if NT_BINARY */
      BINARYOP op;		/* operation */
      NODE *lhs;		/* first operand */
      NODE *rhs;		/* second operand */
      } b;
    struct {		/* if NT_FUNCTION */
      char *name;		/* function's name (malloced) */
      int inx;			/* index in function table
				   (-1 if not yet looked up) */
      int nargs;		/* number of arguments given */
      NODE **args;		/* the arguments themselves */
      } f;
    } u;
  } ;

/* If value is nil, the variable "doesn't exist". */
struct var {
  VAR *link;
  char *name;
  NUM *value;
  } ;

/*
 * A function can evaluate its arguments or not.  If FF_NOEVAL is
 *  clear, the arguments will be evaluated and (*u.numfn) will be
 *  called with the resulting NUMs; if FF_NOEVAL is set, the arguments
 *  will not be evaluated and (*u.nodefn) will be called with the
 *  NODEs.
 */
struct fxn {
  const char *name;
  union {
    NUM *(*numfn)(int, NUM **);
    NUM *(*nodefn)(int, NODE **);
    } u;
  unsigned int flags;
#define FF_NOEVAL 0x00000001
  } ;

/* Initializer macros. */
#define NUMFN(name) { #name, { numfn: C_##name }, 0 }
#define NODEFN(name) { #name, { nodefn: C_##name }, FF_NOEVAL }

/* The table of builtin functions. */
static NUM *C_pow(int, NUM **);
static NUM *C_abs(int, NUM **);
static NUM *C_gcd(int, NUM **);
static NUM *C_lcm(int, NUM **);
static NUM *C_modpow(int, NUM **);
static FXN fxns[] = { NUMFN(pow),
		      NUMFN(abs),
		      NUMFN(gcd),
		      NUMFN(lcm),
		      NUMFN(modpow),
		      { 0 } };

/* State variables. */

/* Number of the expression currently being dealt with. */
static int exprno;
/* The chain of variables. */
static VAR *vars;
/* The list of past output numbers. */
static NUMLIST *history;
/* Did we push back the last token read? */
static int untokened;
/* The type of the last token read. */
static TOKTYPE toktype;
/* The length in characters of the last token read. */
static int toklen;
/* The characters making up the last token read. */
static char *tokbuf;
/* The amount of space malloced to tokbuf. */
static int tokhave;
/* If toktype is TOK_NUMBER, this is the NUM for it. */
static NUM *toknum;
/* If toktype is TOK_NUMBER, this is an int for it.
   Used primarily when parsing history list references. */
static int tokinum;
/* Input pushback, but at the character level. */
static int ungetval;
/* Flag indicating a character was pushed back. */
static int ungotten;
/* Indicates debugging output wanted. */
static int debugging;

/*
 * qflag indicates that -q was given, in which case prompts and output
 *  history number markers aren't printed (largely for use in shell
 *  scripts).  qtemp is a little like qflag, but stronger (it
 *  suppresses the output of the expression value too); it's cleared
 *  after reading each expression, and is used to support ending
 *  expressions with semicolons to indicate that the output should not
 *  be printed.
 */

static int qflag = 0;
static int qtemp = 0;

/*
 * The parser is a recursive-descent one, and has to call up in the
 *  call hierarchy to handle parenthesized subexpressions.  This
 *  forward declaration is here for that.
 */
static NODE *parse_top(void);

/*
 * Initialize the whole system at startup.
 */
static void init(void)
{
 exprno = 1;
 vars = 0;
 history = 0;
 untokened = 0;
 tokbuf = 0;
 tokhave = 0;
 toknum = 0;
 ungotten = 0;
 debugging = 0;
}

/* Get an input character.  Handles character-level pushback. */
static int get(void)
{
 if (ungotten)
  { ungotten = 0;
    return(ungetval);
  }
 return(getchar());
}

/* Push back a character onto the input. */
static void unget(int c)
{
 ungotten = 1;
 ungetval = c;
}

/* Flush input to the next newline.  Called on error. */
static void flushnl(void)
{
 int c;

 do
  { c = get();
  } while ((c != '\n') && (c != EOF));
}

/*
 * Allocate a new NUM.  It's returned with refcount==1 and value zero.
 */
static NUM *num_alloc(void)
{
 NUM *rv;

 rv = malloc(sizeof(NUM));
 rv->refcnt = 1;
 mpz_init(&rv->v);
 return(rv);
}

/*
 * Free a NUM.  You should approximately never call this directly;
 *  releasing NUMs should normally be done through num_deref.
 */
static void num_free(NUM *n)
{
 mpz_clear(&n->v);
 free(n);
}

/*
 * Increment the reference count on a NUM.  Includes sanity checking.
 */
static NUM *num_ref(NUM *n)
{
 n->refcnt ++;
 if (n->refcnt > 100) abort();
 return(n);
}

/*
 * Decrement the reference count on a NUM; if this is the last
 *  reference, actually free it.  Includes some sanity checks.
 */
static void num_deref(NUM *n)
{
 if (n == 0) return;
 if (n->refcnt == 0) abort();
 n->refcnt --;
 if (n->refcnt > 100) abort();
 if (n->refcnt == 0) num_free(n);
}

/*
 * Free a NODE, and everything it points to.
 */
static void node_free(NODE *n)
{
 switch (n->type)
  { case NT_CONST:
       num_deref(n->u.c);
       break;
    case NT_VAR:
       free(n->u.var);
       break;
    case NT_HIST:
       break;
    case NT_UNARY:
       node_free(n->u.u.arg);
       break;
    case NT_BINARY:
       node_free(n->u.b.lhs);
       node_free(n->u.b.rhs);
       break;
    case NT_FUNCTION:
	{ int i;
	  free(n->u.f.name);
	  for (i=0;i<n->u.f.nargs;i++) node_free(n->u.f.args[i]);
	  free(n->u.f.args);
	}
       break;
  }
 free(n);
}

/*
 * Make a copy of a NUM.  The copy always has refcount 1; the original
 *  does not have its refcount affected.
 */
static NUM *copynum(NUM *n)
{
 NUM *rv;

 rv = malloc(sizeof(NUM));
 mpz_init_set(&rv->v,&n->v);
 rv->refcnt = 1;
 return(rv);
}

/*
 * Prepare to modify a NUM.  minrefs must be the expected value of the
 *  reference count if there are no "other" references; if the actual
 *  refcount is greater than this, a copy of the number is returned
 *  instead (and one reference to the original is dropped).
 *
 * Note that minrefs<1 does not make sense; the caller must always have
 *  a reference to the NUM (or shouldn't have the pointer in the first
 *  place) and will do something with the referred-to NUM upon return
 *  (or there's no reason to call num_modify).  This means that the
 *  num_deref call in the body will never actually free n, so there is
 *  no actual use-after-free risk.
 */
static NUM *num_modify(NUM *n, int minrefs)
{
 if (minrefs < 1) abort();
 if (n->refcnt > minrefs)
  { num_deref(n);
    n = copynum(n);
  }
 return(n);
}

/*
 * Store a NUM into a variable, dereffing the NUM that was there first.
 */
#define SETREF(loc,num) do { num_deref(loc); (loc) = num_ref(num); } while (0)

/*
 * Construct a new NODE, given all the ingredients.  The first argument
 *  gives the type; the rest of the arglist is type-specific:
 *
 *	NT_CONST
 *		A NUM *, giving the constant value.
 *	NT_VAR
 *		A char *, giving the variable name.
 *	NT_HIST
 *		An int, giving the history-list entry number.
 *	NT_UNARY
 *		An int (should be a UNARYOP, but they're promoted to
 *		ints as varargs arguments) giving the operation, then a
 *		NODE * giving the operand.
 *	NT_BINARY
 *		A NODE * giving the left operand, then an int (should
 *		be a BINARYOP, but they're promoted to ints as varargs
 *		arguments) giving the operation, then a NODE * giving
 *		the right operand.
 *	NT_FUNCTION
 *		A char * giving the function name, then an int giving
 *		the number of arguments, then that many more NODE *
 *		arguments, each giving one argument.  Note that there
 *		is no way to node_make a function call with a run-time
 *		variable number of arguments; for that, you need to
 *		frob at least the nargs and args fields yourself.
 */
static NODE *node_make(NODETYPE type, ...)
{
 NODE *n;
 va_list ap;

 n = malloc(sizeof(NODE));
 n->type = type;
 va_start(ap,type);
 switch (type)
  { default: abort(); break;
    case NT_CONST:
       n->u.c = va_arg(ap,NUM *);
       break;
    case NT_VAR:
       n->u.var = va_arg(ap,char *);
       break;
    case NT_HIST:
       n->u.hist = va_arg(ap,int);
       break;
    case NT_UNARY:
       n->u.u.op = va_arg(ap,int);
       n->u.u.arg = va_arg(ap,NODE *);
       break;
    case NT_BINARY:
       n->u.b.lhs = va_arg(ap,NODE *);
       n->u.b.op = va_arg(ap,int);
       n->u.b.rhs = va_arg(ap,NODE *);
       break;
    case NT_FUNCTION:
	{ int i;
	  n->u.f.name = va_arg(ap,char *);
	  n->u.f.inx = -1;
	  n->u.f.nargs = va_arg(ap,int);
	  n->u.f.args = malloc(n->u.f.nargs*sizeof(NODE *));
	  for (i=0;i<n->u.f.nargs;i++) n->u.f.args[i] = va_arg(ap,NODE *);
	}
       break;
  }
 va_end(ap);
 return(n);
}

#if 0
/*
 * Return a NUM with value equal to the int arg.
 */
static NUM *num_for_int(int v)
{
 NUM *n;

 n = num_alloc();
 mpz_set_si(&n->v,v);
 return(n);
}
#endif

/*
 * Multiply two NUMs.
 */
static NUM *num_mul(NUM *n1, NUM *n2)
{
 NUM *rv;

 rv = num_alloc();
 mpz_mul(&rv->v,&n1->v,&n2->v);
 return(rv);
}

/*
 * Divide one NUM by another.  If n2 is zero, print a complaint and
 *  return nil.
 */
static NUM *num_div(NUM *n1, NUM *n2)
{
 NUM *rv;

 if (! mpz_sgn(&n2->v))
  { printf("division by zero\n");
    return(0);
  }
 rv = num_alloc();
 mpz_tdiv_q(&rv->v,&n1->v,&n2->v);
 return(rv);
}

/*
 * Divide one NUM by another, returning the remainder.  If n2 is zero,
 *  print a complaint and return nil.
 */
static NUM *num_mod(NUM *n1, NUM *n2)
{
 NUM *rv;

 if (! mpz_sgn(&n2->v))
  { printf("modulus by zero\n");
    return(0);
  }
 rv = num_alloc();
 mpz_tdiv_r(&rv->v,&n1->v,&n2->v);
 return(rv);
}

/*
 * Add two NUMs.
 */
static NUM *num_add(NUM *n1, NUM *n2)
{
 NUM *rv;

 rv = num_alloc();
 mpz_add(&rv->v,&n1->v,&n2->v);
 return(rv);
}

/*
 * Subtract one NUM from another.
 */
static NUM *num_sub(NUM *n1, NUM *n2)
{
 NUM *rv;

 rv = num_alloc();
 mpz_sub(&rv->v,&n1->v,&n2->v);
 return(rv);
}

/*
 * Look up a VAR by name.  If it's not found, return nil (if create is
 *  false) or create it and return it (if create is true).
 */
static VAR *var_by_name(const char *name, int create)
{
 VAR *v;

 for (v=vars;v&&strcmp(v->name,name);v=v->link) ;
 if (!v && create)
  { v = malloc(sizeof(VAR));
    v->name = strdup(name);
    v->link = vars;
    vars = v;
    v->value = 0;
  }
 return(v);
}

/*
 * Given a function name, look up the index for it.  Returns -1 if the
 *  name is not in the list.
 */
static int function_lookup(const char *name)
{
 int i;

 for (i=0;fxns[i].name;i++) if (!strcmp(fxns[i].name,name)) return(i);
 return(-1);
}

/*
 * Evaluate a NODE, returning its value (or a nil pointer on error,
 *  with a message printed to stderr).
 */
static NUM *evalnode(NODE *n)
{
 switch (n->type)
  { case NT_CONST:
       return(num_ref(n->u.c));
       break;
    case NT_VAR:
	{ VAR *v;
	  for (v=vars;v&&strcmp(v->name,n->u.var);v=v->link) ;
	  if (v && v->value) return(num_ref(v->value));
	  printf("no variable `%s' defined\n",n->u.var);
	  return(0);
	}
       break;
    case NT_HIST:
	{ NUMLIST *h;
	  for (h=history;h&&(h->n!=n->u.hist);h=h->link) ;
	  if (h) return(num_ref(h->value));
	  printf("no history element #%d exists\n",n->u.hist);
	  return(0);
	}
       break;
    case NT_UNARY:
	{ NUM *a;
	  a = evalnode(n->u.u.arg);
	  if (a == 0) return(0);
	  switch (n->u.u.op)
	   { case U_PLUS:
		return(a);
		break;
	     case U_MINUS:
		a = num_modify(a,1);
		mpz_neg(&a->v,&a->v);
		return(a);
		break;
	   }
	}
       break;
    case NT_BINARY:
       switch (n->u.b.op)
	{ case B_ASSIGN:
	      { VAR *v;
		NUM *val;
		if (n->u.b.lhs->type != NT_VAR)
		 { printf("invalid lhs of =, somehow, in evalnode");
		   return(0);
		 }
		val = evalnode(n->u.b.rhs);
		if (! val) return(0);
		v = var_by_name(n->u.b.lhs->u.var,1);
		SETREF(v->value,val);
		return(val);
	      }
	     break;
	  default:
	      { NUM *lhs;
		NUM *rhs;
		NUM *rv;
		lhs = evalnode(n->u.b.lhs);
		rhs = evalnode(n->u.b.rhs);
		if (!lhs || !rhs)
		 { if (lhs) num_deref(lhs);
		   if (rhs) num_deref(rhs);
		   return(0);
		 }
		switch (n->u.b.op)
		 { case B_PLUS:
		      rv = num_add(lhs,rhs);
		      break;
		   case B_MINUS:
		      rv = num_sub(lhs,rhs);
		      break;
		   case B_TIMES:
		      rv = num_mul(lhs,rhs);
		      break;
		   case B_DIVIDE:
		      rv = num_div(lhs,rhs);
		      break;
		   case B_MOD:
		      rv = num_mod(lhs,rhs);
		      break;
		   case B_ASSIGN: /* shut up -Wswitch */
		      break;
		 }
		num_deref(lhs);
		num_deref(rhs);
		return(rv);
	      }
	     break;
	}
       break;
    case NT_FUNCTION:
	{ int fx;
	  NUM **args;
	  int i;
	  NUM *rv;
	  fx = n->u.f.inx;
	  if (fx < 0)
	   { fx = function_lookup(n->u.f.name);
	     if (fx < 0)
	      { printf("unknown function name `%s'\n",n->u.f.name);
		return(0);
	      }
	     n->u.f.inx = fx;
	   }
	  if (fxns[fx].flags & FF_NOEVAL)
	   { rv = (*fxns[fx].u.nodefn)(n->u.f.nargs,n->u.f.args);
	   }
	  else
	   { args = malloc(n->u.f.nargs*sizeof(NUM *));
	     for (i=0;i<n->u.f.nargs;i++)
	      { args[i] = evalnode(n->u.f.args[i]);
		if (! args[i])
		 { for (;i>0;i--) num_deref(args[i]);
		   return(0);
		 }
	      }
	     rv = (*fxns[fx].u.numfn)(n->u.f.nargs,args);
	     for (i=0;i<n->u.f.nargs;i++) num_deref(args[i]);
	   }
	  return(rv);
	}
       break;
  }
 fprintf(stderr,"invalid node type %d in evalnode\n",(int)n->type);
 abort();
 return(0);
}

/*
 * Return the value of a NUM as an int.
 */
static int num_intval(NUM *n)
{
 return(mpz_get_si(&n->v));
}

/*
 * Handle pow(x,y).  Unlike modpow(), we don't need to handle exponents
 *  too large to fit in an int.
 */
static NUM *C_pow(int nargs, NUM **args)
{
 NUM *rv;
 int i;

 if (nargs != 2)
  { printf("usage: pow(base,power)\n");
    return(0);
  }
 i = num_intval(args[1]);
 if (i < 0)
  { printf("negative power in pow()\n");
    return(0);
  }
 rv = num_alloc();
 mpz_pow_ui(&rv->v,&args[0]->v,i);
 return(rv);
}

/*
 * Handle modpow(x,y).
 */
static NUM *C_modpow(int nargs, NUM **args)
{
 NUM *rv;

 if (nargs != 3)
  { printf("usage: modpow(base,power,modulus)\n");
    return(0);
  }
 if (! mpz_sgn(&args[2]->v))
  { printf("modulus by zero\n");
    return(0);
  }
 if (mpz_sgn(&args[1]->v) < 0)
  { printf("negative exponent to modpow\n");
    return(0);
  }
 rv = num_alloc();
 mpz_powm(&rv->v,&args[0]->v,&args[1]->v,&args[2]->v);
 return(rv);
}

/*
 * Handle abs().  Pretty trivial.
 */
static NUM *C_abs(int nargs, NUM **args)
{
 NUM *n;

 if (nargs != 1)
  { printf("usage: abs(num)\n");
    return(0);
  }
 n = num_alloc();
 mpz_abs(&n->v,&args[0]->v);
 return(n);
}

/*
 * Handle gcd().  Pretty trivial.
 */
static NUM *C_gcd(int nargs, NUM **args)
{
 NUM *n;
 int i;

 n = num_alloc();
 mpz_set_ui(&n->v,0);
 for (i=0;i<nargs;i++) mpz_gcd(&n->v,&n->v,&args[i]->v);
 return(n);
}

/*
 * Handle lcm().  Not hard, though there seems to be no mpz_lcm, so we
 *  have to do the a*b/gcd(a,b) thing....
 */
static NUM *C_lcm(int nargs, NUM **args)
{
 NUM *n;
 int i;
 MP_INT t;
 MP_INT p;

 n = num_alloc();
 mpz_set_ui(&n->v,1);
 mpz_init(&t);
 mpz_init(&p);
 for (i=0;i<nargs;i++)
  { mpz_gcd(&t,&n->v,&args[i]->v);
    mpz_divexact(&t,&n->v,&t);
    mpz_mul(&n->v,&args[i]->v,&t);
  }
 return(n);
}

/*
 * Print a NUM to stdout, in IOBASE.
 */
static void printnum(NUM *n)
{
 mpz_out_str(stdout,IOBASE,&n->v);
}

/*
 * Dump out a NODE.  Debugging routine.
 */
static void dumpnode(NODE *n)
{
 switch (n->type)
  { case NT_CONST:
       printf("<CONST:");
       printnum(n->u.c);
       printf(">");
       break;
    case NT_VAR:
       printf("<VAR:%s>",n->u.var);
       break;
    case NT_HIST:
       printf("<HIST:%d>",n->u.hist);
       break;
    case NT_UNARY:
       printf("<UNARY:");
       switch (n->u.u.op)
	{ case U_PLUS:  printf("PLUS:");  break;
	  case U_MINUS: printf("MINUS:"); break;
	}
       dumpnode(n->u.u.arg);
       printf(">");
       break;
    case NT_BINARY:
       printf("<BINARY:");
       switch (n->u.b.op)
	{ case B_PLUS:   printf("PLUS:");   break;
	  case B_MINUS:  printf("MINUS:");  break;
	  case B_TIMES:  printf("TIMES:");  break;
	  case B_DIVIDE: printf("DIVIDE:"); break;
	  case B_MOD:    printf("MOD:");    break;
	  case B_ASSIGN: printf("ASSIGN:"); break;
	}
       dumpnode(n->u.b.lhs);
       printf(":");
       dumpnode(n->u.b.rhs);
       printf(">");
       break;
    case NT_FUNCTION:
	{ int i;
	  printf("<FUNCTION:%s[%d]:%d",n->u.f.name,n->u.f.inx,n->u.f.nargs);
	  for (i=0;i<n->u.f.nargs;i++)
	   { printf(":");
	     dumpnode(n->u.f.args[i]);
	   }
	  printf(">");
	}
       break;
  }
}

/*
 * Set the character character `off' in the current token to `val',
 *  reallocating tokbuf if necessary.
 */
static void settokc(int off, char val)
{
 if (off >= tokhave)
  { tokhave = off + 1;
    tokbuf = realloc(tokbuf,tokhave);
  }
 tokbuf[off] = val;
}

/*
 * Read a `number' token.  Argument is the first character of the
 *  number, which our caller must have already checked is a digit.
 */
static void token_number(int c)
{
 int i;

 i = 0;
 do
  { settokc(i++,c);
    c = get();
  } while (isdigit(c));
 unget(c);
 toktype = TOK_NUMBER;
 settokc(i,'\0');
 toknum = toknum ? num_modify(toknum,1) : num_alloc();
 mpz_set_str(&toknum->v,tokbuf,10);
 tokinum = mpz_get_ui(&toknum->v);
}

/*
 * Read a `variable' token.  Argument is the first character, which our
 *  caller must have checked is appropriate to begin a variable.
 */
static void token_var(int c)
{
 int i;

 settokc(0,c);
 i = 1;
 while (1)
  { c = get();
    if (! isalnum(c)) break;
    settokc(i++,c);
  }
 unget(c);
 settokc(i,'\0');
 toktype = TOK_VAR;
}

/*
 * Read a single-character token.  This is a catchall.
 */
static void token_char(int c)
{
 toklen = 1;
 settokc(0,c);
 settokc(1,'\0');
 toktype = TOK_CHAR;
}

/*
 * Read a token.  Handles pushed-back tokens and otherwise checks the
 *  first character to see what sort of token it is....
 */
static void token(int geteol)
{
 int c;

 if (untokened)
  { untokened = 0;
    if (geteol || (toktype != TOK_EOL)) return;
  }
 do
  { c = get();
    if (c == EOF)
     { toktype = TOK_EOF;
       return;
     }
    if ((c == '\n') && geteol)
     { toktype = TOK_EOL;
       return;
     }
  } while (isspace(c));
      if (isdigit(c)) token_number(c);
 else if (isalpha(c)) token_var(c);
 else                 token_char(c);
}

/*
 * Push back the last-read token.
 */
static void untoken(void)
{
 untokened = 1;
}

/*
 * Implement a syscmd which sets an int.
 */
static void syscmd_setvar(int *varp, int min, int max, const char *what)
{
 int val;
 int c;

 val = 0;
 while (1)
  { c = get();
    if ((c == '\n') || (c == EOF))
     { unget(c);
       break;
     }
    if (!isdigit(c)) continue;
    val = (val * 10) + (c - '0');
  }
 if ((val < min) || (val > max))
  { printf("%s value out of range [%d..%d]\n",what,min,max);
  }
 else
  { *varp = val;
    printf("%s set to %d.\n",what,val);
  }
}

/*
 * Implement the `get help' syscmd.
 */
static void syscmd_help(void)
{
 printf("\
Operators: * (multiplication), / (divison), + (addition), - (subtraction)\n\
           %% (remainder), = (assignment), or function calls.\n\
Functions: abs(value) - absolute value\n\
           pow(base,power) - computes powers\n\
           modpow(base,power,modulus) - computes modular powers\n\
");
}

/*
 * Check to see if the next `expression' is really a syscmd (flagged by
 *  a ? as the first character).  If so, process it and return 1; else,
 *  return 0.  Our caller must have already skipped whitespace.
 */
static int syscmd(void)
{
 int c;

 c = get();
 if (c == '?')
  { c = get();
    switch (c)
     { case EOF: unget(EOF); return(1); break;
       case '?': case '\n':
	  printf("?d  %3d (debugging, 0 or 1)\n",debugging);
	  printf("?h (get help)\n");
	  break;
       case 'd':
	  syscmd_setvar(&debugging,0,1,"debugging");
	  break;
       case 'h':
	  syscmd_help();
	  break;
       default:
	  printf("unknown syscmd `%c'\n",c);
	  break;
     }
    do
     { c = get();
     } while ((c != '\n') && (c != EOF));
    unget('\n');
    return(1);
  }
 unget(c);
 return(0);
}

/*
 * Parse an object which can be a terminal (constant or variable), a
 *  parenthesized subexpression, function call, or any of those
 *  preceded by any sequence of unary operators.
 */
static NODE *parse_unary(void)
{
 NODE *new;

 token(0);
 switch (toktype)
  { case TOK_EOF:
    case TOK_EOL: /* shut up -Wswitch */
    case TOK_ERR:
       return(0);
       break;
    case TOK_NUMBER:
       new = node_make(NT_CONST,toknum);
       toknum = 0;
       break;
    case TOK_VAR:
	{ char *vstr;
	  vstr = strdup(tokbuf);
	  token(1);
	  if ((toktype == TOK_CHAR) && (tokbuf[0] == '('))
	   { new = node_make(NT_FUNCTION,vstr,0);
	     while (1)
	      { NODE *arg;
		arg = parse_top();
		if (! arg)
		 { node_free(new);
		   return(0);
		 }
		new->u.f.args = realloc(new->u.f.args,(new->u.f.nargs+1)*sizeof(NODE *));
		new->u.f.args[new->u.f.nargs++] = arg;
		token(0);
		if ((toktype == TOK_CHAR) && (tokbuf[0] == ')')) break;
		if ((toktype == TOK_CHAR) && (tokbuf[0] == ',')) continue;
		printf("invalid argument list delimiter\n");
		node_free(new);
		return(0);
	      }
	   }
	  else
	   { untoken();
	     new = node_make(NT_VAR,vstr);
	   }
	}
       break;
    case TOK_CHAR:
       if (tokbuf[0] == '$')
	{ int h;
	  token(0);
	  if ((toktype == TOK_CHAR) && (tokbuf[0] == '$'))
	   { if (exprno > 1)
	      { h = exprno - 1;
	      }
	     else
	      { printf("no previous value available for $$\n");
		return(0);
	      }
	   }
	  else if (toktype == TOK_NUMBER)
	   { h = tokinum;
	     if ((h < 1) || (h >= exprno))
	      { printf("no history value $%d available\n",tokinum);
		return(0);
	      }
	   }
	  else if ((toktype == TOK_CHAR) && (tokbuf[0] == '-'))
	   { token(0);
	     if (toktype != TOK_NUMBER)
	      { untoken();
		tokinum = 1;
	      }
	     h = exprno - tokinum;
	     if ((h < 1) || (h >= exprno))
	      { printf("no history value $%d available\n",-tokinum);
		return(0);
	      }
	   }
	  else
	   { printf("invalid/missing number after $\n");
	     return(0);
	   }
	  new = node_make(NT_HIST,h);
	}
       else if (tokbuf[0] == '(')
	{ new = parse_top();
	  if (! new) return(0);
	  token(0);
	  if ((toktype != TOK_CHAR) || (tokbuf[0] != ')'))
	   { printf("unclosed (\n");
	     node_free(new);
	     return(0);
	   }
	}
       else
	{ UNARYOP op;
	  NODE *rhs;
	  switch (tokbuf[0])
	   { case '+': op = U_PLUS;  break;
	     case '-': op = U_MINUS; break;
	     default:
		printf("unknown operator `%c'\n",tokbuf[0]);
		return(0);
		break;
	   }
	  rhs = parse_unary();
	  if (! rhs) return(0);
	  new = node_make(NT_UNARY,op,rhs);
	}
       break;
  }
 return(new);
}

/*
 * Parse multiplicative-precedence dyadic operators: *, /, %
 */
static NODE *parse_muldiv(void)
{
 NODE *lhs;
 NODE *rhs;
 BINARYOP op;
 NODE *new;

 lhs = parse_unary();
 if (! lhs) return(0);
 while (1)
  { token(1);
    if ((toktype == TOK_CHAR) && (tokbuf[0] == '*'))
     { op = B_TIMES;
     }
    else if ((toktype == TOK_CHAR) && (tokbuf[0] == '/'))
     { op = B_DIVIDE;
     }
    else if ((toktype == TOK_CHAR) && (tokbuf[0] == '%'))
     { op = B_MOD;
     }
    else
     { untoken();
       return(lhs);
     }
    rhs = parse_unary();
    if (! rhs)
     { node_free(lhs);
       return(0);
     }
    new = node_make(NT_BINARY,lhs,op,rhs);
    lhs = new;
  }
}

/*
 * Parse additive-precedence dyadic operators: +, -
 */
static NODE *parse_addsub(void)
{
 NODE *lhs;
 NODE *rhs;
 BINARYOP op;
 NODE *new;

 lhs = parse_muldiv();
 if (! lhs) return(0);
 while (1)
  { token(1);
    if ((toktype == TOK_CHAR) && (tokbuf[0] == '+'))
     { op = B_PLUS;
     }
    else if ((toktype == TOK_CHAR) && (tokbuf[0] == '-'))
     { op = B_MINUS;
     }
    else
     { untoken();
       return(lhs);
     }
    rhs = parse_muldiv();
    if (! rhs)
     { node_free(lhs);
       return(0);
     }
    new = node_make(NT_BINARY,lhs,op,rhs);
    lhs = new;
  }
}

/*
 * Parse assignment-precedence dyadic operators: =
 */
static NODE *parse_assign(void)
{
 NODE *lhs;
 NODE *rhs;
 NODE *new;

 lhs = parse_addsub();
 if (! lhs) return(0);
 token(1);
 if ((toktype != TOK_CHAR) || (tokbuf[0] != '='))
  { untoken();
    return(lhs);
  }
 if (lhs->type != NT_VAR)
  { printf("invalid lhs of =\n");
    node_free(lhs);
    return(0);
  }
 rhs = parse_assign();
 if (! rhs)
  { node_free(lhs);
    return(0);
  }
 new = node_make(NT_BINARY,lhs,B_ASSIGN,rhs);
 return(new);
}

/*
 * Parse the lowest-precedence thing - called for parenthesized
 *  subexpressions, for function arguments, and for the main parse.
 */
static NODE *parse_top(void)
{
 return(parse_assign());
}

/*
 * Main parser entry point: checks for syscmds, parses, and checks for
 *  trailing semicolon don't-print markers.
 */
static NODE *parse(void)
{
 int c;
 NODE *n;

 do
  { c = get();
  } while (isspace(c) && (c != '\n') && (c != EOF));
 if (c == EOF) exit(0);
 unget(c);
 if (c == '\n') return(0);
 if (syscmd()) return(0);
 n = parse_top();
 if (n == 0) return(0);
 token(1);
 if (toktype == TOK_EOL) return(n);
 if ((toktype == TOK_CHAR) && (tokbuf[0] == ';'))
  { qtemp = 1;
    return(n);
  }
 untoken();
 return(n);
}

/*
 * Execute a NODE, printing the result (unless ;-suppressed) and
 *  putting it on the history list.
 */
static void execute(NODE *n)
{
 NUM *rv;
 NUMLIST *nl;

 rv = evalnode(n);
 if (! rv) return;
 if (! qtemp)
  { if (! qflag) printf("$%d = ",exprno);
    printnum(rv);
    printf("\n");
  }
 nl = malloc(sizeof(NUMLIST));
 nl->n = exprno;
 nl->value = rv;
 nl->link = history;
 history = nl;
 exprno ++;
}

/*
 * Parse command-line flags.
 */
static void handleargs(int ac, char **av)
{
 int skip;
 int errs;

 skip = 0;
 errs = 0;
 for (ac--,av++;ac;ac--,av++)
  { if (skip > 0)
     { skip --;
       continue;
     }
    if (**av != '-')
     { fprintf(stderr,"%s: unrecognized argument `%s'\n",__progname,*av);
       errs ++;
       continue;
     }
#if 0
    if (0)
     {
needarg:;
       fprintf(stderr,"%s: %s needs a following argument\n",__progname,*av);
       errs ++;
       continue;
     }
#endif
#define WANTARG() do { if (++skip >= ac) goto needarg; } while (0)
    if (!strcmp(*av,"-q"))
     { qflag = 1;
       continue;
     }
    if (!strcmp(*av,"-Q"))
     { qflag = 0;
       continue;
     }
#undef WANTARG
    fprintf(stderr,"%s: unrecognized option `%s'\n",__progname,*av);
    errs ++;
  }
 if (errs) exit(1);
}

/*
 * main.  Fairly boring.
 */
int main(int, char **);
int main(int ac, char **av)
{
 handleargs(ac,av);
 init();
 while (1)
  { NODE *n;
    if (!qflag && !qtemp) printf("%d> ",exprno);
    qtemp = 0;
    n = parse();
    if (n)
     { if (debugging)
	{ dumpnode(n);
	  printf("\n");
	}
       execute(n);
       node_free(n);
     }
    else
     { flushnl();
     }
  }
}