Stacks and Their Operations

Before any rules are introduced, try a short challenge. The expression below is written in postfix form, which means the operator comes after the values it works on. Read it from left to right and decide what single number it produces. Make a prediction first, and only then check the answer.

If your guess was 10 or 24, the mistake most likely came from applying the operators in the wrong order or from combining the wrong numbers. The rest of this article explains the procedure that avoids both errors. Notice that the answer depends only on the order of the symbols. No parentheses were needed to tell the reader what to compute.

The notation most people learn first is infix. In infix, the operator sits between the two values it combines, as in 6 - 3. This is comfortable for people to read, but it is awkward for a simple machine. Grouping and precedence rules require the reader to look ahead to decide what to compute first.

Postfix notation rearranges the same ingredients so that the operator trails the two values it acts on. The expression 6 - 3 becomes 6 3 -. The expression (6 - 3) * 4 becomes 6 3 - 4 *. The second form needs no parentheses at all, because the order of the symbols alone tells the reader what to compute.

Suppose a program reads a calculation one symbol at a time and must produce a single number at the end. When it sees a number, it cannot yet know what will be done with it, because the operator that uses it may appear much later. So the program has to hold on to that number. Holding values until they are needed, and always reaching for the most recently held value first, is exactly the behavior of a stack.

Postfix expressions can be processed in one pass from left to right. Nothing needs to be reread or reordered. This is what makes them convenient to process with a stack.

Every token in a postfix expression falls into one of two cases, and the procedure depends only on which case applies. Tokens are read in order from left to right.

For addition and multiplication, the order of the two popped values does not change the result. For subtraction and division it does. For these operators, the first popped value is the right operand, and the second popped value is the left operand. The pop order must be respected, or the answer will be wrong.

The diagram below traces the postfix expression 6 3 - 4 *, which is the postfix form of (6 - 3) * 4. Each node shows a token and the stack contents after that token has been processed. The stack is written from bottom to top, so the rightmost value is the top.

The next expression is not from the source. It shows how an operator can use a result produced by an earlier operator. Read it carefully, and watch which values are on the stack when each operator arrives. The postfix expression is 5 1 2 + 4 * + 3 -.

Notice that the first plus did not use the 5 at all. It combined the two most recent values, 1 and 2. The 5 stayed on the stack, waiting until the second plus was reached. This is the behavior that makes a stack the right structure: values wait exactly until the operator that needs them appears.