中序式轉後序式(前序式)


說明

平常所使用的運算式,主要是將運算元放在運算子的兩旁,例如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/+

另一個方式是使用堆疊法進行中序轉後序,演算法直接敘述的話就是使用迴圈,取出中序式的字元,遇運算元直接輸出;堆疊運算子與左括號; 堆疊中運算子優先順序若大於等於讀入的運算子優先順序的話,直接輸出堆疊中的運算子,再將讀入的運算子置入堆疊;遇右括號輸出堆疊中的運算子至左括號。

演算法

以下是虛擬碼的運算法,\0表示中序式讀取完畢:
Procedure Postfix(infix) [
Loop [
op = infix(i)
case [
:x = '\0':
while (stack not empty)
// output all elements in stack
end
return
:x = '(':
// put it into stack
:x is operator:
while (priority(stack[top]) >=
priority(op)) [
// out a element from stack
]
// save op into stack
:x = ')':
while ( stack(top) != '(' ) [
// out a element from stack
]
top = top - 1 // not out '(
:else:
// output current op
]
i++;
]
]

例如(a+b)*(c+d)這個式子,依演算法的輸出過程如下:
OP STACK OUTPUT
( ( -
a ( a
+ (+ a
b (+ ab
) - ab+
* * ab+
( *( ab+
c *( ab+c
+ *(+ ab+c
d *(+ ab+cd
) * ab+cd+
- - ab+cd+*

如果要使用堆疊法將中序式轉為前序式,則使用迴圈由後往前取出中序式的字元,遇運算元直接輸出;堆疊運算子與右括號; 堆疊中運算子優先順序若大於讀入的運算子優先順序的話,直接輸出堆疊中的運算子,再將讀入的運算子置入堆疊;遇左括號輸出堆疊中的運算子至右括號。前面整個演算過程中被輸出的字元再反序列出,就是前序表示式。

實作:C    Java    Python    Scala    Ruby    JavaScript    Haskell

  • C
#include <stdio.h> 
#include <stdlib.h>

#define MAX 80

void inToPostfix(char*, char*); // 中序轉後序
int priority(char); // 運算子優先權

int main(void) {
char infix[MAX] = {'\0'};
char postfix[MAX]= {'\0'};

printf("中序運算式:");
scanf("%s", infix);
inToPostfix(infix, postfix);

int i;
for(i = 0; postfix[i] != '\0'; i++) {
printf("%c", postfix[i]);
}

return 0;
}

void inToPostfix(char* infix, char* postfix) {
char stack[MAX] = {'\0'};
int i, j, top;
for(i = 0, j = 0, top = 0; infix[i] != '\0'; i++) switch(infix[i]) {
case '(': // 運算子堆疊
stack[++top] = infix[i];
break;
case '+': case '-': case '*': case '/':
while(priority(stack[top]) >= priority(infix[i])) {
postfix[j++] = stack[top--];
}
stack[++top] = infix[i]; // 存入堆疊
break;
case ')':
while(stack[top] != '(') { // 遇 ) 輸出至 (
postfix[j++] = stack[top--];
}
top--; // 不輸出 (
break;
default: // 運算元直接輸出
postfix[j++] = infix[i];
}
while(top > 0) {
postfix[j++] = stack[top--];
}
}

int priority(char op) {
switch(op) {
case '+': case '-': return 1;
case '*': case '/': return 2;
default: return 0;
}
}

  • Java
import java.util.*;
import static java.lang.System.out;

public class Infix {
private static int priority(char c) {
return c == '+' || c == '-' ? 1 : c == '*' || c == '/' ? 2 : 0;
}

private static String toPostfix(String infix, boolean isPost) {
String expr = isPost ?
infix : new StringBuffer(infix).reverse().toString();
LinkedList<Character> stack = new LinkedList<>();
StringBuilder output = new StringBuilder();
char toStack = isPost ? '(' : ')';
char toOutput = isPost ? ')' : '(';
for(char c : expr.toCharArray()) {
if(c == toStack) { stack.add(c); }
else if("+-*/".indexOf(c) != -1) {
while(!stack.isEmpty() &&
priority(stack.getLast()) >= priority(c)) {
output.append(stack.removeLast());
}
stack.add(c);
}
else if(c == toOutput) {
while(stack.getLast() != toStack) {
output.append(stack.removeLast());
}
stack.removeLast();
}
else { output.append(c); }
}

while(!stack.isEmpty()) { output.append(stack.removeLast()); }

return isPost ? output.toString() : output.reverse().toString();
}

public static String toPostfix(String infix) {
return toPostfix(infix, true);
}

public static String toPrefix(String infix) {
return toPostfix(infix, false);
}

public static void main(String[] args) {
String infix = "(a+b)*(c+d)";
out.println(toPostfix(infix));
out.println(toPrefix(infix));
}
}

  • Python
def priority(op):
return 1 if op in "+-" else 2 if op in "*/" else 0

def toPostfix(infix, isPost = True):
toStack, toOutput = ('(', ')') if isPost else (')', '(')

def procOpt(c, stack, output):
if stack == "" or priority(stack[-1]) < priority(c):
return (stack + c, output)
else:
return procOpt(c, stack[0:-1], output + stack[-1])

def procPhs(stack, output):
if stack[-1] == toStack:
return (stack[0:-1], output)
else:
return procPhs(stack[0:-1], output + stack[-1])

def procExpr(expr, stack = "", output = ""):
if expr == "":
return output + stack[::-1]
elif expr[0] == toStack:
return procExpr(expr[1:], stack + expr[0], output)
elif expr[0] in "+-*/":
return procExpr(expr[1:], *procOpt(expr[0], stack, output))
elif expr[0] == toOutput:
return procExpr(expr[1:], *procPhs(stack, output))
else:
return procExpr(expr[1:], stack, output + expr[0])

output = procExpr(infix if isPost else infix[::-1])
return output if isPost else output[::-1]

def toPrefix(infix):
return toPostfix(infix, False)

infix = "(a+b)*(c+d)"
print(toPostfix(infix))
print(toPrefix(infix))

  • Scala
def priority(op: Char) = op match {
case '+' | '-' => 1
case '*' | '/' => 2
case _ => 0
}

def toPostfix(infix: String, isPost: Boolean = true) = {
val (toStack, toOutput) = if(isPost) ('(', ')') else (')', '(')

def procOpt(c: Char, stack: String, output: String): (String, String) = {
if(stack == "" || priority(stack.last) < priority(c)) {
(stack + c, output)
} else procOpt(c, stack.init, output + stack.last)
}

def procPhs(stack: String, output: String): (String, String) = {
if(stack.last == toStack) (stack.init, output)
else procPhs(stack.init, output + stack.last)
}

def procExpr(expr: String, so: (String, String) = ("", "")): String = {
val (stack, output) = so
if(expr == "") {
output + stack.reverse
} else if(expr.head == toStack) {
procExpr(expr.tail, (stack + expr.head, output))
} else if("+-*/".contains(expr.head)) {
procExpr(expr.tail, procOpt(expr.head, stack, output))
} else if(expr.head == toOutput) {
procExpr(expr.tail, procPhs(stack, output))
} else procExpr(expr.tail, (stack, output + expr.head))
}

val output = procExpr(if(isPost) infix else infix.reverse)
if(isPost) output else output.reverse
}

def toPrefix(infix: String) = toPostfix(infix, false)

val infix = "(a+b)*(c+d)"
println(toPostfix(infix))
println(toPrefix(infix))

  • Ruby
def priority(op)
"+-".include?(op) ? 1 : "*/".include?(op) ? 2 : 0
end

def toPostfix(infix, isPost = true)
toStack, toOutput = isPost ? ['(', ')'] : [')', '(']

procOpt = ->(c, stack, output) {
if stack == "" || priority(stack[-1]) < priority(c)
[stack + c, output]
else
procOpt.call(c, stack[0...-1], output + stack[-1])
end
}

procPhs = ->(stack, output) {
if stack[-1] == toStack
[stack[0...-1], output]
else
procPhs.call(stack[0...-1], output + stack[-1])
end
}

procExpr = ->(expr, stack = "", output = "") {
if expr == ""
output + stack.reverse
elsif expr[0] == toStack
procExpr.call(expr[1..-1], stack + expr[0], output)
elsif "+-*/".include? expr[0]
procExpr.call(expr[1..-1], *procOpt.call(expr[0], stack, output))
elsif expr[0] == toOutput
procExpr.call(expr[1..-1], *procPhs.call(stack, output))
else
procExpr.call(expr[1..-1], stack, output + expr[0])
end
}

output = procExpr.call(isPost ? infix : infix.reverse)
isPost ? output : output.reverse
end

def toPrefix(infix)
toPostfix(infix, false)
end

infix = "(a+b)*(c+d)"
puts(toPostfix(infix))
puts(toPrefix(infix))

  • JavaScript
Array.prototype.getLast = function() {
return this[this.length - 1];
};

Array.prototype.isEmpty = function() {
return this.length == 0;
};

function priority(c) {
return c === '+' || c === '-' ? 1 : c === '*' || c === '/' ? 2 : 0;
}

function toPostfix(infix, isPost) {
isPost = isPost === undefined ? true : false;
var expr = isPost ? infix.split('') : infix.split('').reverse();
var stack = [];
var output = [];
var toStack = isPost ? '(' : ')';
var toOutput = isPost ? ')' : '(';
expr.forEach(function(c) {
if(c === toStack) { stack.push(c); }
else if('+-*/'.indexOf(c) !== -1) {
while(!stack.isEmpty() &&
priority(stack.getLast()) >= priority(c)) {
output.push(stack.pop());
}
stack.push(c);
}
else if(c === toOutput) {
while(stack.getLast() !== toStack) {
output.push(stack.pop());
}
stack.pop();
}
else { output.push(c); }
});

while(!stack.isEmpty()) { output.push(stack.pop()); }

return isPost ? output.join('') : output.reverse().join('');
}

function toPrefix(infix) {
return toPostfix(infix, false);
}

var infix = "(a+b)*(c+d)";
print(toPostfix(infix));
print(toPrefix(infix));

  • Haskell
priority op = if op `elem` "+-" then 1
else if op `elem` "*/" then 2
else 0

toPfix inf isPost = if isPost then output else reverse output
where
(toStack, toOutput) = if isPost then ('(', ')') else (')', '(')
output = procExpr (if isPost then inf else reverse inf) ("", "")
procOpt c stack output =
if stack == "" || (priority $ last stack) < priority c
then (stack ++ [c], output)
else procOpt c (init stack) (output ++ [last stack])
procPhs stack output =
if last stack == toStack then (init stack, output)
else procPhs (init stack) (output ++ [last stack])
procExpr expr so =
if expr == ""
then output ++ (reverse stack)
else if head == toStack
then procExpr tail (stack ++ [head], output)
else if head `elem` "+-*/"
then procExpr tail $ procOpt head stack output
else if head == toOutput
then procExpr tail $ procPhs stack output
else procExpr tail (stack, output ++ [head])
where (stack, output) = so
head:tail = expr

toPostfix inf = toPfix inf True
toPrefix inf = toPfix inf False

main = do
let inf = "(a+b)*(c+d)"
putStrLn $ toPostfix inf
putStrLn $ toPrefix inf