Algorithm Gossip: 後序式的運算

解法

實作：C    Java    Python    Scala    Ruby

• C

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

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

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

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

    return; 
} 

void eval(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

import java.util.*;

public class InFix {
    private static int priority(char op) {  
        switch(op) { 
           case '+': case '-': 
                return 1; 
            case '*': case '/': 
                return 2;
            default: 
                return 0;
        }  
    }
    
    private static String toPostfix(String expr) {
        LinkedList<Character> stack = new LinkedList<Character>();
        stack.add('\u0000'); 
        StringBuffer buffer = new StringBuffer();
        for(char c : expr.toCharArray()) { 
            switch(c) {  
                case '(': 
                    stack.add(c);
                    break; 
                case '+': case '-': case '*': case '/': 
                    while(priority(stack.getLast()) >= priority(c)) { 
                        buffer.append(stack.removeLast());
                    } 
                    stack.add(c);
                    break; 
                case ')': 
                    while(stack.getLast() != '(') { 
                        buffer.append(stack.removeLast());
                    } 
                    stack.removeLast();
                    break; 
                default: 
                    buffer.append(c);
            } 
        } 
        
        while(stack.getLast() != '\u0000') { 
            buffer.append(stack.removeLast());
        }
        
        return buffer.toString();
    }

    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(String expr) {
        LinkedList<Double> stack = new LinkedList<Double>();
        for(char c : toPostfix(expr).toCharArray()) { 
            switch(c) { 
                case '+': case '-': case '*': case '/': 
                    double p2 = stack.removeLast();
                    double p1 = stack.removeLast();
                    stack.add(cal(p1, c, p2));
                    break; 
                default:
                    stack.add(Double.parseDouble(String.valueOf(c)));
            } 
        } 
        return stack.getLast();
    }        
    
    public static void main(String[] args) {
        System.out.println(InFix.eval("(1+2)*(3+4)"));
    }
}

• Python

def priority(op):
    if op in ['+', '-']:
        return 1
    elif op in ['*', '/']:
        return 2
    else:
        return 0

def toPostfix(infix):
    stack = ['']
    buffer = []
    for c in infix:
        if c == '(':
            stack.append(c)
        elif c in "+-*/":
            while priority(stack[-1]) >= priority(c):
                buffer.append(stack.pop())
            stack.append(c)
        elif c == ')':
            while stack[-1] != '(':
                buffer.append(stack.pop())
            stack.pop()
        else:
            buffer.append(c)
    while stack[-1] != '':
        buffer.append(stack.pop())
    return buffer

def cal(p1, op, p2):
    result = {
      '+': lambda : p1 + p2,
      '-': lambda : p1 - p2,
      '*': lambda : p1 * p2,
      '/': lambda : p1 / p2
    }[op]()
    return result

def eval(infix):
    stack = []
    for c in toPostfix(infix):
        if c in ['+', '-', '*', '/']:
            p2 = stack.pop()
            p1 = stack.pop()
            stack.append(cal(p1, c, p2))
        else:
            stack.append(float(c))
    return stack[-1]

print(eval("(1+2)*(3+4)"))

• Scala

import scala.collection.mutable.ListBuffer

object InFix {
    private def priority(op: Char) = {
        op match {
            case '+'|'-' => 1
            case '*'|'/' => 2
            case _ => 0
        }
    }
    
    def toPostfix(expr: String) = {
        val stack = new ListBuffer[Char]
        stack + '\u0000'
        val buffer = new ListBuffer[Char]
        for(c <- expr) {
            c match {
                case '(' => 
                    stack + c
                case '+'|'-'|'*'|'/' =>
                    while(priority(stack.last) >= priority(c)) {
                        buffer + stack.last
                    }
                    stack + c
                case ')' =>
                    while(stack.last != '(') {
                        buffer + stack.remove(stack.length- 1)
                    }
                    stack.remove(stack.length - 1)
                case _ => buffer + c
            }
        }
        while(stack.last != '\u0000') {
            buffer + stack.remove(stack.length - 1)
        }
        buffer.mkString
    }

    private def cal(p1: Double, op: Char, p2: Double) = {
        op match {
            case '+' => p1 + p2
            case '-' => p1 - p2
            case '*' => p1 * p2
            case '/' => p1 / p2
            case _ => 0.0
        }
    }
    
    def eval(expr: String) = {
        val stack = new ListBuffer[Double]
        for(c <- toPostfix(expr)) {
            c match {
                case '+'|'-'|'*'|'/' =>
                    val p2 = stack.remove(stack.length - 1)
                    val p1 = stack.remove(stack.length - 1)
                    stack + cal(p1, c, p2)
                case _ =>
                    stack + c.toString.toDouble
            }
        }
        stack.last
    }
}

println(InFix.eval("(1+2)*(3+4)"))

• Ruby

def priority(op)
    case op
    when "+", "-"
        return 1
    when "*", "/"
        return 2
    else
        return 0
    end
end

def toPostfix(infix)
    stack = [""]
    buffer = []
    infix.each_char { |c|
        case c
        when "("
            stack << c
        when "+", "-", "*", "/"
            while priority(stack[-1]) >= priority(c)
                buffer << stack.pop
            end
            stack << c
        when ")"
            while stack[-1] != "("
                buffer << stack.pop
            end
            stack.pop
        else
            buffer << c
        end
    }
    while stack[-1] != ""
        buffer << stack.pop
    end
    buffer
end

def cal(p1, op, p2)
    case op
    when "+"
        return p1 + p2
    when "-" 
        return p1 - p2
    when "*"
        return p1 * p2
    when "/"
        return p1 / p2
    end
end

def eval(infix)
    stack = []
    toPostfix(infix).each { |c|
        if "+-*/".include?(c)
            p2 = stack.pop
            p1 = stack.pop
            stack << cal(p1, c, p2)
        else
            stack << c.to_f
        end
    }
    stack[-1]
end

puts eval("(1+2)*(3+4)")