中缀表达式转后缀表达式(Java代码实现)

 1 private static List parseToSuffixExpression(List expressionList) {
 2         //创建一个栈用于保存操作符
 3         Stack opStack = new Stack();
 4         //创建一个list用于保存后缀表达式
 5         List suffixList = new ArrayList();
 6         for(String item : expressionList){
 7             //得到数或操作符
 8             if(isOperator(item)){
 9                 //是操作符 判断操作符栈是否为空
10                 if(opStack.isEmpty() || "(".equals(opStack.peek()) || priority(item) > priority(opStack.peek())){
11                     //为空或者栈顶元素为左括号或者当前操作符大于栈顶操作符直接压栈
12                     opStack.push(item);
13                 }else {
14                     //否则将栈中元素出栈如队，直到遇到大于当前操作符或者遇到左括号时
15                     while (!opStack.isEmpty() && !"(".equals(opStack.peek())){
16                         if(priority(item)  priority(opStack.peek())){
17                             suffixList.add(opStack.pop());
18                         }
19                     }
20                     //当前操作符压栈
21                     opStack.push(item);
22                 }
23             }else if(isNumber(item)){
24                 //是数字则直接入队
25                 suffixList.add(item);
26             }else if("(".equals(item)){
27                 //是左括号，压栈
28                 opStack.push(item);
29             }else if(")".equals(item)){
30                 //是右括号 ，将栈中元素弹出入队，直到遇到左括号，左括号出栈，但不入队
31                 while (!opStack.isEmpty()){
32                     if("(".equals(opStack.peek())){
33                         opStack.pop();
34                         break;
35                     }else {
36                         suffixList.add(opStack.pop());
37                     }
38                 }
39             }else {
40                 throw new RuntimeException("有非法字符！");
41             }
42         }
43         //循环完毕，如果操作符栈中元素不为空，将栈中元素出栈入队
44         while (!opStack.isEmpty()){
45             suffixList.add(opStack.pop());
46         }
47         return suffixList;
48     }
49     /**
50      * 判断字符串是否为操作符
51      * @param op
52      * @return
53      */
54     public static boolean isOperator(String op){
55         return op.equals("+") || op.equals("-") || op.equals("*") || op.equals("/");
56     }
57 
58     /**
59      * 判断是否为数字
60      * @param num
61      * @return
62      */
63     public static boolean isNumber(String num){
64         return num.matches("\\d+");
65     }
66 
67     /**
68      * 获取操作符的优先级
69      * @param op
70      * @return
71      */
72     public static int priority(String op){
73         if(op.equals("*") || op.equals("/")){
74             return 1;
75         }else if(op.equals("+") || op.equals("-")){
76             return 0;
77         }
78         return -1;
79     }

 1 /**
 2      * 将表达式转为list
 3      * @param expression
 4      * @return
 5      */
 6     private static List expressionToList(String expression) {
 7         int index = 0;
 8         List list = new ArrayList();
 9         do{
10             char ch = expression.charAt(index);
11             if(ch  58){
12                 //是操作符，直接添加至list中
13                 index ++ ;
14                 list.add(ch+"");
15             }else if(ch >= 47 && ch ){
16                 //是数字,判断多位数的情况
17                 String str = "";
18                 while (index =47 && expression.charAt(index) ){
19                     str += expression.charAt(index);
20                     index ++;
21                 }
22                 list.add(str);
23             }
24         }while (index  expression.length());
25         return list;
26     }

1 public static void main(String []args){
2 
3         String expression = "1+((2+3)*4)-5";
4         List expressionList = expressionToList(expression);
5         System.out.println("expressionList="+expressionList);
6         //将中缀表达式转换为后缀表达式
7         List suffixList = parseToSuffixExpression(expressionList);
8         System.out.println(suffixList);
9 }

 1  /**
 2      * 根据后缀表达式list计算结果
 3      * @param list
 4      * @return
 5      */
 6     private static int calculate(List list) {
 7         Stack stack = new Stack();
 8         for(int i=0; i){
 9             String item = list.get(i);
10             if(item.matches("\\d+")){
11                 //是数字
12                 stack.push(Integer.parseInt(item));
13             }else {
14                 //是操作符，取出栈顶两个元素
15                 int num2 = stack.pop();
16                 int num1 = stack.pop();
17                 int res = 0;
18                 if(item.equals("+")){
19                     res = num1 + num2;
20                 }else if(item.equals("-")){
21                     res = num1 - num2;
22                 }else if(item.equals("*")){
23                     res = num1 * num2;
24                 }else if(item.equals("/")){
25                     res = num1 / num2;
26                 }else {
27                     throw new RuntimeException("运算符错误！");
28                 }
29                 stack.push(res);
30             }
31         }
32         return stack.pop();
33     }

 1 public static void main(String []args){
 2 
 3         String expression = "1+((2+3)*4)-5";
 4         List expressionList = expressionToList(expression);
 5         System.out.println("中缀表达式转为list结构="+expressionList);
 6         //将中缀表达式转换为后缀表达式
 7         List suffixList = parseToSuffixExpression(expressionList);
 8         System.out.println("对应的后缀表达式列表结构="+suffixList);
 9         //根据后缀表达式计算结果
10         int calculateResult = calculate(suffixList);
11         System.out.printf(expression+"=%d\n",calculateResult);
12 }