Java 数据结构 栈 - Lisp前缀表达式解析与回溯方式走迷宫

Java 数据结构 栈 - Lisp前缀表达式解析与回溯方式走迷宫

这两天沉迷POE中, 果然是复杂一些的游戏才玩的进去. 可以暂时玩着等今年的废土3和博德之门3了. 当然开发方面也绝对不能落下, 这两天把栈相关的练习写完了, 其中有两个比较大的程序值得留意一下. 分别是Lisp表达式解析和用栈来记录路径走迷宫. Lisp表达式解析 迷宫寻路 Lisp表达式解析 L

这两天沉迷POE中, 果然是复杂一些的游戏才玩的进去. 可以暂时玩着等今年的废土3和博德之门3了. 当然开发方面也绝对不能落下, 这两天把栈相关的练习写完了, 其中有两个比较大的程序值得留意一下. 分别是Lisp表达式解析和用栈来记录路径走迷宫.
  1. Lisp表达式解析
  2. 迷宫寻路

Lisp表达式解析

Lisp表达式是前缀表达式, 解析思路其实和之前也差不多, 关键还是在处理括号的套路, 由于Lisp表达式的括号必定是成对的, 只要遇到一个右括号, 就必定可以计算出来一个结果. 所以其实思路不算太难就想得到. 这里还考虑了换行符和空白等符号, 以让输入一段表达式更加方便. 算法如下: 从表达式的开始进行解析, 表达式的每个字符有如下几种情况:
  1. 遇到一个操作符, 将操作符压入操作符A栈中, 称为A栈. 由于操作符是单个的, 所以使用Char类型的Stack接口对象
  2. 遇到一个左括号, 将左括号压入操作数栈中,称为B栈, 这里左括号实际上是一个区分, 所以比较好的方法是不压入操作符栈中, 而是压入操作数栈中. 不过这里碰到类型问题, 后来想了想, 还是使用了字符串和BigDecimal类之间的转换来操作, 因此这里的栈就是字符串栈.
  3. 遇到一个操作数, 将操作数压入B栈.
  4. 遇到一个右括号, 从A栈中弹出一个操作符, 从B栈中不断的弹出所有操作数直到遇到左括号, 弹出左括号, 计算操作符与所有的操作数的结果, 将结果放回到B栈中
  5. 遇到其他字符(比如空白), 跳过.
这里读入操作数的时候, 并不是简单的读入单字符, 而是从当前字符串的位置开始, 向后不断搜索到空白或者右括号的部分, 将这个部分读入成一个字符串, 然后创建对应的BigDecimal类来解析. 根据上边的思路, 可以编写代码如下:
import java.math.BigDecimal;
import java.math.RoundingMode;
import java.util.Scanner;

public class LispInterpreter {

    public static void main(String[] args) {
        boolean goOn = true;
        Scanner input = new Scanner(System.in);
        String expression;
        while (goOn) {
            System.out.println("请输入Lisp表达式, 例如(+(-6)(*2 3 4)).  输入quit退出: ");
            expression = input.nextLine();
            if (expression.equals("quit")) {
                goOn = false;
            } else {
                try {
                    System.out.println("你输入的表达式的结果是: " + evaluateLispExpression(expression));
                } catch (IllegalArgumentException e) {
                    System.out.println(e.getMessage());
                }
            }
        }
    }

    public static String evaluateLispExpression(String expression) {
        int length = expression.length();

        //存放字符串形式的值的栈
        Stack<String> valueStack = new LinkedListStack<>();

        //存放操作符的栈
        Stack<Character> operatorStack = new LinkedListStack<>();

        //开始遍历表达式
        for (int i = 0; i < length; i++) {
            char currentChar = expression.charAt(i);

            switch (currentChar) {

                //左括号就压值栈
                case '(':
                    valueStack.push(String.valueOf(currentChar));
                    break;

                //加减乘除操作符, 压操作符栈
                case '+':
                case '-':
                case '*':
                case '/':
                    operatorStack.push(currentChar);
                    break;

                //右括号需要计算一对括号中的结果
                case ')':
                    //首先获取最近的操作符.
                    char operator = operatorStack.pop();
                    //将操作符和当前的值栈交给解析一对括号的函数来操作
                    parseSinglePairExpression(operator, valueStack);
                    break;

                //各种空白符直接忽略
                case ' ':
                case '\n':
                case '\r':
                    break;

                //剩下的是数字字符, 需要从当前位置一直读入到下一个空白符合或者右括号为止
                default:
                    //用一个变量j来判断空白符号或者右括号, 只要不是, 遇到字符就连续拼接
                    int j = i;
                    StringBuilder builder = new StringBuilder();
                    while (expression.charAt(j) != ')' && expression.charAt(j) != ' ' && expression.charAt(j)!='\r' && expression.charAt(j)!='\n') {
                        builder.append(expression.charAt(j));
                        j++;
                    }

                    //拼接完成之后的字符串应该就是操作数字符串, 将其压入栈中
                    valueStack.push(builder.toString());

                    //当前的j指向空白符号或者右括号, 将i设置为j-1, 由于循环的最后会递增i, 这样下一次i就会扫描到j指向的位置
                    i = j - 1;
                    break;
            }
        }

        //将结果从B栈中弹出, 此时两个栈应该都为空.
        String result = valueStack.pop().toString();

        //最后检测两个栈, 有一个栈没有弹空就说明表达式有问题, 报异常
        if (valueStack.isEmpty() && operatorStack.isEmpty()) {
            return result;
        } else {
            throw new IllegalArgumentException("表达式有误");
        }
    }


