中序式轉後序式

人們平常使用的運算式，是將運算元放在運算子兩旁，例如 a + b / d 這樣的式子，這稱為中序（infix）表示式；然而電腦剖析運算式時，為了有效率地判斷運算的順序，可將中序表示式轉換為後序（postfix）或前序（prefix）表示式。

解法思路

後序表示式又稱為逆向波蘭表示式（reverse polish notation），是由波蘭的數學家盧卡謝維奇提出，例如 (a + b) * (c + d)，表示為後序表示式時是 a b + c d + *。

想以人工轉換計算後序式的話，可以使用括號法，將運算子兩旁的運算元，依先後順序全部括號起來，然後將右括號取代為左邊最接近的運算子（從最內層括號開始），最後去掉全部的左括號就可以完成。例如：

a + b * d + c / d
((a + (b * d)) + (c / d))
a b d * + c d / +

另一個方式是堆疊法，使用迴圈取出中序式的元素，遇運算元直接輸出，遇到運算子與左括號進行堆疊，堆疊中運算子優先順序若大於等於讀入的運算子優先順序，直接輸出堆疊中的運算子，再將讀入的運算子置入堆疊；遇右括號輸出堆疊中的運算子至左括號。

以下是虛擬碼的運算法，\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)，依演算法的輸出過程如下：

元素	堆疊	輸出
(	(	-
a	(	a
+	(+	a
b	(+	ab
)	-	ab+
*	*	ab+
(	*(	ab+
c	*(	ab+c
+	*(+	ab+c
d	*(+	ab+cd
)	*	ab+cd+
-	-	ab+cd+*

若要用堆疊法將中序式轉為前序式，使用迴圈由後往前取出中序式的字元，遇運算元直接輸出；遇運算子與右括號進行堆疊；堆疊中運算子優先順序若大於讀入的運算子優先順序，直接輸出堆疊中的運算子，再將讀入的運算子置入堆疊；遇左括號輸出堆疊中的運算子至右括號。

程式實作

#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