1 package com.hicc.lc;
 2 
 3 import java.util.ArrayList;
 4 import java.util.HashMap;
 5 import java.util.List;
 6 import java.util.Map;
 7 import java.util.Stack;
 8 
 9 import com.hicc.lc.vo.Result;
10 
11 public class Generator {
12     // 获得运算符优先级
13     public static int getPriority(String operator) {
14         final int plusPriority = 2;
15         final int multiplyPriority = 3;
16         final int minusPriority = 4;
17         final int leftBracketPriority = 1;
18         if ("+".equals(operator))
19             return plusPriority;
20         if ("*".equals(operator))
21             return multiplyPriority;
22         if ("-".equals(operator))
23             return minusPriority;
24         if ("(".equals(operator))
25             return leftBracketPriority;
26         return 0;
27     }
28 
29     // 比较两运算符优先级
30     public static boolean priorThan(String operatorA, String operatorB) {
31         return getPriority(operatorA) > getPriority(operatorB);
32     }
33 
34     public static void main(String args[]) {
35         String expression = "(a+b+c)*d*-e+f*g";
36 //        String expression = "(A+B)*(C+D)+E";
37         Map<Integer, String> retrivalWords = new HashMap<Integer, String>();// 检索词表存储区
38         Stack<String> operatorList = new Stack<String>();// 算子保留栈
39         List<Result> result = new ArrayList<Result>();// 结果保留栈
40         expression = expression.concat(".");
41         int letterNum = 0;
42         for (int i = 0; i < expression.length(); i++) {
43             String s = String.valueOf(expression.charAt(i));
44             if (s.matches("[a-zA-Z]")) {
45                 letterNum = letterNum + 1;
46             } else {
47                 if (letterNum > 0) {
48                     String retrivalWord = expression
49                             .substring(i - letterNum, i);
50                     retrivalWords.put(retrivalWords.size() + 1, retrivalWord);
51                     result.add(new Result(0, retrivalWord));
52                     letterNum = 0;
53                 }
54                 if ("(".equals(s)) {
55                     operatorList.push("(");
56                 }
57                 if ("+*-".contains(s)) {
58                     while ((!operatorList.isEmpty())
59                             && (!priorThan(s, operatorList.peek()))) {
60                         result.add(new Result(1, operatorList.pop()));
61                     }
62 //                    if((!operatorList.isEmpty())
63 //                            && !s.equals(operatorList.peek()))
64                         operatorList.push(s);
65                 }
66                 if (")".equals(s)) {
67                     while (!operatorList.peek().equals("(")) {
68                         result.add(new Result(1, operatorList.pop()));
69                     }
70                     operatorList.pop();
71                 }
72                 if (".".equals(s)) {
73                     while (!operatorList.isEmpty()) {
74                         result.add(new Result(1, operatorList.pop()));
75                     }
76                     result.add(new Result(1, "."));
77                 }
78 
79             }
80         }
81         System.out.print("输出逆波兰表达式:");
82         for (int j = 0; j < result.size(); j++) {
83             System.out.print(result.get(j).getContent());
84         }
85         System.out.println();
86     }
87 }

package com.hicc.lc.vo;

public class Result {
    private int charactor;
    private String content;

    public Result(int charactor, String content) {
        this.charactor = charactor;
        this.content = content;
    }

    public int getCharactor() {
        return charactor;
    }

    public String getContent() {
        return content;
    }

    public void setCharactor(int charactor) {
        this.charactor = charactor;
    }

    public void setContent(String content) {
        this.content = content;
    }
}