    /**
     * 这个函数用来根据运算符从栈中取出操作数进行计算, 并将结果放入栈中
     * @param operator 单字符的操作符
     * @param valueStack 存放值的栈
     */
    private static void parseSinglePairExpression(char operator, Stack<String> valueStack) {
        //设置一个临时的栈, 用于按照表达式的顺序存放操作数
        Stack<BigDecimal> tempStack = new LinkedListStack<>();

        //同时设置一个统计有几个操作数的变量
        int count = 0;

        //只要栈顶不是左括号, 就反复从B栈中弹出操作数, 然后放到临时栈中, 同时进行计数.
        while (!valueStack.peek().equals("(")) {
            tempStack.push(new BigDecimal(valueStack.pop()));
            count++;
        }
        //然后弹出左括号, 弹出左括号后, 一对括号之间的内容就全部被弹出, 接下来只需要计算出结果, 然后放回B栈中即可.
        valueStack.pop();

        //现在有了所有的按照顺序排列的操作数和操作符, 根据操作符来进行运算.
        //根据操作符进行四种运算, 最后都要将计算结果压入B栈.
        switch (operator) {
            case '+':
                //如果无操作数, 返回0
                if (count == 0) {
                    valueStack.push("0");
                //如果有操作数, 反复弹出结果, 相加即可
                } else {
                    BigDecimal sum = new BigDecimal("0");
                    while (!tempStack.isEmpty()) {
                        sum = sum.add(tempStack.pop());
                    }
                    //将结果压入值栈
                    valueStack.push(sum.toString());
                }
                break;

            case '-':
                //如果没有操作数就报异常
                if (count == 0) {
                    throw new IllegalArgumentException("减法必须至少有一个操作数");
                //如果只有一个操作数就取反
                } else if (count == 1) {
                    valueStack.push(tempStack.pop().negate().toString());
                //如果有两个以上操作数, 不断相减
                } else {
                    BigDecimal start = tempStack.pop();
                    while (!tempStack.isEmpty()) {
                        start = start.subtract(tempStack.pop());
                    }
                    valueStack.push(start.toString());
                }
                break;
            case '*':
                //乘法无操作数返回1
                if (count == 0) {
                    valueStack.push(new BigDecimal("1").toString());
                //至少有一个操作数, 连续相乘即可, 然后将结果字符串压入值栈
                } else {
                    BigDecimal start = tempStack.pop();
                    while (!tempStack.isEmpty()) {
                        start = start.multiply(tempStack.pop());
                    }
                    valueStack.push(start.toString());
                }
                break;

            case '/':
                //除法必须有操作数, 否则报异常
                if (count == 0) {
                    throw new IllegalArgumentException("除法必须至少有一个操作数");
                //仅有一个操作数的话返回1/a
                } else if (count == 1) {
                    BigDecimal result = new BigDecimal("1").divide(tempStack.pop(),2, RoundingMode.HALF_UP);
                    valueStack.push(result.toString());
                //超过两个操作数的情况下, 不断进行除法
                } else {
                    BigDecimal start = tempStack.pop();
                    while (!tempStack.isEmpty()) {
                        start = start.divide(tempStack.pop(),2, RoundingMode.HALF_UP);
                    }
                    valueStack.push(start.toString());
                }
                break;

            //如果操作符不属于上边四种, 就报异常
            default:
                throw new IllegalArgumentException("操作符有误");
        }
    }

}
这里编写了一个私有的静态函数用来从栈中辅助计算, 就让整个过程不那么复杂, 解析表达式放入内容是一个方法, 根据操作符和栈来计算是另外一个方法, 这样比较方便修改错误. 这里测试都通过了, 发现这次对于栈的理解也更深刻了. 解析Lisp稍微麻烦的一点就是操作数的个数不固定,不像中缀表达式必定是两个操作数,但每对括号内就一个操作符又是容易之处,所以解决方案就是把左括号压到值栈里,其他的操作符留在操作符栈里,思路还算比较容易想到,就是类型转换稍微麻烦点。

