Infix to Postfix With a Stack

Get access to whole semester resourcesSemester Pass

Chapter Thirty-Seven

Syllabus topic Module 1, "Stacks: Applications of stack like prefix to postfix notation"

Pages 111 to 113 of 411

In one line

Operands go straight to the output and operators wait on a stack until an operator of the same or higher precedence arrives, which is the algorithm known as shunting yard.

The algorithm

for each token:

operand : send it to the output

'(' : push it

')' : pop to the output until '(' is popped, and discard the '('

operator o : while the stack top is an operator of higher precedence,

or equal precedence and o is left associative: pop it to the output

then push o

at the end : pop everything remaining to the output

The one line that carries all the difficulty is the operator rule, and it says: an operator waiting on the stack goes to the output when something arrives that does not need to wait for it.

Associativity is why the rule says "equal precedence and left associative". For A - B - C, the first minus must come out before the second is pushed, because minus groups leftwards. For A ^ B ^ C it must not, because exponent groups rightwards.

Built, with the trace printed

PRECEDENCE = {"+": 1, "-": 1, "x": 2, "/": 2, "%": 2, "^": 3}
RIGHT_ASSOCIATIVE = {"^"}


def to_postfix(tokens, trace=False):
    """Shunting yard. Returns the postfix tokens."""
    output, stack = [], []
    if trace:
        print("%-6s %-24s %s" % ("token", "output", "stack"))
    for token in tokens:
        if token not in PRECEDENCE and token not in "()":
            output.append(token)
        elif token == "(":
            stack.append(token)
        elif token == ")":
            while stack and stack[-1] != "(":
                output.append(stack.pop())
            if not stack:
                raise ValueError("a ')' with no matching '('")
            stack.pop()                                  # discard the '('
        else:
            while (stack and stack[-1] != "("
                   and (PRECEDENCE[stack[-1]] > PRECEDENCE[token]
                        or (PRECEDENCE[stack[-1]] == PRECEDENCE[token]
                            and token not in RIGHT_ASSOCIATIVE))):
                output.append(stack.pop())
            stack.append(token)
        if trace:
            print("%-6s %-24s %s" % (token, " ".join(output), " ".join(stack)))
    while stack:
        if stack[-1] == "(":
            raise ValueError("a '(' that is never closed")
        output.append(stack.pop())
    if trace:
        print("%-6s %-24s %s" % ("end", " ".join(output), ""))
    return output


print("A + B x C - D")
to_postfix("A + B x C - D".split(), trace=True)

print()
# The tokens are split on spaces, so a bracket MUST be its own token.
# "(A + B)".split() gives "(A" and "B)", and the brackets are then read as
# part of the operand names: the first draft of this listing printed
# "(A B) C x +" and the gate caught it.
for infix in ["A + B x C", "( A + B ) x C", "A + B x C - D",
              "( A + B ) x ( C - D )", "A ^ B ^ C", "A - B - C",
              "A x ( B + C ) / D"]:
    print("%-22s -> %s" % (infix, " ".join(to_postfix(infix.split()))))

print()
for bad in ["A + B )", "( A + B"]:
    try:
        to_postfix(bad.split())
    except ValueError as e:
        print("%-12s refused: %s" % (bad, e))

Infix to Postfix With a Stack

A + B x C - D
token  output                   stack
A      A
+      A                        +
B      A B                      +
x      A B                      + x
C      A B C                    + x
-      A B C x +                -
D      A B C x + D              -
end    A B C x + D -

A + B x C              -> A B C x +
( A + B ) x C          -> A B + C x
A + B x C - D          -> A B C x + D -
( A + B ) x ( C - D )  -> A B + C D - x
A ^ B ^ C              -> A B C ^ ^
A - B - C              -> A B - C -
A x ( B + C ) / D      -> A B C + x D /

A + B )      refused: a ')' with no matching '('
( A + B      refused: a '(' that is never closed

Follow the trace at the -. The stack held + x. Minus has lower precedence than both, so both were popped to the output before minus was pushed. That single step is the algorithm.

Now compare the last two rows of the conversions, which is where associativity shows:

A ^ B ^ C gives A B C ^ ^. The first ^ stayed on the stack when the second arrived, because exponent is right associative, so the rightmost exponent is applied first.

A - B - C gives A B - C -. The first - came out when the second arrived, because minus is left associative.

Those two lines are the standard examination trap, and the program settles them.

Checking the conversions

The conversions above agree with chapter 36's, which were produced by a completely different method (walking a fully bracketed tree). Two independent methods agreeing is worth more than either one checked by eye.

Row by row: A + B x C gave A B C x + in both; ( A + B ) x C gave A B + C x in both; A + B x C - D gave A B C x + D - in both; ( A + B ) x ( C - D ) gave A B + C D - x in both.

The cost

Each token is pushed at most once and popped at most once, so the work is proportional to the number of tokens: O(n) time. The stack holds at most the operators currently waiting, so O(n) memory in the worst case, which is an expression like ((((A)))).

Infix to Postfix With a Stack

Quick revision

Operands go straight to the output; operators wait on a stack.
On an operator, pop while the top has higher precedence, or equal precedence and the new operator is

left associative; then push.

( is pushed; ) pops to the output until ( is found, and the ( is discarded, not output.
At the end, pop everything left; a ( still there means it was never closed.
A ^ B ^ C gives A B C ^ ^ (right associative) and A - B - C gives A B - C - (left

associative).

O(n) time, O(n) memory in the worst case.

Test yourself

1. What happens to an operand, and what happens to an operator? An operand goes straight to the output. An operator waits on the stack until an operator arrives that does not need to wait for it.

2. State the popping rule for an incoming operator o. Pop while the stack top is an operator with higher precedence, or with equal precedence when o is left associative. Then push o.

3. Convert (A + B) x C and show why brackets disappear. A B + C x. The ( is pushed and discarded when the ) arrives; the ) forces the + out before the x is considered, so the grouping is carried by the order of the output symbols.

4. Convert A ^ B ^ C and A - B - C, and explain the difference. A B C ^ ^ and A B - C -. Exponent is right associative so the waiting ^ is not popped when a second arrives; minus is left associative so the waiting - is.

5. What are the two bracket errors, and when is each detected? A ) with nothing matching, found when the stack empties while searching for a (; and a ( never closed, found when it is still on the stack at the end.

6. Give the time and memory costs and say why. O(n) time, because each token is pushed and popped at most once. O(n) memory in the worst case, since the stack may hold every operator, as in a deeply bracketed expression.

The rest of this subject

These notes are cut from the University's printed syllabus. Open the syllabus itself, or the past papers, for the same subject.

Issue