Java 中序轉後序 中序轉前序 演算法

最近別實驗室的學弟要寫一個計算機，但是他沒想到方法
我推薦他用中序轉後序的方式去處理，不過他似乎不太瞭解
所以我就直接幫他分析一下程式碼

這次程式碼是由良葛格的『中序式轉後序式（前序式）』及『 後序式的運算』複製過來的XD

分別由『Calculator』及『Infix』所組成的，Infix類別是在做『中序轉前序』或『中序轉後序』
Calculator則是提供輸入四則運算以及運算的類別

觀念部份，改天補上

import java.util.*;
import static java.lang.System.out;

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 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("5+0*8/8"));
 }
}

import java.util.*;

public class Infix {
 // 優先順序 +- = 1, */ = 2, other = 0
 private static int priority(char c) {
  return c == '+' || c == '-' ? 1 : c == '*' || c == '/' ? 2 : 0;
 }

 private static String toPostfix(String infix, boolean isPost) {

  // 如果為後序就不用反轉，前序則需要反轉
  String expr = isPost ? infix : new StringBuffer(infix).reverse()
    .toString();

  // 字元
  LinkedList stack = new LinkedList();
  StringBuilder output = new StringBuilder();
  // 是則為( 不是則為)
  char toStack = isPost ? '(' : ')';

  // 是則為) 不是則為(
  char toOutput = isPost ? ')' : '(';

  for (char c : expr.toCharArray()) {
   if (c == toStack) { // 加入 ( 或 )
    stack.add(c);
   } else if ("+-*/".indexOf(c) != -1) { // 加入運算符號
    // 堆疊不為空，且優先權沒有大於，則移除並加入到output
    while (!stack.isEmpty()
      && priority(stack.getLast()) >= priority(c)) {
     output.append(stack.removeLast());
    }
    // 加入運算符號
    stack.add(c);
   } else if (c == toOutput) { // 加入 ) 或 (
    // 不 等於( 或 ) 則加入output
    while (stack.getLast() != toStack) {
     output.append(stack.removeLast());
    }
    stack.removeLast();
   } else {
    // 加入數字
    output.append(c);
   }
  }

  // 堆疊不為空，不斷回傳最後一個值並且刪除
  while (!stack.isEmpty()) {
   output.append(stack.removeLast());
  }

  // 如果是後序則回傳結果文字，否則傳回反轉文字
  return isPost ? output.toString() : output.reverse().toString();
 }

 // 後序
 public static String toPostfix(String infix) {
  return toPostfix(infix, true);
 }

 // 前序
 public static String toPrefix(String infix) {
  return toPostfix(infix, false);
 }

}

參考資料：
中序式轉後序式（前序式）
後序式的運算