迷宫寻路

所谓迷宫寻路, 就是一个二维数组当成迷宫, 然后从起点走到终点. 我自己想出来了算法, 竟然就是初级的递归回溯. 算法的核心很简单, 创建一个找迷宫的对象步骤如下:
  1. 首先需要一个二维字符数组作为迷宫, 每一个格子用X表示无法通行, 空格表示没有走过的可以通行的路线. * 表示路径中的路线, a表示走过但是无法通行的路线. 一开始所有格子只有X和空格两种状态.
  2. 然后在构造函数中设置起点和终点, 用一个Point类来表示点, 先行后列. 传入的起点按照行列传入, 在构造Point的时候减去1, 传入实际索引.
  3. 之后将起点Point对象压入栈, 然后开始进行主算法.
  4. 开启一个循环, 只要栈不为空, 就循环如下操作:
    1. 不断获取栈顶的Point对象, 然后按照下右上左的顺序检查相邻是不是为通行点. 只要找到, 就返回这个可用点, 如果没找到, 返回null.
    2. 如果有相邻可用点, 将这个点压入栈中, 然后将这个点对应的坐标设置为*, 表示加入到路径中. 之后立刻判断是不是已经到出口, 如果到出口就结束循环. 否则继续循环, 用新的栈顶的点继续寻找相邻可用的点.
    3. 如果这个点没有相邻可用点, 由于在达到这个点的时候已经进行过出口判断, 说明当前点为死路, 将当前点对应的数组标记为 a, 表示此地可以走动, 但是路不通. 之后最关键的, 将当前点弹出栈, 之后继续循环.
    4. 整个循环就按照这个算法, 当走到死路的时候, 就会回退到之前的节点继续寻找可用点. 如果没有可用路径, 这个算法会一直回退到栈完全为空. 此时循环也会结束
  5. 循环结束之后检查栈, 栈为空则说明无路径可以从入口抵达出口, 如果栈不为空, 则说明找到了一条路径, 之后显示即可.
自己想出了解法, 终于明白了栈的一大好处就是可以进行回溯, 当前条件不满足的时候, 可以处理上一个条件. 详细代码如下, 还是感觉很不错的:
import datastructure.chapter5.LinkedListStack;
import datastructure.chapter5.Stack;
import java.util.Objects;

public class PathFinder {

    private Point start;

    private Point destination;

    //二维字符数组, 作为迷宫
    private char[][] maze;

    //迷宫的行数, 用于判断是否越界
    private int row;

    //迷宫的列数, 用于判断是否越界
    private int column;

    //存放路径的栈
    private Stack<Point> path = new LinkedListStack<>();

    //构造器, 传入迷宫对象, 起点和终点的坐标, 创建起点, 并将起点加入栈中, 将字符数组中起点对应的坐标设置为*
    public PathFinder(char[][] maze, int startX, int startY, int endX, int endY) {
        this.maze = maze;
        this.start = new Point(startX-1, startY-1);
        this.destination = new Point(endX-1, endY-1);
        path.push(start);
        maze[startX-1][startY-1] = '*';
        row = maze.length;
        column = (maze[0]).length;
        System.out.println("迷宫初始化完毕, 有 "+row+" 行, "+ column+" 列.");
        System.out.println("迷宫初始化完毕, 起点是: "+ start);
        System.out.println("迷宫初始化完毕, 终点是: "+ destination);
    }

