# 中序式轉後序式（前序式）

## 解法

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

## 演算法

``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++;     ]] ``

 OP STACK OUTPUT ( ( - a ( a + (+ a b (+ ab ) - ab+ * * ab+ ( *( ab+ c *( ab+c + *(+ ab+c d *(+ ab+cd ) * ab+cd+ - - ab+cd+*

• C
``#include <stdio.h> #include <stdlib.h> #define MAX 80void 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 : 0enddef 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.reverseenddef 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));``

``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 TruetoPrefix inf = toPfix inf Falsemain = do    let inf = "(a+b)*(c+d)"    putStrLn \$ toPostfix inf    putStrLn \$ toPrefix inf``