public class PolandNotation {
    public static void main(String[] args) {
        //先定义一个逆波兰表达式
        //(3+4)*5-6 => 3 4 +5 * 6 -
        //说明为了方便，逆波兰表达式的数字和符号使用空格隔开
        String suffixExpression = "3 4 + 5 * 6 -";
        //思路
        //1.先将"3 4 +5 * 6 -" => 放到ArrayList中
        //2.将ArrayList 传递给一个方法,遍历ArrayList配合栈完成计算
        List<String> list = getListString(suffixExpression);
        int res = calculate(list);
        System.out.println("计算结果是="+res);
    }
    //将一个逆波兰表达式，依次将数据和运算符放入到ArrayList中
    public static List<String> getListString(String suffixExpression) {
        //将suffixExpression分割
        String[] split = suffixExpression.split(" ");
        List<String> list = new ArrayList<String>();
        for (String ele : split) {
            list.add(ele);
        }
        return list;
    }
    //完成对逆波兰表达式的运算
    /**
     * 1. 从左至右扫描，将3和4压入堆栈：
     * 2. 遇到+运算符，因此弹出4和3(4为栈顶元素，3为次顶元素)，计算出3+4的值，得7，再将7入栈：
     * 3. 将5入栈：
     * 4. 接下来是×运算符，因此弹出5和7，计算出7×5=35，将35入栈：
     * 5. 将6入栈：
     * 6. 最后是-运算符，计算出35-6的值，即29，由此得出最终结果
     */
    public static int calculate(List<String> ls) {
        //创建给栈,只需要一个栈即可
        Stack<String> stack = new Stack<>();
        //遍历 ls
        for (String item : ls) {
            //这里使用正则表达式来取出数
            if (item.matches("\d+")) {//匹配多位数
                //入栈
                stack.push(item);
            } else {
                //pop出两个数,并运算,在入栈
                int num2 = Integer.parseInt(stack.pop());
                int num1 = Integer.parseInt(stack.pop());
                int res = 0;
                if (item.equals("+")) {
                    res = num1 + num2;
                } else if (item.equals("-")) {
                    res = num1 - num2;
                } else if (item.equals("*")) {
                    res = num1 * num2;
                } else if (item.equals("/")) {
                    res = num1 / num2;
                }else {
                    throw new RuntimeException("运算符有问题");
                }
                //把res 入栈
                stack.push(""+res);
            }
        }
        ///最后留在stack的数据是运算结构
        return Integer.parseInt(stack.pop());
    }
}
复制代码