    //主算法
    //从起点出发, 尝试往一个方向走, 如果可以的话, 将走到的格子加到栈中
    //如果一个格子各个方向都走不通(即所有方向都是路径中, 阻塞, 已经访问, 则将该格子标记为已经访问, 然后将该格子弹出)
    //继续从栈顶尝试往其他方向走.
    //每走一步, 都判定栈顶的点是不是出口, 如果是出口则结束. 如果栈为空, 则说明找不到路径.
    public void findPath() {

        //只要栈不为空
        while (!path.isEmpty()) {
            //尝试寻找栈顶点的相邻可通行点
            Point currentPoint = path.peek();

            Point nextPoint = path.peek().getNextPoint();

            //如果有相邻可通行点, 将可通行点加入path, 同时更改数组的标记
            if (nextPoint != null) {
                path.push(nextPoint);
                maze[nextPoint.x][nextPoint.y] = '*';
                //判断是否为终点, 是终点就结束循环
                if (path.peek().equals(destination)) {
                    break;
                }
            }
            //如果没有相邻可通行点, 说明当前路径不通, 需要将当前路径标记为已经访问, 然后弹出栈.
            else {
                maze[currentPoint.x][currentPoint.y] = 'a';
                path.pop();
            }
        }

        //循环结束之后, 如果栈为空, 说明无路可走, 退回到起点. 栈不空则找到路径
        if (path.isEmpty()) {
            System.out.println("该迷宫没有从起点到终点的路径");
        } else {
            System.out.println("找到一条路径, 用*号表示, a表示该算法曾经探寻过的路线:");
            printMaze();
        }

    }

    private void printMaze() {
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < column; j++) {
                System.out.print(maze[i][j] + " ");
            }
            System.out.println();
        }
    }

    //内部类Point, 将寻找相邻可通行格子的任务交给Point的getNextPoint()方法
    private class Point {
        private int x;
        private int y;

        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Point point = (Point) o;
            return x == point.x &&
                    y == point.y;
        }

        @Override
        public int hashCode() {
            return Objects.hash(x, y);
        }

        //按照下右上左的顺序寻找可通行点
        public Point getNextPoint() {
            //先尝试下方, 最小索引是0, 最大索引是row-1
            // 如果x不是在最底部, 检查x下方坐标的状态, 如果可以通行, 返回那个点
            if (x != row - 1) {
                if (maze[x + 1][y] == ' ') {
                    return new Point(x + 1, y);
                }
            }

            //再尝试右方, 横向最小索引是0, 最大索引是column-1
            if (y != column - 1) {
                if (maze[x][y + 1] == ' ') {
                    return new Point(x, y + 1);
                }
            }

            //再尝试上方, x索引最小为0, 上方最小索引是0
            if (x != 0) {
                if (maze[x - 1][y] == ' ') {
                    return new Point(x - 1, y);
                }
            }

            //最后尝试左方
            if (y != 0) {
                if (maze[x][y - 1] == ' ') {
                    return new Point(x, y - 1);
                }
            }

            //四个方向都走不通, 返回null
            return null;
        }

        @Override
        public String toString() {
            return "Point{" +
                    "x=" + x +
                    ", y=" + y +
                    '}';
        }
    }


    public static void main(String[] args) {


        //7行, 13列的迷宫, 坐标为先行,后列, 起点是 (2,1), 出口是 (3,13)
        char[][] maze = new char[][]{
                {'X', 'X', 'X', 'X', 'X', 'X', 'X', 'X', 'X', 'X', 'X', 'X', 'X'},
                {' ', ' ', ' ', 'X', ' ', ' ', ' ', 'X', 'X', 'X', 'X', ' ', 'X'},
                {'X', 'X', ' ', ' ', ' ', 'X', ' ', ' ', ' ', ' ', 'X', ' ', ' '},
                {'X', 'X', ' ', 'X', 'X', ' ', 'X', ' ', 'X', ' ', ' ', ' ', 'X'},
                {'X', 'X', ' ', ' ', 'X', ' ', ' ', ' ', 'X', ' ', 'X', ' ', 'X'},
                {'X', 'X', ' ', 'X', 'X', 'X', 'X', 'X', ' ', 'X', 'X', ' ', 'X'},
                {'X', 'X', 'X', 'X', 'X', 'X', 'X', 'X', 'X', 'X', 'X', 'X', 'X'}
        };

        PathFinder finder = new PathFinder(maze, 2, 1, 3, 13);

        finder.findPath();

    }

}
好好的用栈写了两个大点的程序, 确实又学到新东西了, 也知道怎么回溯了. 这本书确实不错. 这里还有意思的是, 由于是按照下右上左的顺序来寻路, 如果迷宫出口相对入口在右下方, 偏下的比较多, 先寻找下边效率就高, 如果偏右比较多, 则可以在getNextPoint()修改一下四个if的顺序, 优先寻找右边的路线. 针对文中的例子, 就是优先寻找右侧的路线, 整体尝试的次数会比较少. 如果要进一步优化, 估计就得利用图算法了吧.
LICENSED UNDER CC BY-NC-SA 4.0
Comment