後序式的運算

解法

實作：C    Java    Python    Scala    Ruby    JavaScript    Haskell

• C

#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; 
    } 
}

• Java

// 使用 中序式轉後序式 中的 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]));
    }
}

• Python

# 使用 中序式轉後序式 中的 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]))

• Scala

// 使用 中序式轉後序式 中的 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)))

• Ruby

# 使用 中序式轉後序式 中的 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]))

• JavaScript
  

// 使用 中序式轉後序式 中的 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)'));

• Haskell

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

import qualified Data.Map as Map
import System(getArgs)

eval expr = last $ foldl doStack [] (toPostfix expr)
    where
        chr2flt c = fromInteger $ read [c]
        doStack stack c =
            if c `elem` "+-*/" then
                let opts = Map.fromList [('+', (+)), ('-', (-)), 
                                         ('*', (*)), ('/', (/))]
                    (Just opt) = Map.lookup c opts
                in ((head $ tail stack) `opt` (head stack)) : 
                   (tail $ tail stack)
            else (chr2flt c) : stack
            
main = do
    args <- getArgs
    print $ eval $ args !! 0