练手系列(3) 中缀表达式转后缀表达式

　　最近在看数据结构和算法时，看到了中缀表达式和后缀表达式，感觉蛮有意思的，于是自己实现了一下，算是一种锻炼。

①首先，中缀表达式就是我们平时见惯了的算术式，比如：5+3这样的就是中缀表达式，而后缀表达式呢，就是53+这样的。因为转为后缀表达式后，算术式的计算会相对简单一些，可以用栈来实现。

分析图如下：

这种后缀表达式计算的最大的优点就是不用知道什么优先级。

②好，下面我们来看一下怎么从中缀表达式（5+3）变为后缀表达式（53+）：

好了，以上两张图片就是后缀表达式的相关分析。

下面上具体代码：

  1 import java.util.Stack;
  2 
  3 public class Calculate {
  4     // 定义操作符号
  5     private static final char PLUS = '+';
  6     private static final char MINUS = '-';
  7     private static final char MULTIPLY = '*';
  8     private static final char DIVIDE = '/';
  9     private static final char LEFT_PARENTHESIS = '(';
 10     private static final char RIGHT_PARENTHESIS = ')';
 11 
 12     public static void main(String[] args) {
 13         String infix = "(3+(2-1))*5";
 14         String postfix = convert(infix);
 15         System.out.println(postfix);
 16         analysePostfix(postfix);
 17     }
 18 
 19     // 计算后缀表达式
 20     public static void analysePostfix(String postfix) {
 21         Stack<Double> stack = new Stack<Double>();
 22         char[] chs = postfix.toCharArray();
 23         for (int i = 0; i < chs.length; i++) {
 24             if (chs[i] != PLUS && chs[i] != MINUS && chs[i] != MULTIPLY
 25                     && chs[i] != DIVIDE) {
 26                 // 如果读取到的是数字，则加到栈中
 27                 stack.push(Double.valueOf(String.valueOf(chs[i])));
 28             } else {
 29                 // 如果读取到的是操作符，则从栈中弹出两个数字，并执行运算
 30                 double b = (double) stack.pop();
 31                 double a = (double) stack.pop();
 32                 char operator = chs[i];
 33                 double result = calculate(a, b, operator);
 34                 stack.push(result);
 35             }
 36         }
 37         System.out.println("result is : " + stack.pop());
 38     }
 39 
 40     public static double calculate(double a, double b, char operator) {
 41         switch (operator) {
 42         case PLUS:
 43             return a + b;
 44         case MINUS:
 45             return a - b;
 46         case MULTIPLY:
 47             return a * b;
 48         case DIVIDE:
 49             return a / b;
 50         }
 51         return 0;
 52     }
 53 
 54     // 中缀到后缀的转换
 55     public static String convert(String infix) {
 56         Stack<Character> vector = new Stack<Character>();
 57         char[] chs = infix.toCharArray();
 58         StringBuffer postfix = new StringBuffer();
 59         for (int i = 0; i < chs.length; i++) {
 60             // 如果是数字，直接插入表达式中
 61             if (chs[i] != PLUS && chs[i] != MINUS && chs[i] != MULTIPLY
 62                     && chs[i] != DIVIDE && chs[i] != LEFT_PARENTHESIS
 63                     && chs[i] != RIGHT_PARENTHESIS) {
 64                 postfix.append(String.valueOf(chs[i]));
 65             } else {
 66                 // 如果是左括号，直接压入栈中
 67                 if (LEFT_PARENTHESIS == chs[i]) {
 68                     vector.push(chs[i]);
 69                     continue;
 70                 }
 71                 // 如果是右括號，則去除棧裏面的左括號之上的所有操作符號
 72                 if (RIGHT_PARENTHESIS == chs[i]) {
 73                     while (LEFT_PARENTHESIS != vector.peek()) {
 74                         postfix.append(vector.pop());
 75                     }
 76                     vector.pop();
 77                 }
 78                 // 如果当前读到的操作符和栈里面的操作符一样，那么直接加到后缀表达式中
 79                 if (vector.size() > 0 && chs[i] == vector.peek()) {
 80                     postfix.append(String.valueOf(chs[i]));
 81                 } else if (vector.size() == 0 || chs[i] != vector.peek()) {
 82                     // 如果是乘号或者除号，直接压入栈中
 83                     if (MULTIPLY == chs[i] || DIVIDE == chs[i]) {
 84                         vector.push(chs[i]);
 85                     }
 86                     if (PLUS == chs[i] || MINUS == chs[i]) {
 87                         if (vector.size() > 0
 88                                 && (vector.peek() == MULTIPLY || vector.peek() == DIVIDE)) {
 89                             postfix.append(vector.pop().toString());
 90                             vector.push(chs[i]);
 91                         } else {
 92                             vector.push(chs[i]);
 93                         }
 94                     }
 95                 }
 96             }
 97             // 如果已经读完了中缀表达式，则弹出栈中所有操作符并加入到后缀表达式中
 98             if (i == chs.length - 1) {
 99                 for (int j = vector.size(); j > 0; j--) {
100                     postfix.append(vector.pop().toString());
101                 }
102             }
103         }
104         return postfix.toString();
105     }
106 }