中缀表达式转换成后缀表达式

中缀表达式转后缀表达式
思路：

1. 三个方法： ① 将中缀表达式转换成 中缀表达式对应的 List ② 自定义运算符优先级 ???? 将中缀表达式对应的 list 转换成 后缀表达式.
   1.1 使用 list 更好的和 stack 配合，list 比 字符串的遍历更加灵活.
2. 将中缀表达式对应的 list 转换成 后缀表达式
   2.1 需要两个栈： 运算符栈 s1、存储临时结果栈(为了方便使用 List<String> 代替 Stack<String> ) s2
   2.2 遍历 中缀List
   2.3 判断是否为数字、( 、) 、运算符
   2.3.1 如果是数字： 直接压入 s2
   2.3.2 如果是 ( ： 直接压入 s1
   2.3.3 如果是 ) ： 将栈 s1 中 ‘(’ 以上的运算符弹出，压入 s2 ，然后消去 (
   2.3.4 如果是运算符：
   2.3.4.1 当前栈为空 或者 栈顶为 ( ： 直接压入 s1
   2.3.4.2 当前运算符优先级 大于 栈顶的运算符优先级， 直接压人 s1
   2.3.4.3 当前运算符优先级 小于 栈顶的优先级， 将栈顶运算符弹出，压入 s2。 重复上诉 2.3.4.1 和 2.3.4.2 的判断。
   2.4 中缀 List 遍历完后，将 s1 中剩余的运算符依次弹出，压入到 s2 中.
   2.5 如果 s2 使用的 Stack<String> ，还需要将结果逆序输出.

    /**
     *  将中缀表达式转换成后缀表达式
     */
    @Test
    public void TosuffixExpression(){
        /**
         *  直接对 中缀表达式 str 进行操作，不方便，
         *  因此，先将 str 中缀表达式变成对应的 list
         *
         *  对 list 遍历比对 字符串遍历更加灵活
         */

        String expression = "1+((2+3)*4)-5";
        List<String> list = toInSuffixStringList(expression);
        List<String> suffixExpression = getSuffixExpression(list);
        System.out.println(suffixExpression);
        // [1, 2, 3, +, 4, *, +, 5, -]
    }


    /**
     *   将 中缀表达式转成对应的 List
     */
    public static List<String> toInSuffixStringList(String str){
        // 存放 str 字符内容
        List<String> list = new ArrayList<>();

        // 定义需要的相应的变量
        int index = 0;  // 指针，遍历 str 用的
        String s ;
        char ch = ' ';
        // 分解字符串
        while (index < str.length()){
            ch = str.charAt(index++);
            // ch 是个数字
            if( ch >= '0' && ch <= '9'){
                // 重置 s
                s = "";
                s += ch;
                // 防止多位数，进行字符拼接
                while (index < str.length() && ch >= '0' && ch <= '9'){
                    ch = str.charAt(index++);
                    if(ch >= '0' && ch <= '9'){
                        s += ch;
                    }else {
                        // 注意当前是符号了，index ++ 后是符号的下一个, --回去给上面取出这个符号
                        index--;
                        break;
                    }
                }
                list.add(s);
            }else {
                // 不是数字, 直接添加
                list.add(ch + "");
            }
        }
        return list;
    }


    /**
     *   将 中缀表达式对应的List 转换成 后缀表达式
     */
    public static List<String> getSuffixExpression(List<String> list){
        // 需要两个栈
        // 运算符栈
        Stack<String> s1 = new Stack<>();
        // 中间结果栈
        // 因为这个栈只有 push 操作， 没有 pop 最后还需要逆序输出结果，相对较麻烦。
//        Stack<String> s2 = new Stack<>();
        // 所以使用 list 来代替
        List<String> s2 = new ArrayList<>();

        for (String c : list){

            // 判断它是否是数 -- 正则表达式
            if(c.matches("\\d+")){
                // 如果是数字， 直接压入 s2 中
                s2.add(c);
            }else if("(".equals(c)){
                // 不是数字
                // ( 直接压入 s1 中
                s1.push(c);
            }else if(")".equals(c)){
                // 不是数字
                // ) 将s1中的( 之前的符号弹出 然后压入s2 中
                while (!s1.peek().equals("(")){
                    s2.add(s1.pop());
                }
                // 然后再将 ( 消除
                s1.pop();
            } else {
                // 如果是运算符
                // 当前运算符 小于等于s1 栈顶的运算符优先级时
                while (!s1.empty() && Operation.getValue(c) <= Operation.getValue(s1.peek())){
                    // 将 s1 中的符号弹出，然后压入 s2 中
                    s2.add(s1.pop());
                }
                // 再将当前符号压入 s1
                // 或：
                // 1. 当前运算符优先级 大于 栈顶运算符
                // 2. 当前栈顶为  ( 
                s1.push(c);
            }
        }
        // 最后将s1中剩余的按序弹出压入到 s2 中
        while (!s1.empty()){
            s2.add(s1.pop());
        }

        // 如果s2是stack，还需要逆序结果
        return s2;
    }

    /**
     *  运算符优先级
     */
    static class Operation{
        private static final Integer ADD = 1;
        private static final Integer SUB = 1;
        private static final Integer MUL = 2;
        private static final Integer DIV = 2;

        public static int getValue(String c){
            if(c.equals("+")){
                return ADD;
            }else if(c.equals("-")){
                return SUB;
            }else if(c.equals("*")){
                return MUL;
            }else if(c.equals("/")){
                return DIV;
            } else {
                System.out.println("无该运算符[这是在s1中的 ( 还没被消去时 ]: " + c);
            }
            return 0;
        }

    }