栈 - 简书

1.栈----运算受限的线性表

image.png

栈的习题：

image.png

单目运算符：eg: ++、-- 、~、^ 等。特点是只有一个操作数，例如a++

image.png

注意是两个操作数
后缀表达式求值：

image.png

中缀变成后缀：

image.png

另一个应用：栈与递归是联系在一起的（理解栈的变化，返回地址不太明白）

image.png

解答：

image.png

需要注意四点：
一：规定一个方向行走，例如按ESWN、斜着走等
二：将迷宫使用矩阵表示，通路使用0表示，不通路使用1表示
三：记录每个路是否已经走过，若走过，则不再走
四：若某条路走不通，能回退到上一格，因此需要一个能保存走过的路的容器（即栈）

public interface Question {
    /**
     * 检查括号是否匹配
     * @param s
     * @return
     */
    boolean checkBrackets(String s);

    /**
     *  将十进制数a转换为r(r取[2,9])进制
     * @param a 需要转换的数
     * @param r 基数
     * @return
     */
    int convert(int a,int r);

    /**
     * 计算简单的算数表达式
     * @param str
     * @return
     */
    int CalculationArithmeticExpression(String str);

    /**
     * 输出n个布尔量所有可能的组合
     * @param b
     * @param k
     * @param n
     * @return
     */
    void outputCombinationByBoolean(int[] b,int k,int n);

    /**
     * 深度优先迷宫问题
     * @param maze 迷宫
     * @param move 方向矩阵
     */
    void SeekPath(int[][] maze, int[][] move);
}

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * 栈习题
 */
public class Solution implements Question{

    public static void main(String[] args){
        Solution test=new Solution();
        //   String s="{[((('())(')))]}";
        //  System.out.println(test.checkBrackets(s));

        //    System.out.println(test.convert(3425,8));
        //  String infix="10+(18+9*3)/15-6";
        //   System.out.println(test.CalculationArithmeticExpression(infix));
        // System.out.println(10+(18+9*3)/15-6);
        //      int n=3;
        //    int[] b=new int[n];
        //  int k=0;
        // test.outputCombinationByBoolean(b,k,n);
        int[][] map = {                           //迷宫地图,1代表墙壁，0代表通路
               {1,1,1,1,1,1,1,1,1,1,1,1},   //声明迷宫数组
                {1,0,0,0,0,0,1,0,0,0,1,1},
                {1,1,1,0,1,0,1,0,0,0,0,1},
                {1,1,1,1,1,1,1,1,1,1,1,1},

        };

        int[][] move={{0,1},{1,0},{0,-1},{-1,0}};
        test.SeekPath(map,move);
    }
    /**
     * 检查括号是否匹配
     * @param s
     * @return
     */
    @Override
    public boolean checkBrackets(String s) {
        if(s.length()==0)
            return false;
        //初始化栈
        Stack<Character> stack=new Stack<>();
        char c;
        for(int i=0;i<s.length();){
            c=s.charAt(i);
            //跳过单引号和双引号中间的内容
            if(((int)c)==39){
                //跳过单引号包含的内容
                i++;
                while ((c=s.charAt(i))!=39){
                    i++;
                }
                i++;
            }else if(((int)c)==34){
                //跳过双引号
                i++;
                while ((c=s.charAt(i))!=34){
                    i++;
                }
                i++;
            }else {
                switch (c) {
                    case '(':
                        stack.push(c);
                        i++;
                        break;
                    case '{':
                        stack.push(c);
                        i++;
                        break;
                    case '[':
                        stack.push(c);
                        i++;
                        break;
                    case ')':
                        if(stack.peek()=='('){
                            stack.pop();
                            i++;
                            break;
                        }else {
                            return false;
                        }
                    case '}':
                        if(stack.peek()=='{'){
                            stack.pop();
                            i++;
                            break;
                        }else {
                            return false;
                        }
                    case ']':
                        if(stack.peek()=='['){
                            stack.pop();
                            i++;
                            break;
                        }else {
                            return false;
                        }
                }
            }
        }
        if(stack.isEmpty())
            return true;
        return false;
    }

