說明
平常所使用的運算式，主要是將運算元放在運算子的兩旁，例如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
#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;
}
}
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));
}
}
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))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))
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))
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));
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