练手系列(3) 中缀表达式转后缀表达式详解编程语言

  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 }