後序式運算

將中序式轉換為後序式，運算先後順序問題就處理完畢了，只要依序由運算式由前往後讀取，遇到運算子取出需要的運算元，就能進行運算。

解法思路

運算時由後序式的前方開始讀取，遇到運算元先存入堆疊，如果遇到運算子，從堆疊取出兩個運算元進行對應運算，然後將結果存回堆疊，運算式讀取完畢時，堆疊頂端的值就是答案，例如計算後序式 1 2 + 3 4 + * （也就是中序式 (1 + 2) * (3 + 4)）：

讀取	堆疊
1	1
2	1 2（1 + 2 後存回）
+	3
3	3 3
4	3 3 4
+	3 7（3 + 4 後存回）
*	2 1（3 * 7 後存回）

若為運算式的運算子、運算元定義不同型態的節點，中序式轉後序式，之後讀取後序式，遇到運算子取出需要的運算元，建立對應型態的節點，並以樹狀結構設定節點間的關係，就是棵簡單的語法樹了。

程式實作

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

#define MAX 80

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

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

    printf("運算式："); 
    scanf("%s", infix); 
    printf("%f", eval(infix));
    
    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;
    } 
} 

double eval(char* infix) {
    char postfix[MAX]= {'\0'};
    char opnd[2] = {'\0'};
    double stack[MAX] = {0.0}; 
    
    inToPostfix(infix, postfix);    

    int top, i;
    for(top = 0, i = 0; postfix[i] != '\0'; i++) switch(postfix[i]) { 
        case '+': case '-': case '*': case '/': 
            stack[top - 1] = cal(postfix[i], stack[top - 1], stack[top]); 
            top--; 
            break; 
        default: 
            opnd[0] = postfix[i];
            stack[++top] = atof(opnd);
    }             
    
    return stack[top];
}

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

// 使用中序式轉後序式中的 Infix
import java.util.*;

public class Calculator {
    private static double cal(char op, double p1, double p2) {
        switch(op) { 
            case '+': return p1 + p2; 
            case '-': return p1 - p2; 
            case '*': return p1 * p2; 
            case '/': return p1 / p2;
            default:  throw new ArithmeticException(op + " not defined");
        }
    }
    
    public static double eval(String expr) {
        LinkedList<Double> stack = new LinkedList<>();
        for(char c : Infix.toPostfix(expr).toCharArray()) {
            if("+-*/".indexOf(c) != -1) {
                double p2 = stack.removeLast();
                double p1 = stack.removeLast();
                stack.add(cal(c, p1, p2));
            } else { stack.add(Double.parseDouble(String.valueOf(c))); } 
        }
        return stack.getLast();
    }        
    
    public static void main(String[] args) {
        System.out.println(eval(args[0]));
    }
}

# 使用中序式轉後序式中的 toPostfix
from sys import argv
from functools import reduce

def eval(expr):
    def doStack(stack, c):
        if c in "+-*/":
            return stack[0:-2] + [
                {'+': float.__add__,
                 '-': float.__sub__,
                 '*': float.__mul__,
                 '/': float.__floordiv__}[c](stack[-2], stack[-1])]
        else:
            return stack + [float(c)]
            
    return reduce(doStack, toPostfix(expr), [])[-1]

print(eval(argv[1]))

// 使用 中序式轉後序式 中的 toPostfix
def eval(expr: String) = {
    ((Nil:List[Double]) /: Infix.toPostfix(expr)) {
        (stack, c) => {
            if("+-*/".contains(c)) {
                val op1 = stack.tail.head
                val op2 = stack.head
                (c match {
                    case '+' => op1 + op2
                    case '-' => op1 - op2
                    case '*' => op1 * op2
                    case '/' => op1 / op2
                }) :: stack.tail.tail
            } else c.toString.toDouble :: stack
        }
    }.head
}

println(eval(args(0)))

# 使用中序式轉後序式中的 toPostfix

def eval(expr)
    toPostfix(expr).split("").reduce([]) { |stack, c|
        if "+-*/".include? c
            stack[0...-2] + [stack[-2].send(c, stack[-1])]
        else
            stack + [c.to_f]
        end
    } [-1]
end

print(eval(ARGV[0]))

// 使用中序式轉後序式中的 toPostfix
function evaluate(expr) {
    var stack = [];
    toPostfix(expr).split('').forEach(function(c) {
        if('+-*/'.indexOf(c) !== -1) {
            var p2 = stack.pop();
            var p1 = stack.pop();
            stack.push(cal(c, p1, p2));
        } else {
            stack.push(parseInt(c));
        }
    });
    return stack.pop();
}

print(evaluate('(1+2)*(3+4)'));

import System.IO

{- 使用中序式轉後序式中的 toPostfix -}

eval expr = 
    let postfix = toPostfix expr
    in head . foldl stacker [] $ postfix
    where stacker (x:y:ys) '*' = (y * x):ys  
          stacker (x:y:ys) '+' = (y + x):ys  
          stacker (x:y:ys) '-' = (y - x):ys  
          stacker (x:y:ys) '/' = (y / x):ys  
          stacker xs numberToken = (read [numberToken]):xs

main = do
    expr <- getLine
    print $ eval expr