Let Q be an arithmetic expression written in infix notation. Besides operands and operators, Q may also contain left and right parentheses. We assume that the operators in Q consist only of exponentiations (↑), multiplications (*), divisions (/), additions (+) and subtractions (-), and that they have the usual three levels of precedence as given above. We also assume that operators on the same level, including exponentiations, are performed from left to right unless otherwise indicated by parentheses. (This is not standard, since expressions may contain unary operators and some languages perform the exponentiations from right to left. However, these assumptions simplify our algorithm.)

The following algorithm transforms the infix expression Q into its equivalent postfix expression P. The algorithm uses a stack to temporarily hold operators and left parentheses. The postfix expression P will be constructed from left to right using the operands from Q and the operators, which are removed from STACK. We begin by pushing a left parenthesis onto STACK and adding a right parenthesis at the end of Q. The algorithm is completed when STACK is empty.

Algorithm: POLISH(Q, P)

Suppose Q is an arithmetic expression written in infix notation. This algorithm finds the equivalent postfix expression P.

1. Push "(" onto STACK, and add ")" to the end of Q.

2. Scan Q from left to right and repeat Steps 3 to 6 for each element of Q until the STACK is empty:

3. If an operand is encountered, add it to P.

4. If a left parenthesis is encountered, push it onto STACK.

5. If an operator ⊗ is encountered, then:

(a) Repeatedly pop from STACK and add to P each operator (on

the top of STACK) which has the same precedence as or higher precedence than ⊗.

(b) Add ⊗ to STACK.

[End of If structure.]

6. If a right parenthesis is encountered, then:

(a) Repeatedly pop from STACK and add to P each operator (on

the top of STACK) until a left parenthesis is encountered.

(b) Remove the left parenthesis. [Do not add the left parenthesis to P.]

[End of If structure.]

[End of Step 2 loop.]

7. Exit.

The terminology sometimes used for Step 5 is that ⊗ will "sink" to its own level. .

EXAMPLE

Consider the following arithmetic infix expression Q:

Q: A+(B*C- (D/E↑F)*G)*H

We simulate the previous algorithm to transform Q into its equivalent postfix expression P.

First we push "(" onto STACK, and then we add ")" to the end of Q to obtain:

A + ( B * C - ( D / E ↑ F ) * G ) * H )

(1) (2) (3) (4) (5) (6) (7) (8) (9) (10) (11) (12) (13)(14) (15) (16)(17) (18)(19) (20)

The elements of Q have now been labeled from left to right for easy reference. Table below shows the status of STACK and of the string P as each element of Q is scanned. Observe that

(1) Each operand is simply added to P and does not change STACK.

(2) The subtraction operator (-) in row 7 sends * from STACK to P before it (-) is pushed onto STACK.

(3) The right parenthesis in row 14 sends j and then I from STACK to P, and then removes the left parenthesis from the top of STACK.

(4) The right parenthesis in row 20 sends * and then + from STACK to P, and then removes-the left parenthesis from the top of STACK.

After Step 20 is executed, the STACK is empty and

P: A B C * D E F ↑ / G * - H * +

which is the required postfix equivalent of Q.

Resources

Top Categories

Product

Company