【java】中缀表达式转后缀表达式 java实现

  1 package com.agen.exchangePox;
  2 
  3 import java.util.ArrayList;
  4 import java.util.Arrays;
  5 import java.util.HashMap;
  6 import java.util.List;
  7 import java.util.Map;
  8 import java.util.stream.Collectors;
  9 
 10 import org.junit.Test;
 11 
 12 public class InfixInToSuffix {
 13     /**
 14      *提前将 符号的优先级定义好
 15      */
 16     private static final Map<Character, Integer> basic = new HashMap<Character, Integer>();
 17     static {
 18         basic.put('-', 1);
 19         basic.put('+', 1);
 20         basic.put('*', 2);
 21         basic.put('/', 2);
 22         basic.put('(', 0);//在运算中  （）的优先级最高，但是此处因程序中需要 故设置为0
 23     }
 24     
 25     @Test
 26     public void test(){
 27         String a = toSuffix("55.6+4*60/2+33+(4.7*5.6)/5");//传入 一串 算数公式  
 28         System.out.println(a);
 29         System.out.println(dealEquation(a));
 30         
 31         
 32     }
 33     
 34     /**
 35      * 将  中缀表达式  转化为  后缀表达式
 36      */
 37     public String toSuffix(String infix){
 38         List<String> queue = new ArrayList<String>();                                    //定义队列  用于存储 数字  以及最后的  后缀表达式
 39         List<Character> stack = new ArrayList<Character>();                             //定义栈    用于存储  运算符  最后stack中会被 弹空
 40         
 41         char[] charArr = infix.trim().toCharArray();                                    //字符数组  用于拆分数字或符号
 42         String standard = "*/+-()";                                                        //判定标准 将表达式中会出现的运算符写出来
 43         char ch = '&';                                                                    //在循环中用来保存 字符数组的当前循环变量的  这里仅仅是初始化一个值  没有意义
 44         int len = 0;                                                                    //用于记录字符长度 【例如100*2,则记录的len为3 到时候截取字符串的前三位就是数字】
 45         for (int i = 0; i < charArr.length; i++) {                                        //开始迭代
 46             
 47             ch = charArr[i];                                                            //保存当前迭代变量
 48             if(Character.isDigit(ch)) {                                                    //如果当前变量为 数字  
 49                 len++;    
 50             }else if(Character.isLetter(ch)) {                                            //如果当前变量为  字母
 51                 len++;
 52             }else if(ch == '.'){                                                        //如果当前变量为  .  会出现在小数里面
 53                 len++;
 54             }else if(Character.isSpaceChar(ch)) {                                        //如果当前变量为 空格  支持表达式中有空格出现
 55                 if(len > 0) {                                                            //若为空格 代表 一段结束 ，就可以往队列中  存入了  【例如100 * 2  100后面有空格 就可以将空格之前的存入队列了】
 56                     queue.add(String.valueOf(Arrays.copyOfRange(charArr, i - len, i)));    //往 队列存入 截取的 字符串 
 57                     len = 0;                                                            //长度置空
 58                 }
 59                 continue;                                                                //如果空格出现，则一段结束  跳出本次循环
 60             }else if(standard.indexOf(ch) != -1) {                                        //如果是上面标准中的 任意一个符号
 61                 if(len > 0) {                                                            //长度也有
 62                     queue.add(String.valueOf(Arrays.copyOfRange(charArr, i - len, i)));    //说明符号之前的可以截取下来做数字
 63                     len = 0;                                                            //长度置空
 64                 }
 65                 if(ch == '(') {                                                            //如果是左括号
 66                     stack.add(ch);                                                        //将左括号 放入栈中
 67                     continue;                                                            //跳出本次循环  继续找下一个位置
 68                 }
 69                 if (!stack.isEmpty()) {                                                    //如果栈不为empty
 70                     int size = stack.size() - 1;                                        //获取栈的大小-1  即代表栈最后一个元素的下标
 71                     boolean flag = false;                                                //设置标志位
 72                     while (size >= 0 && ch == ')' && stack.get(size) != '(') {            //若当前ch为右括号，则 栈里元素从栈顶一直弹出，直到弹出到 左括号
 73                         queue.add(String.valueOf(stack.remove(size)));                    //注意此处条件：ch并未入栈，所以并未插入队列中；同样直到找到左括号的时候，循环结束了，所以左括号也不会放入队列中【也就是：后缀表达式中不会出现括号】
 74                         size--;                                                            //size-- 保证下标永远在栈最后一个元素【栈中概念：指针永远指在栈顶元素】
 75                         flag = true;                                                    //设置标志位为true  表明一直在取（）中的元素
 76                     }
 77                     while (size >= 0 && !flag && basic.get(stack.get(size)) >= basic.get(ch)) {    //若取得不是（）内的元素，并且当前栈顶元素的优先级>=对比元素 那就出栈插入队列
 78                         queue.add(String.valueOf(stack.remove(size)));                    //同样  此处也是remove()方法，既能得到要获取的元素，也能将栈中元素移除掉
 79                         size--;
 80                     }
 81                 }
 82                 if(ch != ')') {                                                            //若当前元素不是右括号  
 83                     stack.add(ch);                                                        //就要保证这个符号 入栈
 84                 } else {                                                                //否则就要出栈 栈内符号
 85                     stack.remove(stack.size() - 1);
 86                 }
 87             }
 88             if(i == charArr.length - 1) {                                                //如果已经走到了  中缀表达式的最后一位
 89                 if(len > 0) {                                                            //如果len>0  就截取数字
 90                     queue.add(String.valueOf(Arrays.copyOfRange(charArr, i - len+1, i+1)));
 91                 }    
 92                 int size = stack.size() - 1;                                            //size表示栈内最后一个元素下标
 93                 while (size >= 0) {                                                        //一直将栈内  符号全部出栈 并且加入队列中  【最终的后缀表达式是存放在队列中的，而栈内最后会被弹空】
 94                     queue.add(String.valueOf(stack.remove(size)));
 95                     size--;
 96                 }
 97             }
 98             
 99         }
100         return queue.stream().collect(Collectors.joining(","));                            //将队列中元素以,分割 返回字符串
101     }
102     
103 
104     /**
105      * 将 后缀表达式 进行  运算 计算出结果
106      * @param equation
107      * @return
108      */
109     public String dealEquation(String equation){
110         String [] arr = equation.split(",");                                    //根据, 拆分字符串
111         List<String> list = new ArrayList<String>();                            //用于计算时  存储运算过程的集合【例如list中当前放置  100   20  5  /  则取出20/5 最终将结果4存入list   此时list中结果为  100  4 】
112         
113         
114         for (int i = 0; i < arr.length; i++) {                                    //此处就是上面说的运算过程， 因为list.remove的缘故，所以取出最后一个数个最后两个数  都是size-2
115             int size = list.size();
116             switch (arr[i]) {
117             case "+": double a = Double.parseDouble(list.remove(size-2))+ Double.parseDouble(list.remove(size-2)); list.add(String.valueOf(a));     break;
118             case "-": double b = Double.parseDouble(list.remove(size-2))- Double.parseDouble(list.remove(size-2)); list.add(String.valueOf(b));     break;
119             case "*": double c = Double.parseDouble(list.remove(size-2))* Double.parseDouble(list.remove(size-2)); list.add(String.valueOf(c));     break;
120             case "/": double d = Double.parseDouble(list.remove(size-2))/ Double.parseDouble(list.remove(size-2)); list.add(String.valueOf(d));       break;
121             default: list.add(arr[i]);     break;                                    //如果是数字  直接放进list中
122             }
123         }
124         
125         return list.size() == 1 ? list.get(0) : "运算失败" ;                    //最终list中仅有一个结果，否则就是算错了
126     }
127     
128     
129 
130 }