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 後存回

實作: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)")