= Optimal stack evaluation of a binary expression tree
{title2=$d(e\circ f)=\min\{\max(d(e),1+d(f)),\max(d(f),1+d(e))\}$}
Suppose each subtree of a <binary expression tree> is evaluated completely before its sibling, leaves one result on an operand <stack>, and is not spilled or interleaved. If the child depths are $p,q$, evaluating the first child needs $p$ slots and keeping its result while evaluating the second needs $1+q$. Reversing the order gives $\max(q,1+p)$. If either order preserves the expression's meaning, the minimum is $\max(p,q)$ when $p\ne q$ and $p+1$ when $p=q$. For example, if $p>q$, integrality gives $p\geq q+1$, so evaluating the deeper child first attains the lower bound $p$. If $p=q$, the second child needs its own $p$ slots plus one saved result regardless of order. Induction over the <binary expression tree> proves optimality in this evaluation model.
For a noncommutative operator, an instruction swapping the top two <stack> entries or a reverse-operand opcode permits the same ordering while preserving operand positions. Reordering still requires absence of order-sensitive <side effects>. Reassociation and interleaving are separate transformations and are not part of this optimality claim.
Back to article page