public class PolandNotation {
    public static void main(String[] args) {
        //完成将一个中缀表达式转成后缀表达式的功能
        //说明
        //1.    1+((2+3)×4)-5 => " 1 2 3 + 4 * + 5 -"
        //2.因为直接对 str 进行操作 不方便 因此先将1+((2+3)×4)-5 => 中缀表达式对应得List
        //  即"1+((2+3)×4)-5" = >ArrayList  [1,+,(,(,2,+,3,),×,4,),-,5]
        //3.将得到的中缀表达式对应的List => 后缀表达式对应的List
        //  即ArrayList [1, +, (, (, 2, +, 3, ), ×, 4, ), -, 5] => [1, 2, 3, + 4, *, +, 5, -]
        String expression = "1+((2+3)*4)-5";
        List<String> infixExpression = toInfixExpressionList(expression);
        System.out.println("中缀表达式对应的List="+infixExpression);
        List<String> suffixExpression = parseSuffixExpressionList(infixExpression);
        System.out.println("后缀表达式对应的List="+suffixExpression);
        //先定义一个逆波兰表达式
        //(3+4)*5-6 => 3 4 +5 * 6 -
        //说明为了方便，逆波兰表达式的数字和符号使用空格隔开
        //String suffixExpression = "3 4 + 5 * 6 -";
        //思路
        //1.先将"3 4 +5 * 6 -" => 放到ArrayList中
        //2.将ArrayList 传递给一个方法,遍历ArrayList配合栈完成计算
        //List<String> list = getListString(suffixExpression);
        int res = calculate(suffixExpression);
        System.out.println("计算结果是=" + res);
    }
    //  即ArrayList [1, +, (, (, 2, +, 3, ), ×, 4, ), -, 5] => [1, 2, 3, + 4, *, +, 5, -]
    //方法: 中缀表达式转成后缀表达式的
    public static List<String> parseSuffixExpressionList(List<String> ls) {
        //定义两个栈
        Stack<String> s1 = new Stack<>();//符号栈
        //说明：因为s2这个栈，在整个转换过程中，没有pop操作，而且后面我们还需要逆序输出
        //因此比较麻烦，这里我们就不用Stack<String>直接使用List<String>s2
        //Stack<String> s2 = new Stack<>();//存储中间结果得栈s2
        List<String> s2 = new ArrayList<>();//存储中间结果得栈s2
        //遍历ls
        for (String item : ls) {
            //如果是一个数,加入到s2
            if (item.matches("\d+")) {
                s2.add(item);
            } else if (item.equals("(")) {
                s1.push(item);
            } else if (item.equals(")")) {
                //如果是右括号“)”，则依次弹出s1栈顶的运算符，并压入s2,直到遇到左括号为止，此时将这一对括号丢弃
                while (!s1.peek().equals("(")) {
                    s2.add(s1.pop());
                }
                s1.pop();//将 ( 弹出s1栈,消除小括号
            } else {
                //当item的优先级小于等于s1栈顶运算符，将s1栈顶的运算符弹出并加入到s2中，再次转到(4.1)与s1中新的栈顶运算符相比较
                //问题:缺少一个比较优先级高低的办法
                while (s1.size() != 0 && Operation.getValue(s1.peek())>=Operation.getValue(item)){
                    s2.add(s1.pop());
                }
                //还需要将item压入栈
                s1.push(item);
            }
        }
        //将s1中剩余的运算符依次弹出并加入s2
        while(s1.size() != 0){
            s2.add(s1.pop());
        }
        return s2; //注意因为是存放到List,因此按顺序输出就是对应的后缀表达式对应的Lst
    }
    //方法:将中缀表达式转成对应得List
    public static List<String> toInfixExpressionList(String s) {
        //定义一个List,存放中缀表达式 对应得内容
        List<String> ls = new ArrayList<String>();
        int i = 0;//这个是一个指针,用于遍历 中缀表达式字符串
        String str; //对多位数得拼接
        char c;//没遍历到一个字符,就放入到c
        do {
            //如果c是一个非数字,我们就需要加入到ls
            if ((c = s.charAt(i)) < 48 || (c = s.charAt(i)) > 57) {
                ls.add("" + c);
                i++;//i需要后移
            } else { //如果是一个树,需要考虑多位数
                str = "";//先将str 置成""
                while (i < s.length() && (c = s.charAt(i)) >= 48 && (c = s.charAt(i)) <= 57) {
                    str += c;//拼接
                    i++;
                }
                ls.add(str);
            }
        } while (i < s.length());
        return ls;
    }
    //将一个逆波兰表达式，依次将数据和运算符放入到ArrayList中
    public static List<String> getListString(String suffixExpression) {
        //将suffixExpression分割
        String[] split = suffixExpression.split(" ");
        List<String> list = new ArrayList<String>();
        for (String ele : split) {
            list.add(ele);
        }
        return list;
    }
    //完成对逆波兰表达式的运算
    /**
     * 1. 从左至右扫描，将3和4压入堆栈：
     * 2. 遇到+运算符，因此弹出4和3(4为栈顶元素，3为次顶元素)，计算出3+4的值，得7，再将7入栈：
     * 3. 将5入栈：
     * 4. 接下来是×运算符，因此弹出5和7，计算出7×5=35，将35入栈：
     * 5. 将6入栈：
     * 6. 最后是-运算符，计算出35-6的值，即29，由此得出最终结果
     */
    public static int calculate(List<String> ls) {
        //创建给栈,只需要一个栈即可
        Stack<String> stack = new Stack<>();
        //遍历 ls
        for (String item : ls) {
            //这里使用正则表达式来取出数
            if (item.matches("\d+")) {//匹配多位数
                //入栈
                stack.push(item);
            } else {
                //pop出两个数,并运算,在入栈
                int num2 = Integer.parseInt(stack.pop());
                int num1 = Integer.parseInt(stack.pop());
                int res = 0;
                if (item.equals("+")) {
                    res = num1 + num2;
                } else if (item.equals("-")) {
                    res = num1 - num2;
                } else if (item.equals("*")) {
                    res = num1 * num2;
                } else if (item.equals("/")) {
                    res = num1 / num2;
                } else {
                    throw new RuntimeException("运算符有问题");
                }
                //把res 入栈
                stack.push("" + res);
            }
        }
        ///最后留在stack的数据是运算结构
        return Integer.parseInt(stack.pop());
    }
}
//编写一个类Operation 可以返回一个运算符 对应的优先级
class Operation {
    private static int ADD = 1;
    private static int SUB = 1;
    private static int MUL = 2;
    private static int DIV = 2;
    //写一个方法,返回对应的优先级数字
    public static int getValue(String operation){
        int result = 0;
        switch (operation){
            case "+":
                result = ADD;
                break;
            case "-":
                result = SUB;
                break;
            case "*":
                result = MUL;
                break;
            case "/":
                result = DIV;
                break;
            default:
                System.out.println("不存在该运算符");
                break;
        }
        return result;
    }
}
复制代码

public static void test ( int n){
        if (n > 2) {
            test(n - 1);
        }
        System.out.println("n=" + n);
    }
复制代码

public static int factorial(int n) {
        if (n == 1) {
            return 1;
        } else {
            return factorial(n - 1) * n;
            /*
            n=3
            factorial(3-1)*3  =>factorial(2-1)*2*3 =>factorial(1)*2*3
             */
        }
    }
复制代码

