全部标签
写点什么
OpenHarmony算法元宇宙MySQL移动开发学习方法Web3.0高效工作数据库Python音视频前端AI大数据团队管理程序员运维深度思考低代码redisgolang微服务架构flutter 查看更多

Qz 学算法 - 数据结构篇 (表达式、递归)

作者：浅辄
  • 2023-04-23
    吉林

  • 本文字数：9841 字

    阅读完需：约 32 分钟

前缀、中缀、后缀表达式->(逆波兰表达式)

1.前缀表达式(波兰表达式)

  • 前缀表达式又称波兰式，前缀表达式的运算符位于操作数之前

  • 举例说明：(3+4)×5-6 对应的前缀表达式就是-×+3456

前缀表达式的计算机求值

从右至左扫描表达式，遇到数字时，将数字压入堆栈，遇到运算符时，弹出栈顶的两个数，用运算符对它们做相应的计算（栈顶元素和次顶元素），并将结果入栈：重复上述过程直到表达式最左端，最后运算得出的值即为表达式的结果


例如：(3+4)×5-6 对应的前缀表达式就是**-×+3456，针对前缀表达式求值步骤如下：


  1. 从右至左扫描，将 6、5、4、3 压入堆栈

  2. 遇到+运算符，因此弹出 3 和 4（3 为栈顶元素，4 为次顶元素)，计算出 3+4 的值，得 7 再将 7 入栈

  3. 接下来是×运算符，因此弹出 7 和 5，计算出 7×5=35，将 35 入栈

  4. 最后是-运算符，计算出 35-6 的值，即 29，由此得出最终结果

2.中缀表达式

  • 中缀表达式就是常见的运算表达式，如(3+4)×5-6

  • 中缀表达式的求值是我们人最熟悉的，但是对计算机来说却不好操作，因此，在计算结果时，往往会将中缀表达式转成其它表达式来操作(一般转成后缀表达式)

3.后缀表达式

  • 后缀表达式又称逆波兰表达式，与前缀表达式相似，只是运算符位于操作数之后

  • 中举例说明：(3+4)×5-6 对应的后缀表达式就是 34+5×6-

  • 再比如



后缀表达式的计算机求值

从左至右扫描表达式，遇到数字时，将数字压入堆栈，遇到运算符时，弹出栈顶的两个数，用运算符对它们做相应的计算（次顶元素和栈顶元素），并将结果入栈：重复上述过程直到表达式最右端，最后运算得出的值即为表达式的结果


例如：(3+4)×5-6 对应的后缀表达式就是 34+5×6-，针对后缀表达式求值步骤如下：


  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，由此得出最终结果

逆波兰计算器

输入一个逆波兰表达式，使用栈(Stack),计算其结果


支持小括号和多位数整数，因为这里我们主要讲的是数据结构，因此计算器进行简化，只支持对整数的计算。


思路分析


代码完成


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());    }}
复制代码

4.中缀转后缀表达式

大家看到，后缀表达式适合计算式进行运算，但是人却不太容易写出来，尤其是表达式很长的情况下，因此在开发中，我们需要将中缀表达式转成后缀表达式。

操作步骤

  1. 初始化两个栈：运算符栈 s1 和储存中间结果的栈 s2;

  2. 从左至右扫描中缀表达式：

  3. 遇到操作数时，将其压 s2:

  4. 遇到运算符时，比较其与 s1 栈顶运算符的优先级：

  5. 如果 s1 为空，或栈顶运算符为左括号“("，则直接将此运算符入栈：

  6. 否则，若优先级比栈顶运算符的高，也将运算符压入 s1:

  7. 否则，将 s1 栈顶的运算符弹出并压入到 s2 中，再次转到(4.1)与 s1 中新的栈顶运算符相比较；

  8. 遇到括号时：

  9. 如果是左括号"()"，则直接压入 s1

  10. 如果是右括号“)”，则依次弹出 s1 栈顶的运算符，并压入 s2,直到遇到左括号为止，此时将这一对括号丢弃

  11. 重复步骤 2 至 5，直到表达式的最右边

  12. 将 s1 中剩余的运算符依次弹出并压入 s2

  13. 依次弹出 s2 中的元素并输出，结果的逆序即为中缀表达式对应的后缀表达式

举例说明