    /**
     * 将十进制数a转换为r(r取[2,9])进制
     * @param a 需要转换的数
     * @param r 基数
     * @return
     */
    @Override
    public int convert(int a, int r) {
        if(r<2 || r>9 || a<0)
            return -1;
        //初始化
        Stack<Integer> stack=new Stack<>();
        //商
        int quo;
        //余数
        int remainder;
        while ((quo=a/r)!=0){
            remainder=a%r;
            stack.push(remainder);
            a=quo;
        }
        //压入最后一项商等于0的余数
        remainder=a%r;
        stack.push(remainder);

        StringBuilder s=new StringBuilder();
        while (!stack.isEmpty()){
            s.append(stack.pop());
        }
        return Integer.parseInt(s.toString());
    }

    /**
     * 计算简单的算数表达式
     * 仅包含+、-、*、/
     * @param str
     * @return
     */
    @Override
    public int CalculationArithmeticExpression(String str) {
        //为简单起见，将str转为List
        List<String> list=new ArrayList<>();
        convertList(list,str);
        List<String> suffixList=infixChangedToSuffix(list);
        //负责计算
        Stack<Integer> stack=new Stack<>();
        String item;
        for(int i=0;i<suffixList.size();i++){
            item=suffixList.get(i);
            if(isNum(item)){
                stack.push(Integer.parseInt(item));
            }else {
                Integer v2=stack.pop();
                Integer v1=stack.pop();
                //注意运算的顺序
                if(item.equals(PriorityOperators.ADD.getOperators())){
                    stack.push(v1+v2);
                }else if(item.equals(PriorityOperators.SUBTRACT.getOperators())){
                    stack.push(v1-v2);
                }else if(item.equals(PriorityOperators.MULTIPLY.getOperators())){
                    stack.push(v1*v2);
                }else if(item.equals(PriorityOperators.DIVIDE.getOperators())){
                    stack.push(v1/v2);
                }
            }
        }
        return stack.pop();
    }

    /**
     * 将中缀表达式转换为List
     * @param list
     * @param str
     */
    private void convertList(List<String> list, String str) {
        int i=0;
        int start;
        while (i<str.length()){
            if(isNum(String.valueOf(str.charAt(i)))){
                start=i;
                while (i<str.length() && isNum(String.valueOf(str.charAt(i)))){
                    i++;
                }
                list.add(str.substring(start,i));
            }else {
                list.add(String.valueOf(str.charAt(i)));
                i++;
            }

        }
    }

    /**
     * 判断是否是数字
     * @param s
     * @return
     */
    private boolean isNum(String s) {
        try{
            Integer.parseInt(s);
            return true;
        }catch (Exception e){
            return false;
        }
    }

