From Gossip@caterpillar

Algorithm Gossip: 後序式的運算

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

解法

運算時由後序式的前方開始讀取，遇到運算元先存入堆疊，如果遇到運算子，則由堆疊中取出兩個運算元進行對應的運算，然後將結果存回堆疊，如果運算式讀取完畢，那麼堆疊頂的值就是答案了，例如我們計算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 後存回

實作

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

void evalPf(char*); 
double cal(double, char, double); 

int main(void) { 
    char input[80]; 

    printf("輸入後序式："); 
    scanf("%s", input); 
    evalPf(input); 

    return; 
} 

void evalPf(char* postfix) { 
    double stack[80] = {0.0}; 
    char temp[2]; 
    char token; 
    int top = 0, i = 0; 

    temp[1] = '\0'; 

    while(1) { 
        token = postfix[i]; 
        switch(token) { 
            case '\0': 
                printf("ans = %f\n", stack[top]); 
                return; 
            case '+': case '-': case '*': case '/': 
                stack[top-1] = 
                       cal(stack[top-1], token, stack[top]); 
                top--; 
                break; 
            default: 
                if(top < sizeof(stack) / sizeof(float)) { 
                    temp[0] = postfix[i]; 
                    top++; 
                    stack[top] = atof(temp); 
                } 
                break; 
        } 
        i++; 
    } 
} 

double cal(double p1, char op, double p2) { 
    switch(op) { 
        case '+': 
            return p1 + p2; 
        case '-': 
            return p1 - p2; 
        case '*': 
            return p1 * p2; 
        case '/': 
            return p1 / p2; 
    } 
}

Java

public class InFix {
    private static int priority(char op) {  
        switch(op) { 
           case '+': case '-': 
                return 1; 
            case '*': case '/': 
                return 2;
            default: 
                return 0;
        }  
    }
    
    public static char[] toPosfix(char[] infix) {
        char[] stack = new char[infix.length]; 
        char[] postfix = new char[infix.length];
        char op; 

        StringBuffer buffer = new StringBuffer();

        int top = 0;
        for(int i = 0; i < infix.length; i++) { 
            op = infix[i]; 
            switch(op) {  
                // 運算子堆疊 
                case '(': 
                    if(top < stack.length) { 
                        top++; 
                        stack[top] = op; 
                    } 
                    break; 
                case '+': case '-': case '*': case '/': 
                    while(priority(stack[top]) >= 
                          priority(op)) { 
                        buffer.append(stack[top]);
                        top--; 
                    } 
                    // 存入堆疊 
                    if(top < stack.length) { 
                        top++; 
                        stack[top] = op; 
                    } 
                    break; 
                // 遇 ) 輸出至 ( 
                case ')': 
                    while(stack[top] != '(') { 
                        buffer.append(stack[top]);
                        top--; 
                    } 
                    top--;  // 不輸出( 
                    break; 
                // 運算元直接輸出 
                default: 
                    buffer.append(op);
                    break; 
            } 
        } 
        
        while(top > 0) { 
            buffer.append(stack[top]);
            top--; 
        }
        
        return buffer.toString().toCharArray();
    }

    private static double cal(double p1, char op, double p2) { 
        switch(op) { 
            case '+': 
                return p1 + p2; 
            case '-': 
                return p1 - p2; 
            case '*': 
                return p1 * p2; 
            case '/': 
                return p1 / p2; 
        }
        return 0.0;
    }
    
    public static double eval(char[] postfix) {
        double[] stack = new double[postfix.length]; 
        char token; 
        int top = 0; 

        for(int i = 0; i < postfix.length; i++) { 
            token = postfix[i]; 
            switch(token) { 
                case '+': case '-': case '*': case '/': 
                    stack[top-1] = 
                       cal(stack[top-1], token, stack[top]); 
                    top--; 
                    break; 
                default: 
                    if(top < stack.length) { 
                        char temp = postfix[i]; 
                        top++; 
                        stack[top] = 
                            Double.parseDouble(
                                    String.valueOf(temp)); 
                    } 
                    break; 
            } 
        } 

        return stack[top];
    }
    
    public static void main(String[] args) {
        String infix = "(1+2)*(3+4)";
        
        System.out.println(InFix.eval(
                InFix.toPosfix(infix.toCharArray())));
    }
}