1998 note: As I've learned more about parsers and compilers,
I realize that what I wrote here was a hand-crafted hybrid
of a traditional recursive-descent parser and a shift/reduce
table-driven parser for what is probably an LL(1) grammar. I
haven't become so expert yet that I'm sure exactly just
which kind of grammar this parses, but as far as I can tell,
this could all be done with recursive-descent; I simply
hacked in a cool shortcut to avoid lots of recursive
functions that would merely serve to figure out precedence.

--------

/* In the following description, I use the terms "number", "value" and "node"
    somewhat loosely, as they can all refer to the same things - a number
    (integer, floating point, fraction, "dimensioned"), or a whole tree
    representing an expression that would evaluate to one of the
    aformentioned.
*/
/* These three arrays contain all the info needed to drive the parser.  Each
    operator has a corresponding priority (on an arbitrary scale), and a
    type: infix (binary), prefix, or postfix. Note that operators with the
    same symbol but different meanings must be carefully arranged in order
    to parse right. */
EXPORT char const operator[OPS][OPLEN] = {
        "Null operator",
		"+","-","*","/","^","AND","NOT","!","OR","MOD","-",
		"&&","&","~","||","|"
	};
EXPORT int const priority[OPS] = {
		0,
		120,120,130,130,135,50,140,132,40,130,140,
		50,80,140,40,60
	};
/* Operator type: 0=NULL, 1=infix (binary), 2=prefix, 3=postfix */
EXPORT int const optype[OPS] = {
		0,
		1,1,1,1,1,1,2,3,1,1,2,
		1,1,2,1,1
	};

/* Here is the pseudo-C algorithim that is the guts of the parser.
Parenthesized sub-expressions are handled in a traditional recursive-
descent manner, by a recursive call (from the value parsing function) */
parse(string to parse)
{
    create local operand and number stacks;
    put NULL on operand and number stacks;
        /* NULL here is used as a kind of ultimate lowest priority operator */
    forever {
        if next symbol could be a prefix operand, /* if it could be, it is */
            push on operand stack;
            continue;
        /* else if next symbol is another kind of operand, there's an error */
        n = parse a value (a number, dimensioned number, variable name, or
            recursively parse a parethesized sub-expression);
        forever {
            op = parse operator;    /* op is actually an integer */
            while (priority[op] <= priority[operator on top of stack]) {
                if (priority[op] == pririty[operator on top of stack] &&
                        op is not NULL)
                    return n;  /* Except for error handling (which I haven't
                        included here), this is they only point of exit.  It
                        is reached after the algorithm has hit the end of the
                        string or an unmatched right parenthesis and then
                        having "reduced" - converted all the leftover operators
                        and numbers on the stacks into an expression tree, n.*/

                if (op on top of stack is a prefix operator) {
                    n2 = new node representing the operator on the stack
                        operating on n;
                    n = n2;
                } else {
                    /* Operator is binary (infix) */
                    n2 = new node representing the operator on the stack
                        operating on the number on the stack and n;
                    n = n2;
                    pop number stack;
                }
                pop operator stack;
            } /* end while */
            if (op is a postfix operator) {
                n2 = new node representing operator op operating on n;
                n = n2;
            } else {
                /* op is a lower priority binary (infix) operator */
                push op on operator stack;
                push n on number stack;
                break; /* to outer forever loop */
            }
        } /* end inner forever */
    } /* end outer forever */
    /* This point never reached */
}