    /**
     * 为了方便计算机进行计算，只支持数字的简单计算
     * 将中缀表达式转换为后缀表达式
     * @param s1 中缀表达式
     * @return
     */
    private List<String> infixChangedToSuffix(List<String> s1){
        //负责装后缀表达式
        List<String> s2=new ArrayList<>();
        //负责装运算符，运算符有优先级
        Stack<PriorityOperators> r=new Stack<>();
        String c;
        int index=0;
        while (index<s1.size()){
            c=s1.get(index);
            if(isNum(c)){
                //数字
                s2.add(c);
            }else if(!c.equals(PriorityOperators.RIGHT.getOperators())){
                //运算符(除了右括号)，则压栈,压栈前需判断优先级
                if(r.isEmpty()){
                    if(PriorityOperators.ADD.getOperators().equals(c)){
                        r.push(PriorityOperators.ADD);
                    }else if(PriorityOperators.SUBTRACT.getOperators().equals(c)){
                        r.push(PriorityOperators.SUBTRACT);
                    }else if(PriorityOperators.MULTIPLY.getOperators().equals(c)){
                        r.push(PriorityOperators.MULTIPLY);
                    }else if(PriorityOperators.DIVIDE.getOperators().equals(c)){
                        r.push(PriorityOperators.DIVIDE);
                    }else {
                        r.push(PriorityOperators.LEFT);
                    }
                }else {
                    //判断当前的运算符优先级与栈顶运算符优先级
                    if(PriorityOperators.ADD.getOperators().equals(c)){
                        if(PriorityOperators.ADD.getPriority()>r.peek().getPriority()){
                            //当前优先级大于栈顶元素优先级，则直接压栈
                            r.push(PriorityOperators.ADD);
                        }else {
                           //弹栈，直到当前当前优先级大于栈顶元素优先级,才结束循环
                            while (!r.isEmpty() && (PriorityOperators.ADD.getPriority()<r.peek().getPriority())){
                                s2.add(r.pop().getOperators());
                            }
                            r.push(PriorityOperators.ADD);
                        }
                    }else if(PriorityOperators.SUBTRACT.getOperators().equals(c)){
                        if(PriorityOperators.SUBTRACT.getPriority()>r.peek().getPriority()){
                            //当前优先级大于栈顶元素优先级，则直接压栈
                            r.push(PriorityOperators.SUBTRACT);
                        }else {
                            //弹栈，直到当前当前优先级大于栈顶元素优先级
                            while (!r.isEmpty() && (PriorityOperators.SUBTRACT.getPriority()<r.peek().getPriority())){
                                s2.add(r.pop().getOperators());
                            }
                            r.push(PriorityOperators.SUBTRACT);
                        }

                    }else if(PriorityOperators.MULTIPLY.getOperators().equals(c)){
                        if(PriorityOperators.MULTIPLY.getPriority()>r.peek().getPriority()){
                            //当前优先级大于栈顶元素优先级，则直接压栈
                            r.push(PriorityOperators.MULTIPLY);
                        }else {
                            //弹栈，直到当前当前优先级大于栈顶元素优先级
                            while (!r.isEmpty() && (PriorityOperators.MULTIPLY.getPriority()<r.peek().getPriority())){
                                s2.add(r.pop().getOperators());
                            }
                            r.push(PriorityOperators.MULTIPLY);
                        }

                    }else if(PriorityOperators.DIVIDE.getOperators().equals(c)){
                        if(PriorityOperators.DIVIDE.getPriority()>r.peek().getPriority()){
                            //当前优先级大于栈顶元素优先级，则直接压栈
                            r.push(PriorityOperators.DIVIDE);
                        }else {
                            //弹栈，直到当前当前优先级大于栈顶元素优先级
                            while (!r.isEmpty() && (PriorityOperators.DIVIDE.getPriority()<r.peek().getPriority())){
                                s2.add(r.pop().getOperators());
                            }
                            r.push(PriorityOperators.DIVIDE);
                        }
                    }else {
                        //左括号
                        r.push(PriorityOperators.LEFT);
                    }
                }
            }else {
                //遇到右括号，出栈，直到左括号
                while (!r.isEmpty() && (!r.peek().getOperators().equals(PriorityOperators.LEFT.getOperators()))){
                    s2.add(r.pop().getOperators());
                }
                if(!r.isEmpty())
                    //弹出左括号
                    r.pop();

            }
            index++;
        }
        while (!r.isEmpty())
            s2.add(r.pop().getOperators());
        return s2;
    }

