波兰表达式

代码实现

  1. import java.util.ArrayList;
  2. import java.util.List;
  3. import java.util.Stack;
  5. /**
  6.  * @author laoduan
  7.  * @create 2020-04-17-16:42
  8.  */
  9. public class PolandNotation {
  11.     public static void main(String[] args) {
  14. //        String suffixExpression = "30 4 + 5 * 6 -";
  15. //        String suffixExpression = "4 5 * 8 - 60 + 8 2 / +";
  16. //        List<String> rpnList = getListString(suffixExpression);
  17. //        System.out.println("rpnList="+rpnList);
  18. //
  19. //        int res = calulate(rpnList);
  20. //        System.out.println("计算的结果是"+res);
  21. //
  22. //
  24.         String expression = "1+((2+3)*4)-5";
  25.         List<String>infixExpressionList = toinfixExpressionList(expression);
  26.         System.out.println(infixExpressionList);
  28.         List<String> parseSuffixExpressionList = parseSuffixExpressionList(infixExpressionList);
  29.         System.out.println("后缀表达式对应的List"+parseSuffixExpressionList);
  31.         System.out.printf("expression=%d",calulate(parseSuffixExpressionList));
  33.     }
  37.     //方法:将得到的中缀表达式对应的List=》后缀表达式对应的List
  38.     public static List<String> parseSuffixExpressionList(List<String> ls){
  39.         //定义两个栈
  40.         Stack<String>s1 = new Stack<String>();//符号栈
  41.         //s2在整个转换过程中没有pop操作
  42.         //所以直接用List
  43.         List<String> s2 = new ArrayList<String>();
  45.         //遍历ls
  46.         for(String item:ls){
  47.             //如果是一个数，入s2
  48.             if(item.matches("\\d+")){
  49.                 s2.add(item);
  50.             }
  51.             else if(item.equals("(")){
  52.                 s1.push(item);
  53.             }
  54.             else if(item.equals(")")){
  55.                 //如果是)，就一直弹出，直到(
  56.                 while (!s1.peek().equals("(")){
  57.                     s2.add(s1.pop());
  58.                 }
  59.                 s1.pop();//将(弹出s1       消除（）
  60.             }else {
  61.                 //当item的优先级小于等于s1栈顶运算符,将s1栈顶的运算符弹出并加入s2
  62.                 while (s1.size()!=0&&Operation.getValue(s1.peek())>=Operation.getValue(item)){
  63.                     s2.add(s1.pop());
  64.                 }
  65.                 //将item压入栈中
  66.                 s1.push(item);
  67.             }
  68.         }
  69.         while (s1.size()!=0){
  70.             s2.add(s1.pop());
  71.         }
  72.         return s2;//因为是存放到list,因此正常输出就是逆波兰
  73.     }
  75.     //将中缀表达式转成list
  76.     public static List<String> toinfixExpressionList(String s){
  77.         List<String> ls = new ArrayList<String>();
  78.         int i = 0;
  79.         String str;
  80.         char c;
  81.         do{
  82.             //如果是非数字，加入到ls
  83.             if ((c=s.charAt(i))<48||(c=s.charAt(i))>57){
  84.                 ls.add(""+c);
  85.                 i++;
  86.             }else {//如果是个数，要考虑多位数
  87.                 str = "";//先置空
  88.                 while (i<s.length()&&(c=s.charAt(i))>=48&&(c=s.charAt(i))<=57){
  89.                     str+=c;
  90.                     i++;
  91.                 }
  92.                 ls.add(str);
  93.             }
  94.         }while (i<s.length());
  95.         return ls;
  96.     }
  98.     public static List<String> getListString(String suffixExpression){
  99.         String[] split = suffixExpression.split(" ");
  100.         List<String> list = new ArrayList<String>();
  101.         for(String ele:split){
  102.             list.add(ele);
  103.         }
  104.         return list;
  106.     }
  108.     public static int calulate(List<String> ls){
  109.         Stack<String> stack = new Stack<String>();
  110.         for (String item:ls){
  111.             if(item.matches("\\d+")){
  112.                 stack.push(item);
  113.             }else
  114.             {
  115.                 //不是数，pop出两个数，运算
  116.                 int num2 = Integer.parseInt(stack.pop());
  117.                 int num1 = Integer.parseInt(stack.pop());
  118.                 int res = 0;
  119.                 if(item.equals("+")){
  120.                     res=num1+num2;
  121.                 }else if(item.equals("-")){
  122.                     res = num1-num2;
  123.                 }else if(item.equals("*")){
  124.                     res = num1*num2;
  125.                 }else if(item.equals("/")){
  126.                     res = num1/num2;
  127.                 }else {
  128.                     throw new RuntimeException("运算符有误");
  129.                 }
  130.                 //把res入栈
  131.                 stack.push(""+res);
  132.             }
  133.         }
  134.         //最后留在stack的就是结果
  135.         return Integer.parseInt(stack.pop());
  136.     }
  137. }
  141. //Operation   可以返回一个运算符对应的优先级
  142. class Operation{
  143.     private static int ADD = 1;
  144.     private static int SUB = 1;
  145.     private static int MUL = 2;
  146.     private static int DIV = 2;
  149.     //写一个方法，返回对应的优先级数字
  150.     public static int getValue(String operation){
  151.         int result = 0;
  152.         switch (operation){
  153.             case "+":
  154.                 result = ADD;
  155.                 break;
  156.             case "-":
  157.                 result = SUB;
  158.                 break;
  159.             case "*":
  160.                 result = MUL;
  161.                 break;
  162.             case "/":
  163.                 result = DIV;
  164.                 break;
  165.                 default:
  166.                     System.out.println("不存在该运算符");
  167.                     break;
  168.         }
  169.         return result;
  170.     }
  171. }