public class Maze {
    public static void main(String[] args) {
        //先创建一个二维数组,模拟迷宫
        //地图
        int[][] map = new int[8][7];
        //使用1表示墙
        //上下全部置为1
        for (int i = 0; i < 7; i++) {
            map[0][i] = 1;
            map[7][i] = 1;
        }
        //左右全部为1
        for (int i = 0; i < 8; i++) {
            map[i][0] = 1;
            map[i][6] = 1;
        }
        //设置挡板
        map[3][1] = 1;
        map[3][2] = 1;
        //输出地图
        System.out.println("地图的情况");
        for (int i = 0; i < map.length; i++) {
            for (int j = 0; j < map[i].length; j++) {
                System.out.print(map[i][j] + " ");
            }
            System.out.println();
        }
        //使用递归回溯给小球找路
        setWay1(map,1,1);
        //输出新的地图,小球走过,并标识过的地图
        System.out.println("小球走过,并标识过的地图");
        for (int i = 0; i < map.length; i++) {
            for (int j = 0; j < map[i].length; j++) {
                System.out.print(map[i][j] + " ");
            }
            System.out.println();
        }
    }
    //使用递归回溯来给小球找路
    /*
    1.map表示地图
    2.i,j表示从地图的哪个位置开始出发（1,1)
    3.如果小球能到map[6][5]位置，则说明通路找到，
    4.约定：当map[i][j]为0表示该点没有走过当为1表示墙；2表示通路可以走；3表示该点已经走过，但是走不通
    5.在走迷宫时,需要确定一个策略(方法) 下->右->上->左 ,如果该点走不通在回溯
     */
    /**
     * @param map 地图
     * @param i   从哪个位置开始找
     * @param j
     * @return 如果找到通路，就返回true,否则返回false
     */
    public static boolean setWay1(int[][] map, int i, int j) {
        if (map[6][5] == 2) { //同路已经找到
            return true;
        } else {
            if (map[i][j] ==0){ //如果当前的点还没有走过
                //按照策略下->右->上->左
                map[i][j]=2;//假定该点是可以走通
                if (setWay(map,i+1,j)){ //向下走
                    return true;
                }else if (setWay1(map,i,j+1)) { //向右走
                    return true;
                }else if (setWay1(map,i-1,j)) { //向上走
                    return true;
                }else if(setWay1(map,i,j-1)){ //向左走
                    return true;
                }else{
                    //说明改点走不通,是死路
                    map[i][j]=3;
                    return false;
                }
            }else{ //如果map[i][j] != 0,可能是1,2,3
                return false;
            }
        }
    }
}
复制代码

//修改找路的策略  改成上->右->下->左
public static boolean setWay2(int[][] map, int i, int j) {
    if (map[6][5] == 2) { //同路已经找到
        return true;
    } else {
        if (map[i][j] == 0) { //如果当前的点还没有走过
            //按照策略下->右->上->左
            map[i][j] = 2;//假定该点是可以走通
            if (setWay2(map, i - 1, j)) { //向上走
                return true;
            } else if (setWay2(map, i, j + 1)) { //向右走
                return true;
            } else if (setWay2(map, i + 1, j)) { //向下走
                return true;
            } else if (setWay2(map, i, j - 1)) { //向左走
                return true;
            } else {
                //说明改点走不通,是死路
                map[i][j] = 3;
                return false;
            }
        } else { //如果map[i][j] != 0,可能是1,2,3
            return false;
        }
    }
}
复制代码

public class Queue8 {
    //定义一个max表示共有多少个皇后
    int max =8;
    //定义数组array,保存皇后防止位置的结果,比如  arr[8]={0,4,7,5,2,6,1,3}
    int [] array = new int [max];
    static int count = 0;
    public static void main(String[] args) {
        Queue8 queue8 = new Queue8();
        queue8.check(0);
        System.out.printf("一共有%d解法",count);
    }
    //编写一个方法,放置第n个皇后
    //特别注意：check是每一次递归时，进入到check中都有for(int i=0;i<max;i++)
    private void check(int n){
        if (n==max){ //n=8,其实8个皇后就已然放好
            print();
            return;
        }
        //依次放入皇后,并判断是否重复
        for (int i = 0; i < max; i++) {
            //先把当前这个皇后 n 放到该行的第1列
            array[n] = i;
            //判断当防止第n个皇后i列时,是否冲突
            if (judge(n)){ //不冲突
                //接着放n+1个皇后,即开始递归
                check(n+1);
            }
            //如果冲突,就继续执行array[n] = i即将第n个皇后放置在本行的后移的一个位置
        }
    }
    //查看当我们放置第个皇后，就去检测该皇后是否和前面已经摆放的皇后冲突
    /**
     *
     * @param n 表示第n个皇后
     * @return
     */
    private boolean judge(int n){
        for (int i = 0; i < n; i++) {
            //说明
            //1.array[i]==array[n]表示判断第n个皇后是否和前面的n-1个皇后在同一列
            //2.Math.abs(n-1)==Math.abs(array[n]-array[i])表示判断第个皇后是否和第i皇后是否在同一斜线
            if (array[i]==array[n]||Math.abs(i-n)==Math.abs(array[i]-array[n])){
                return false;
            }
        }
        return true;
    }
    //写一个方法,可以将皇后摆放的位置输出
    private void print(){
        count++;
        for (int i = 0; i < array.length;i++) {
            System.out.print(array[i]+" ");
        }
        System.out.println();
    }
}