認 識 PreFix、InFix、PostFix

• 認 識 PreFix、InFix、PostFix

PreFix（前序式）：* + 1 2 + 3 4

InFix（中序式）： (1+2)*(3+4)

PostFix（後序式）：1 2 + 3 4 + *

後 序式的運算

例如：

運算時由 後序式的前方開始讀取，遇到運算元先存入堆疊，如果遇到運算子，則由堆疊中取出兩個運算元進行對應的運算，然後將結果存回堆疊，如果運算式讀取完 畢，那麼堆疊頂的值就是答案了，例如我們計算12+34+*這個運算式（也就是(1+2)*(3+4)）：

讀取 堆疊

1 1

2 1 2

+ 3 // 1+2 後存回

3 3 3

4 3 3 4

+ 3 7 // 3+4 後存回

* 21 // 3 * 7 後存回

Algorithm Gossip: 中序式轉後序式（前序式）

說 明

平常所使用的運算式，主要是將運算元放在運算子的兩旁，例如a+b/d這樣的式子，這稱之為中序（Infix）表示 式，對於人類來說，這樣的式子很容易理 解，但由於電腦執行指令時是有順序的，遇到中序表示式時，無法直接進行運算，而必須進一步判斷運算的先後順序，所以必須將中序表示式轉換為另一種表示方 法。

可以將中序表示式轉換為後序（Postfix）表示式，後序表示式又稱之為逆向波蘭表示式（Reverse polish notation），它是由波蘭的數學家盧卡謝維奇提出，例如(a+b)*(c+d)這個式子，表示為後序表示式時是ab+cd+*。 

解 法

用手算的方式來計算後序式相當的簡單，將運算子兩旁的運算元依先後順序全括號起來，然後將所有 的右括號取代為左邊最接近的運算子（從最內層括號開始），最後去掉所有的左括號就可以完成後序表示式，例如：

a+b*d+c/d   =>    ((a+(b*d))+(c/d)) -> abd*+cd/+

如果要用程式來進行中序轉後序，則必須使用堆疊，演算法很簡單，直接敘述的話就是使用迴圈，取出中序式的字元，遇運算元直接輸出；堆疊運算子與左括號； 堆疊中運算子優先順序大於讀入的運算子優先順序的話，直接輸出堆疊中的運算子，再將讀入的運算子置入堆疊；遇右括號輸出堆疊中的運算子至左括號。 

OP STACK OUTPUT

( ( -

a ( a

+ (+ a

b (+ ab

) - ab+

* * ab+

( *( ab+

c *( ab+c

+ *(+ ab+c

d *(+ ab+cd

) * ab+cd+

- - ab+cd+*

如果要將中序式轉為前序式，則在讀取中序式時是由後往前讀取，而左右括號的處理方式相反，其餘 不變，但輸出之前必須先置入堆疊，待轉換完成後再將堆疊中的 值由上往下讀出，如此就是前序表示式。 

Infix, Prefix and Postfix Expressions

Infix Expression Prefix Expression Postfix Expression

A + B + A B A B +

A + B * C + A * B C A B C * +

Infix Expression Prefix Expression Postfix Expression

(A + B) * C * + A B C A B + C *

Infix Expression Prefix Expression Postfix Expression

A + B * C + D + + A * B C D A B C * + D +

(A + B) * (C + D) * + A B + C D A B + C D + *

A * B + C * D + * A B * C D A B * C D * +

A + B + C + D + + + A B C D A B + C + D +

說明：將中序式轉換為後序式 的好處是，不用處理運算子先後順序問題，只要依序由運算式由前往後讀取即可。

例如(a+b)*(c+d)這個式子，依演算法的輸出過程如下：

When you write an arithmetic expression such as B * C, the form of the expression provides you with information so that you can interpret it correctly. In this case we know that the variable B is being multiplied by the variable C since the multiplication operator * appears between them in the expression. This type of notation is referred to as infix since the operator is in between the two operands that it is working on.

Consider another infix example, A + B * C. The operators + and * still appear between the operands, but there is a problem. Which operands do they work on? Does the + work on A and B or does the * take B and C? The expression seems ambiguous.

In fact, you have been reading and writing these types of expressions for a long time and they do not cause you any problem. The reason for this is that you know something about the operators + and *. Each operator has a precedence level. Operators of higher precedence are used before operators of lower precedence. The only thing that can change that order is the presence of parentheses. The precedence order for arithmetic operators places multiplication and division above addition and subtraction. If two operators of equal precedence appear, then a left-to-right ordering or associativity is used.

Let’s interpret the troublesome expression A + B * C using operator precedence. B and C are multiplied first, and A is then added to that result. (A + B) * C would force the addition of A and B to be done first before the multiplication. In expression A + B + C, by precedence (via associativity), the leftmost + would be done first.

Although all this may be obvious to you, remember that computers need to know exactly what operators to perform and in what order. One way to write an expression that guarantees there will be no confusion with respect to the order of operations is to create what is called a fully parenthesized expression. This type of expression uses one pair of parentheses for each operator. The parentheses dictate the order of operations; there is no ambiguity. There is also no need to remember any precedence rules.

The expression A + B * C + D can be rewritten as ((A + (B * C)) + D) to show that the multiplication happens first, followed by the leftmost addition. A + B + C + D can be written as (((A + B) + C) + D) since the addition operations associate from left to right.

There are two other very important expression formats that may not seem obvious to you at first. Consider the infix expression A + B. What would happen if we moved the operator before the two operands? The resulting expression would be + A B. Likewise, we could move the operator to the end. We would get A B +. These look a bit strange.

These changes to the position of the operator with respect to the operands create two new expression formats, prefix and postfix. Prefix expression notation requires that all operators precede the two operands that they work on. Postfix, on the other hand, requires that its operators come after the corresponding operands. A few more examples should help to make this a bit clearer (see Table 2).

A + B * C would be written as + A * B C in prefix. The multiplication operator comes immediately before the operands B and C, denoting that * has precedence over +. The addition operator then appears before the A and the result of the multiplication.

In postfix, the expression would be A B C * +. Again, the order of operations is preserved since the * appears immediately after the B and the C, denoting that * has precedence, with + coming after. Although the operators moved and now appear either before or after their respective operands, the order of the operands stayed exactly the same relative to one another.

Now consider the infix expression (A + B) * C. Recall that in this case, infix requires the parentheses to force the performance of the addition before the multiplication. However, when A + B was written in prefix, the addition operator was simply moved before the operands, + A B. The result of this operation becomes the first operand for the multiplication. The multiplication operator is moved in front of the entire expression, giving us * + A B C. Likewise, in postfix A B + forces the addition to happen first. The multiplication can be done to that result and the remaining operand C. The proper postfix expression is then A B + C *.

Consider these three expressions again (see Table 3). Something very important has happened. Where did the parentheses go? Why don’t we need them in prefix and postfix? The answer is that the operators are no longer ambiguous with respect to the operands that they work on. Only infix notation requires the additional symbols. The order of operations within prefix and postfix expressions is completely determined by the position of the operator and nothing else. In many ways, this makes infix the least desirable notation to use.

Table 4 shows some additional examples of infix expressions and the equivalent prefix and postfix expressions. Be sure that you understand how they are equivalent in terms of the order of the operations being performed.