将中缀表达式“1+((2+3)×4)-5”转换为后缀表达式的过程如下



因此结果为:


" 1 2 3 + 4 * + 5 -"

代码实现

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;    }}
复制代码

递归

需求引入


看个实际应用场景，迷宫问题（回溯），递归(Recursion)

1.递归的概念

简单的说：递归就是方法自己调用自己，每次调用时传入不同的变量递归有助于编程者解决复杂的问题，同时可以让代码变得简洁。

2.递归调用机制

  • 打印问题


        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                 */            }        }
复制代码



3.递归能解决什么样的问题

  • 各种数学问题如：8 皇后问题，汉诺塔，阶乘问题，迷宫问题，球和篮子的问题(google 编程大赛)

  • 各种算法中也会使用到递归，比如快排，归并排序，二分查找，分治算法等

  • 将用栈解决的问题->第归代码比较简洁

4.递归需要遵守的重要规则

  • 执行一个方法时，就创建一个新的受保护的独立空间（栈空间）

  • 方法的局部变量是独立的，不会相互影响，比如 n 变量

  • 如果方法中使用的是引用类型变量（比如数组），就会共享该引用类型的数据

  • 归必须向退出递归的条件逼近，否则就是无限递归，出现 StackOverflowError,死归了：)

  • 当一个方法执行完毕，或者遇到 return.,就会返回，遵守谁调用，就将结果返回给谁，同时当方法执行完毕或者返回时，该方法也就执行完毕。

迷宫回溯问题

  • 小球得到的路径，和程序员设置的找路策略有关即：找路的上下左右的顺序相关

  • 再得到小球路径时，可以先使用（下右上左），再改成（上右下左)，看看路径是不是有变化

  • 测试回溯现象

  • 思考：如何求出最短路径？

代码实现

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;            }        }    }}
复制代码

关于回溯

如果我在设置起点为 1,1,而 map[3][1] = 1; map[3][2] = 1; map[4][1] = 1;map[4][2] = 1;,这样只有上下两个格子可以移动,这时运行完就会把走过的路径设置为 3

最短路径

//修改找路的策略  改成上->右->下->左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;        }    }}
复制代码


最简单的方法就是对上下左右的找路策略进行穷举，然后比较哪个最短即可

八皇后问题

需求引入

八皇后问题，是一个古老而著名的问题，是回溯算法的典型案例。该问题是国际西洋棋棋手马克斯-贝瑟尔于 1848 年提出：在 8×8 格的国际象棋上摆放八个皇后，使其不能互相攻击，即：任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少 种摆法。



思路分析

  1. 第一个皇后先放第一行第一列

  2. 第二个皇后放在第二行第一列、然后判断是否 OK,如果不 0K,继续放在第二列、第三列、依次把所有列都放完，找到一个合适

  3. 继续第三个皇后，还是第一列、第二列直到第 8 个皇后也能放在一个不冲突的位置，算是找到了一个正确解

  4. 当得到一个正确解时，在栈回退到上一个栈时，就会开始回溯，即将第一个皇后，放到第一列的所有正确解，全部得到

  5. 然后回头继续第一个皇后放第二列，后面继续循环执行 1,2,3 的步骤


说明

理论上应该创建一个二维数组来表示棋盘，但是实际上可以通过算法，用一个一维数组即可解决问题.arr[8]={0,4,7,5,2,6,1,3} //对应 arr 下标 表示第几行，即第几个皇后，arr[i]=val,val 表示第 i+1 个皇后，放在第 i+1 行的第 val+1 列

代码实现

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();    }}
复制代码


划线
评论
复制
发布于: 刚刚阅读数: 3

版权声明: 本文为 InfoQ 作者【浅辄】的原创文章。

原文链接:【http://xie.infoq.cn/article/ffd26f26cd8d3db226200f195】。文章转载请联系作者。

数据结构三周年连更
用户头像

浅辄

关注

大丈夫生于天地之间,岂能郁郁久居人之下 2022-11-08 加入

Java、Spider、Go

评论

发布
暂无评论
Copyright © 2023, Geekbang Technology Ltd. All rights reserved. 极客邦控股（北京）有限公司 | 京 ICP 备 16027448 号 - 5京公网安备京公网安备 11010502039052号
Qz学算法-数据结构篇(表达式、递归)_数据结构_浅辄_InfoQ写作社区