/*
To actually implement the shuffling, the parser had first to be modified
so as to build a parse tree rather than evaluating the result as it goes.
Like this:
*/

// Arrays instead of structs for expression tree nodes.
// Leaf nodes have O[E]==0 with the data value in V[E].
// Other nodes have the operator in O[E] with V[E] unused.
// L[E] and R[E] point to (are indices of) subnodes.

int newnode(int op, int val, int left, int right) {
  if (next>=max) fail("Arrays full");
  o[next] = op; v[next]=val; l[next] = left; r[next] = right;
  return next++;
}

// The result of EXPR is the index to the top level node describing
// the (sub-)expression it has built.

int expr (int refprec) {
int op,p,f,l,r;
  if (skip('-')) {                    // unary prefix (only minus)
    r = expr(precminus);              // get operand
    if (o[r]==0) {                    // that was a constant:
      v[r] = -v[r]; l = r;            // negate it directly
    } else l = newnode('-',0,nil,r);
  } else if (skip('(')) {             // bracketed subexpression
    l = expr(0); if (!skip(')')) fail("Close bracket missing");
  } else if (sym>='0' && sym<='9') {  // bare operand
    l = 0; do {l = l*10-'0'+sym; skip(sym);} while (sym>='0' && sym<='9');
    l = newnode(0,l,nil,nil);
  } else fail("Operand expected");
  while (1) {
    op = sym; f = prec(op); p = f>>2<<2;
    if (p<=refprec) if (p<refprec || (f&2)==0) return l;
    skip(op); r = nil; if ((f&1)==0) r = expr(p);
    l = newnode(op,0,l,r);
  }
}

/*
Notice how there is no longer (a need for) a separate operand getting
function, this task being absorbed into EXPR itself.

Next thing we do is write an expression evaluator, to which the result
of the top level call to EXPR can be passed.  Like this:
*/

int eval (int e) {
int a,b,c;
  if (e==nil) return dummy; b = o[e];
  if (b==0) {    // leaf node
    a = v[e]; printf("Push #%d\n",a); return a;
  }
  if (b=='@') return eval(shuffle(l[e]));
  a = eval(l[e]); c = eval(r[e]);
  return calculate(a,b,c);
}

/*
Now we can implement the special treatment required to do the shuffling,
which involves rearranging the tree before evaluating it.  Notice where the
'@' operator is intercepted in EVAL above.  The rearranging itself looks
hairier than it is:
*/

int shuffle (int e) {
// Rearrange an expression tree such that any divide ops on the
// left are bubbled up to the top and merged into a single one.
int mainop,left,right,leftop,ll,lr;
  if (e==nil) fail("Shuffle nil?");
  mainop = o[e]; if (mainop==0) return e;   // leaf node
  if (mainop!='*' && mainop!='/') return e; // not '*' or '/': nothing to do
  l[e] = shuffle(l[e]);                     // do sub-shuffle first
  left  = l[e]; ll = l[left]; leftop = o[left];
  right = r[e]; lr = r[left];
  if (mainop=='*') {
    if (leftop=='/') {      // change (ll/lr)*right to (ll*right)/lr
      r[e] = lr; o[e] = '/'; o[left] = '*'; r[left] = right;
    }
  } else if (leftop=='/') { // change (ll/lr)/right to ll/(lr*right)
    l[e] = lr; o[e] = '*'; r[left] = e; e = left;
  }
  return e;
}

/*
And the result:

3! - 2! + 2 * 4! / 5 * 11 / 6! / 12 * 7@ - 100
Push #3
Factorial: 3! = 6
Push #2
Factorial: 2! = 2
Subtract: 6-2 = 4
Push #2
Push #4
Factorial: 4! = 24
Multiply: 2*24 = 48
Push #11
Multiply: 48*11 = 528
Push #7
Multiply: 528*7 = 3696
Push #5
Push #6
Factorial: 6! = 720
Multiply: 5*720 = 3600
Push #12
Multiply: 3600*12 = 43200
Divide: 3696/43200 = 0
Add: 4+0 = 4
Push #100
Subtract: 4-100 = -96
Result: -96

*/