    @Override
    public void outputCombinationByBoolean(int[] b,int k,int n) {
        if(k==n){
            System.out.print(Arrays.toString(b));
        }else {
            b[k]=1; outputCombinationByBoolean(b,k+1,n);
            b[k]=0; outputCombinationByBoolean(b,k+1,n);
        }
    }
    /**
     * 深度优先搜索迷宫问题（回溯、递归思路都一样）
     * @param maze 迷宫
     * @param move 方向矩阵
     *  核心思想类似于双指针，例如：
    下标 0,1,2,3,4,5,6,7,8,9,10,11
     * 0{1,1,1,1,1,1,1,1,1,1,1,1},
     * 1{1,0,0,0,0,0,1,0,0,0,1,1},
     * 2{1,1,1,0,1,0,1,0,0,0,0,1},
     * 3{1,1,1,1,1,1,1,1,1,1,1,1}
     *  过程是：一个指针p指向当前点，即（x,y），另一个指针q指向当前点的d方向上的点，即（g,h）
     *  初始情况：x=1,y=1,d=0,因为(1,1)在0方向的点是(1,2)，即g=1,h=2，maze[g][h]!=1 && mark[g][h]!=1 =>(1,2)可达
     *  因此将(1,1,0)压栈；当前点向后挪一位，且将d赋值为0，即（x=g;y=h;d=0;）,之后同理
     *  压栈过程：(1,1,0)-->(1,2,0)-->(1,3,0)-->(1,4,0)-->(1,5,1),注意（2,5，d）点(q指针指向的点)不压栈,因为d=0,1,2,3都不可达
     *  当都不可达（q指针指向的点）时，弹栈（p指针指向的点）,即弹出(1,5,1)，d++,即d=2,换个方向重复上述过程
     */
    @Override
    public void SeekPath(int[][] maze,int[][] move) {
        if (maze==null || move==null)
            return;

        int m=maze.length-1;
        int n=maze[0].length-1;
        //用于标记节点是否已经访问过,访问过则标记1
        int[][] mark=new int[m+1][n+1];
        //用于存放走过的路径
        Stack<Node> stack=new Stack<>();

        //初始点默认是没有方向的（因为d=-1）
        stack.push(new Node(1,1,-1));

        //因为maze外围会人为增加墙，所以初始点是（1,1）
        //增加墙的原因是避免判断边界，代码具有统一性
        mark[1][1]=1;
       //核心思想是：类似于双指针，例如，当前点(1,1)以方向0出发，
       //下一点是(1,2)，若可达，则把(1,1,0)压栈
       //若(1,2)不可达，说明(1,1)点的0方向不可达，则d++，尝试1方向
       //若4个方向都不可达，则当前点弹栈，d++，换个方向继续尝试
        Node root;
        while (!stack.isEmpty()){
             //当前点的4个方向都不可达(即d<0或d>3)，弹出当前点
             root=stack.pop();
            //d++，换个方向继续尝试
             int x=root.getX(), y=root.getY(), d=root.getDirection()+1;
             while (d<4){
                 if((x==(m-1)) && y==(n-1)){
                     //出口，输出一条路径
                     System.out.println(x+","+y);
                     Node h;
                     while (!stack.isEmpty()){
                         h=stack.pop();
                         System.out.println(h.getX()+","+h.getY());
                     }
                     return;
                 }
                 //maze[x][y]是当前点，maze[g][h]是当前点(maze[x][y])在d方向上的点
                 int g=x+move[d][0],h=y+move[d][1];
                  //用于判断当前节点d方向的后一个节点是否可达
                 if(maze[g][h]==0 && mark[g][h]==0){
                     //若可达
                     mark[g][h]=1;
                    //压入当前节点和方向d(d的方向其实是maze[g][h]相对于maze[x][y]的方向)
                     stack.push(new Node(x,y,d));
                     x=g;y=h;d=0;
                 }else {
                     //maze[g][h]不可达，则换个方向测试
                       d++;
                 }
             }
        }
        System.out.println("no path");
    }



    /**
     * 用于封装迷宫的结点
     */
    static class Node{
        /**
         * 横坐标
         */
        private int x=-1;
        /**
         * 纵坐标
         */
        private int y=-1;
        /**
         * 方向,取值0,1,2,3，分别表示E、S、W、N
         */
        private int direction=-1;


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

        public int getX() {
            return x;
        }

        public int getY() {
            return y;
        }

        public int getDirection() {
            return direction;
        }


        public void setX(int x) {
            this.x = x;
        }

        public void setY(int y) {
            this.y = y;
        }

        public void setDirection(int direction) {
            this.direction = direction;
        }


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

    }

    /**
     * 封装有优先级的运算符
     * 优先级：
     * +  2
     * -  1
     * *  4
     * /  3
     */
    enum PriorityOperators{
        ADD("+",2),
        SUBTRACT("-",1),
        MULTIPLY("*",4),
        DIVIDE("/",3),
        LEFT("(",0),
        RIGHT(")",0);
        //运算符
        private String operators;
        //优先级
        private int priority;

        PriorityOperators(String operators, int priority) {
            this.operators = operators;
            this.priority = priority;
        }

        public String getOperators() {
            return operators;
        }

        public int getPriority() {
            return priority;
        }
    }
}