[数据结构与算法] 邂逅栈

怼烎@ 2023-06-29 11:59 25阅读 0赞

### 栈的相关用法 ###

*   *  需求介绍
     *  栈的介绍
     *   *  利用数组实现栈
         *  栈实现综合计算器
         *   *  前缀表达式(波兰表达式)
             *  中缀表达式
             *  后缀表达式
     *  递归
     *   *  递归使用的场景
         *  递归原则
         *   *  递归实现迷宫问题
         *  8皇后问题

> 在邂逅了完线性结构的数组和队列后, 我们便偶遇了栈这个东东, 他到底是个啥?  
> 就让我们慢慢揭开它的神秘面纱吧~~~

## 需求介绍 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMzcxNTU2_size_16_color_FFFFFF_t_70]

## 栈的介绍 ##

**[栈的英文为(stack)][stack]:  又名堆栈，它是一种运算受限的线性表。限定仅在表尾(栈顶)进行插入和删除操作的线性表**

*  栈是一个**先入后出**(FILO-First In Last Out)的有序列表。
 *  栈(stack)是**限制**线性表中元素的**插入和删除**只能在线性表的同一端进行的一种特殊线性表。允许插入和删除的一端，为变化的一端，称为栈顶(Top)，另一端为固定的一端，称为栈底(Bottom)。
 *  根据栈的定义可知，最先放入栈中元素在栈底，最后放入的元素在栈顶，而删除元素刚好相反，最后放入的元素最先删除，最先放入的元素最后删除

**入栈图示**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMzcxNTU2_size_16_color_FFFFFF_t_70 1]  
**出栈图示**  
![在这里插入图片描述][20200112204535829.png]

**栈的应用场景**

*  **子程序的调用**：在跳往子程序前，会先将下个指令的地址存到堆栈中，直到子程序执行完后再将地址取出，以回到原来的程序中。
 *  **处理递归调用**：和子程序的调用类似，只是除了储存下一个指令的地址外，也将参数、区域变量等数据存入堆栈中。
 *  **表达式的转换**\[中缀表达式转后缀表达式\] **与求值** (实际解决)。
 *  **二叉树的遍历**。
 *  图形的**深度优先**(depth一first)搜索法。

### 利用数组实现栈 ###

**思路图**

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMzcxNTU2_size_16_color_FFFFFF_t_70 2]  
**代码实现**

/** * 数组模拟栈 * * @author TimePause * @create 2020-01-12 14:19 */
    public class ArrayStackDemo { 
        public static void main(String[] args) { 
            // 创建一个存放4个数据的栈
            ArrayStack stack = new ArrayStack(4);
            // 创建用于读取键盘输入
            Scanner scanner = new Scanner(System.in);
            // 记录键盘输入的内容
            String key = "";
            // 表示是否结束界面的循环选择
            boolean loop = true;
            // 循环显示页面,并执行相关操作
            while (loop) { 
                //页面显示
                System.out.println("输入pop: 执行入栈操作");
                System.out.println("输入push: 执行出栈操作");
                System.out.println("输入list: 显示栈中元素");
                System.out.println("输入exit: 退出");
                System.out.println("请输入你的选择");
                //输入的数据
                key = scanner.next();
                switch (key) { 
                    case "pop":
                        stack.pop();
                        break;
                    case "push":
                        //因为入栈方法中抛出了一个异常, 因此在这里使用try..catch..处理一下
                        try { 
                            System.out.println("请输入入栈的元素");
                            int i = scanner.nextInt();
                            stack.push(i);
                        }catch (Exception e){ 
                            System.out.println(e.getMessage());
                        }
                        break;
                    case "list":
                        stack.showArrayStack();
                        break;
                    case "exit":
                        loop=false;
                        break;
                    default:
                        System.out.println("命令不正确,请重新输入");
                        break;
                }
                System.out.println("欢迎下次使用~~~");
            }
        }
    
    
    }
    
    class ArrayStack { 
        private int maxSize;//栈大小
        private int[] stack;//数组,用来模拟栈,存放数据
        private int top = -1;//top表示栈顶,初始化为-1
    
        /** * 构造方法 */
        public ArrayStack(int maxSize) { 
            this.maxSize = maxSize;
            this.stack = new int[maxSize];//该数组范围:0 -> maxSzie-1
        }
    
        /** * 栈空 */
        public boolean isEmpty() { 
            return top == -1;//栈顶值等于初始化值,说明栈为空
        }
    
        /** * 栈满 */
        public boolean isFull() { 
            return top == maxSize - 1;
        }
    
        /** * 入栈/压栈 */
        public void push(int value) { 
            // 判断是否满
            if (isFull()) { 
                throw new RuntimeException("栈满,无法入栈");
            }
            //只要top独处一行,那么无论top++还是++top,下面获取的都是自增后的数据
            top++;
            // 栈顶指针先自增
            stack[top] = value;
        }
    
        /** * 出栈/弹出 */
        public void pop() { 
            // 判空
            if (isEmpty()) { 
                System.out.println("栈空,无法弹出更多元素了...");
                return;
            }
            //1.显示当前栈顶元素 2.栈顶指针下移
            int pop = stack[top--];
            System.out.println("当前出栈元素为:" + pop);
        }
    
        /** * 遍历显示栈中元素 */
        public void showArrayStack() { 
            //判空
            if (isEmpty()) { 
                System.out.println("栈空,无法显示更多元素...");
            }
            //遍历模拟栈的数组
            for (int i = top; i >= 0; i--) { 
                System.out.printf("stack[%d]=%d\n", i, stack[i]);
            }
        }
    
    }

### 栈实现综合计算器 ###

**逻辑图**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMzcxNTU2_size_16_color_FFFFFF_t_70 3]

**实现代码**

public class Calculator { 
    
        public static void main(String[] args) { 
            //根据前面思路，完成表达式的运算
            String expression = "7*2*2-5+1-5+3-4"; //如何处理多位数的问题？
            //创建两个栈，一个数栈，一个符号栈
            ArrayStack2 numStack = new ArrayStack2(10);
            ArrayStack2 operStack = new ArrayStack2(10);
            //定义需要的相关变量
            int index = 0;//用于扫描表达式
            int num1 = 0;
            int num2 = 0;
            int oper = 0;
            int res = 0;
            char ch = ' '; //将每次扫描得到char保存到ch
            String keepNum = ""; //==>b.用于拼接 多位数
            //开始while循环的扫描expression
            while (true) { 
                //依次得到expression 的每一个字符==>这里只能处理一位数
                ch = expression.substring(index, index + 1).charAt(0);//substring处理得到的是一个string类型, 需要使用charAt转换成char类型
                //判断ch是什么，然后做相应的处理
                if (operStack.isOper(ch)) { //如果是运算符
                    //判断当前的符号栈是否为空
                    if (!operStack.isEmpty()) { 
                        //如果符号栈有操作符，就进行比较,如果当前的操作符的优先级小于或者等于栈中的操作符,就需要从数栈中pop出两个数,
                        //在从符号栈中pop出一个符号，进行运算，将得到结果，入数栈，然后将当前的操作符入符号栈
                        if (operStack.priority(ch) <= operStack.priority(operStack.peek())) { 
                            num1 = numStack.pop();
                            num2 = numStack.pop();
                            oper = operStack.pop();
                            res = numStack.cal(num1, num2, oper);
                            //把运算的结果入数栈
                            numStack.push(res);
                            //然后将当前的操作符入符号栈
                            operStack.push(ch);
                        } else { 
                            //如果当前的操作符的优先级大于栈中的操作符， 就直接入符号栈.
                            operStack.push(ch);
                        }
                    } else { 
                        //如果为空直接入符号栈..
                        operStack.push(ch); // 1 + 3
                    }
                } else {  //如果是数，则直接入数栈
                    //numStack.push(ch - 48); //? eg: 我们扫描的 "1+3" 中的 '1' 代表的是ascall是49 而不是数字 1
    
                    //a.分析思路
                    //1. 当处理多位数时，不能发现是一个数就立即入栈，因为他可能是多位数
                    //2. 在处理数，需要向expression的表达式的index 后再看一位,如果是数就进行扫描，如果是符号才入栈
                    //3. 因此我们需要定义一个变量 字符串，用于拼接
    
                    //c.处理多位数
                    keepNum += ch;
    
                    //e.如果ch已经是expression的最后一位，就直接入栈
                    if (index == expression.length() - 1) { 
                        numStack.push(Integer.parseInt(keepNum));
                    } else { 
    
                        //d.判断下一个字符是不是数字，如果是数字，就继续扫描，如果是运算符，则入栈
                        //注意是看后一位，不是index++
                        if (operStack.isOper(expression.substring(index + 1, index + 2).charAt(0))) { 
                            //如果后一位是运算符，则入栈 keepNum = "1" 或者 "123"
                            numStack.push(Integer.parseInt(keepNum));//将String的substring转换成int类型
                            //重要的!!!!!!, keepNum清空
                            keepNum = "";
                        }
                    }
                }
                //让index + 1, 并判断是否扫描到expression最后.
                index++;
                if (index >= expression.length()) { 
                    break;
                }
            }
    
            //当表达式扫描完毕，就顺序的从 数栈和符号栈中pop出相应的数和符号，并运行.
            while (true) { 
                //如果符号栈为空，则计算到最后的结果, 数栈中只有一个数字【结果】
                if (operStack.isEmpty()) { 
                    break;
                }
                num1 = numStack.pop();
                num2 = numStack.pop();
                oper = operStack.pop();
                res = numStack.cal(num1, num2, oper);
                numStack.push(res);//将运算好的数据入栈
            }
            //将数栈的最后数，pop出，就是结果
            int res2 = numStack.pop();
            System.out.printf("表达式 %s = %d", expression, res2);
        }
    
    }
    
    //先创建一个栈,直接使用前面创建好
    //定义一个 ArrayStack2 表示栈, 需要扩展功能
    class ArrayStack2 { 
        private int maxSize; // 栈的大小
        private int[] stack; // 数组，数组模拟栈，数据就放在该数组
        private int top = -1;// top表示栈顶，初始化为-1
    
        //构造器
        public ArrayStack2(int maxSize) { 
            this.maxSize = maxSize;
            stack = new int[this.maxSize];
        }
    
        //增加一个方法，可以返回当前栈顶的值, 但是不是真正的pop
        public int peek() { 
            return stack[top];
        }
    
        //栈满
        public boolean isFull() { 
            return top == maxSize - 1;
        }
    
        //栈空
        public boolean isEmpty() { 
            return top == -1;
        }
    
        //入栈-push
        public void push(int value) { 
            //先判断栈是否满
            if (isFull()) { 
                System.out.println("栈满");
                return;
            }
            top++;
            stack[top] = value;
        }
    
        //出栈-pop, 将栈顶的数据返回
        public int pop() { 
            //先判断栈是否空
            if (isEmpty()) { 
                //抛出异常
                throw new RuntimeException("栈空，没有数据~");
            }
            int value = stack[top];
            top--;
            return value;
        }
    
        //显示栈的情况[遍历栈]， 遍历时，需要从栈顶开始显示数据
        public void list() { 
            if (isEmpty()) { 
                System.out.println("栈空，没有数据~~");
                return;
            }
            //需要从栈顶开始显示数据
            for (int i = top; i >= 0; i--) { 
                System.out.printf("stack[%d]=%d\n", i, stack[i]);
            }
        }
    
        //返回运算符的优先级，优先级是程序员来确定, 优先级使用数字表示
        //数字越大，则优先级就越高.
        public int priority(int oper) { 
            if (oper == '*' || oper == '/') { 
                return 1;
            } else if (oper == '+' || oper == '-') { 
                return 0;
            } else { 
                return -1; // 假定目前的表达式只有 +, - , * , /
            }
        }
    
        //判断是不是一个运算符
        public boolean isOper(char val) { 
            return val == '+' || val == '-' || val == '*' || val == '/';
        }
    
        //计算方法
        public int cal(int num1, int num2, int oper) { 
            int res = 0; // res 用于存放计算的结果
            switch (oper) { 
                case '+':
                    res = num1 + num2;
                    break;
                case '-':
                    res = num2 - num1;// 注意顺序
                    break;
                case '*':
                    res = num1 * num2;
                    break;
                case '/':
                    res = num2 / num1;
                    break;
                default:
                    break;
            }
            return res;
        }
    
    }

**测试结果**

![在这里插入图片描述][20200113165223596.png]

![在这里插入图片描述][20200113165411754.png]

#### 前缀表达式(波兰表达式) ####

*  前缀表达式又称**波兰式，前缀表达式的运算符位于操作数之前**
 *  举例说明： (3+4)×5-6 对应的前缀表达式就是 - × + 3 4 5 6

**前缀表达式的计算机求值**

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

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

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

#### 中缀表达式 ####

*  中缀表达式就是常见的运算表达式，如(3+4)×5-6
 *  中缀表达式的求值是我们**人最熟悉的，但是对计算机来说却不好操作**(前面我们讲的案例就能看的这个问题)，因此，**在计算结果时，往往会将中缀表达式转成其它表达式来操作(一般转成后缀表达式.)**

#### 后缀表达式 ####

*  后缀表达式又称**逆波兰表达式,与前缀表达式相似，只是运算符位于操作数之后**
 *  举例说明： (3+4)×5-6 对应的后缀表达式就是 3 4 + 5 × 6 –

![在这里插入图片描述][20200113211308315.png]

**中缀转后缀表达式的计算机求值**

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

例如: **(3+4)×5-6 对应的后缀表达式就是 3 4 + 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), 计算其结果
 *  支持小括号和多位数整数，因为这里我们主要讲的是数据结构，因此计算器进行简化，只支持对整数的计算。
 *  思路分析
 *  代码完成

**中缀转后缀**

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

**具体步骤如下:**

*  初始化两个栈：运算符栈s1和储存中间结果的栈s2；
 *  从左至右扫描中缀表达式；
 *  遇到操作数时，将其压s2；
 *  遇到运算符时，比较其与s1栈顶运算符的优先级：  
    如果s1为空，或栈顶运算符为左括号“(”，则直接将此运算符入栈；  
    否则，若优先级比栈顶运算符的高，也将运算符压入s1；  
    否则，将s1栈顶的运算符弹出并压入到s2中，再次转到(4-1)与s1中新的栈顶运算符相比较；
 *  遇到括号时：  
    (1) 如果是左括号“(”，则直接压入s1  
    (2) 如果是右括号“)”，则依次弹出s1栈顶的运算符，并压入s2，直到遇到左括号为止，此时将这一对括号丢弃
 *  重复步骤2至5，直到表达式的最右边
 *  将s1中剩余的运算符依次弹出并压入s2
 *  依次弹出s2中的元素并输出，结果的逆序即为中缀表达式对应的后缀表达式

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMzcxNTU2_size_16_color_FFFFFF_t_70 4]

代码实现

package ah.sz.tp.algorithm1.stack;
    
    import java.util.ArrayList;
    import java.util.List;
    import java.util.Stack;
    
    /** *中缀转后缀表达式 * * @author TimePause * @create 2020-01-14 19:07 */
    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] =》 ArrayList [1,2,3,+,4,*,+,5,–]
    
    		String expression = "1+((2+3)*4)-5";//注意表达式
    		List<String> infixExpressionList = toInfixExpressionList(expression);
    		System.out.println("中缀表达式对应的List=" + infixExpressionList); // ArrayList [1,+,(,(,2,+,3,),*,4,),-,5]
    		List<String> suffixExpreesionList = parseSuffixExpreesionList(infixExpressionList);
    		System.out.println("后缀表达式对应的List" + suffixExpreesionList); //ArrayList [1,2,3,+,4,*,+,5,–]
    
    		System.out.printf("expression=%d", calculate(suffixExpreesionList)); // ?
    
    
    
    		/* //先定义给逆波兰表达式 //(30+4)×5-6 => 30 4 + 5 × 6 - => 164 // 4 * 5 - 8 + 60 + 8 / 2 => 4 5 * 8 - 60 + 8 2 / + //测试 //说明为了方便，逆波兰表达式 的数字和符号使用空格隔开 //String suffixExpression = "30 4 + 5 * 6 -"; String suffixExpression = "4 5 * 8 - 60 + 8 2 / +"; // 76 //思路 //1. 先将 "3 4 + 5 × 6 - " => 放到ArrayList中 //2. 将 ArrayList 传递给一个方法，遍历 ArrayList 配合栈 完成计算 List<String> list = getListString(suffixExpression); System.out.println("rpnList=" + list); int res = calculate(list); System.out.println("计算的结果是=" + res); */
    	}
    
    
    
    	//即 ArrayList [1,+,(,(,2,+,3,),*,4,),-,5] =》 ArrayList [1,2,3,+,4,*,+,5,–]
    	//方法：将得到的中缀表达式对应的List => 后缀表达式对应的List
    	public static List<String> parseSuffixExpreesionList(List<String> ls) { 
    		//定义两个栈
    		Stack<String> s1 = new Stack<String>(); // 符号栈
    		//说明：因为s2 这个栈，在整个转换过程中，没有pop操作，而且后面我们还需要逆序输出
    		//因此比较麻烦，这里我们就不用 Stack<String> 直接使用 List<String> s2
    		//Stack<String> s2 = new Stack<String>(); // 储存中间结果的栈s2
    		List<String> s2 = new ArrayList<String>(); // 储存中间结果的Lists2
    
    		//遍历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, 因此按顺序输出就是对应的后缀表达式对应的List
    
    	}
    
    	//方法：将 中缀表达式转成对应的List
    	// s="1+((2+3)×4)-5";
    	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 置成"" '0'[48]->'9'[57]
    				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<String>();
    		// 遍历 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("不存在该运算符" + operation);
    				break;
    		}
    		return result;
    	}
    
    }

结果展示  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMzcxNTU2_size_16_color_FFFFFF_t_70 5]

**完整版的逆波兰计算器，功能包括**

*  支持 + - \* / ( )
 *  多位数，支持小数,
 *  兼容处理, 过滤任何空白字符，包括空格、制表符、换页符

逆波兰计算器完整版考虑的因素较多，下面给出完整版代码供同学们学习，其基本思路和前面一样，也是使用到：中缀表达式转后缀表达式。

public class ReversePolishMultiCalc { 
    
        /** * 匹配 + - * / ( ) 运算符 */
        static final String SYMBOL = "\\+|-|\\*|/|\$|\$";
    
        static final String LEFT = "(";
        static final String RIGHT = ")";
        static final String ADD = "+";
        static final String MINUS= "-";
        static final String TIMES = "*";
        static final String DIVISION = "/";
    
        /** * 加減 + - */
        static final int LEVEL_01 = 1;
        /** * 乘除 * / */
        static final int LEVEL_02 = 2;
    
        /** * 括号 */
        static final int LEVEL_HIGH = Integer.MAX_VALUE;
    
    
        static Stack<String> stack = new Stack<>();
        static List<String> data = Collections.synchronizedList(new ArrayList<String>());
    
        /** * 去除所有空白符 * @param s * @return */
        public static String replaceAllBlank(String s ){ 
            // \\s+ 匹配任何空白字符，包括空格、制表符、换页符等等, 等价于[ \f\n\r\t\v]
            return s.replaceAll("\\s+","");
        }
    
        /** * 判断是不是数字 int double long float * @param s * @return */
        public static boolean isNumber(String s){ 
            Pattern pattern = Pattern.compile("^[-\\+]?[.\\d]*$");
            return pattern.matcher(s).matches();
        }
    
        /** * 判断是不是运算符 * @param s * @return */
        public static boolean isSymbol(String s){ 
            return s.matches(SYMBOL);
        }
    
        /** * 匹配运算等级 * @param s * @return */
        public static int calcLevel(String s){ 
            if("+".equals(s) || "-".equals(s)){ 
                return LEVEL_01;
            } else if("*".equals(s) || "/".equals(s)){ 
                return LEVEL_02;
            }
            return LEVEL_HIGH;
        }
    
        /** * 匹配 * @param s * @throws Exception */
        public static List<String> doMatch (String s) throws Exception{ 
            if(s == null || "".equals(s.trim())) throw new RuntimeException("data is empty");
            if(!isNumber(s.charAt(0)+"")) throw new RuntimeException("data illeagle,start not with a number");
    
            s = replaceAllBlank(s);
    
            String each;
            int start = 0;
    
            for (int i = 0; i < s.length(); i++) { 
                if(isSymbol(s.charAt(i)+"")){ 
                    each = s.charAt(i)+"";
                    //栈为空，(操作符，或者 操作符优先级大于栈顶优先级 && 操作符优先级不是( )的优先级 及是 ) 不能直接入栈
                    if(stack.isEmpty() || LEFT.equals(each)
                            || ((calcLevel(each) > calcLevel(stack.peek())) && calcLevel(each) < LEVEL_HIGH)){ 
                        stack.push(each);
                    }else if( !stack.isEmpty() && calcLevel(each) <= calcLevel(stack.peek())){ 
                        //栈非空，操作符优先级小于等于栈顶优先级时出栈入列，直到栈为空，或者遇到了(，最后操作符入栈
                        while (!stack.isEmpty() && calcLevel(each) <= calcLevel(stack.peek()) ){ 
                            if(calcLevel(stack.peek()) == LEVEL_HIGH){ 
                                break;
                            }
                            data.add(stack.pop());
                        }
                        stack.push(each);
                    }else if(RIGHT.equals(each)){ 
                        // ) 操作符，依次出栈入列直到空栈或者遇到了第一个)操作符，此时)出栈
                        while (!stack.isEmpty() && LEVEL_HIGH >= calcLevel(stack.peek())){ 
                            if(LEVEL_HIGH == calcLevel(stack.peek())){ 
                                stack.pop();
                                break;
                            }
                            data.add(stack.pop());
                        }
                    }
                    start = i ;    //前一个运算符的位置
                }else if( i == s.length()-1 || isSymbol(s.charAt(i+1)+"") ){ 
                    each = start == 0 ? s.substring(start,i+1) : s.substring(start+1,i+1);
                    if(isNumber(each)) { 
                        data.add(each);
                        continue;
                    }
                    throw new RuntimeException("data not match number");
                }
            }
            //如果栈里还有元素，此时元素需要依次出栈入列，可以想象栈里剩下栈顶为/，栈底为+，应该依次出栈入列，可以直接翻转整个stack 添加到队列
            Collections.reverse(stack);
            data.addAll(new ArrayList<>(stack));
    
            System.out.println(data);
            return data;
        }
    
        /** * 算出结果 * @param list * @return */
        public static Double doCalc(List<String> list){ 
            Double d = 0d;
            if(list == null || list.isEmpty()){ 
                return null;
            }
            if (list.size() == 1){ 
                System.out.println(list);
                d = Double.valueOf(list.get(0));
                return d;
            }
            ArrayList<String> list1 = new ArrayList<>();
            for (int i = 0; i < list.size(); i++) { 
                list1.add(list.get(i));
                if(isSymbol(list.get(i))){ 
                    Double d1 = doTheMath(list.get(i - 2), list.get(i - 1), list.get(i));
                    list1.remove(i);
                    list1.remove(i-1);
                    list1.set(i-2,d1+"");
                    list1.addAll(list.subList(i+1,list.size()));
                    break;
                }
            }
            doCalc(list1);
            return d;
        }
    
        /** * 运算 * @param s1 * @param s2 * @param symbol * @return */
        public static Double doTheMath(String s1,String s2,String symbol){ 
            Double result ;
            switch (symbol){ 
                case ADD : result = Double.valueOf(s1) + Double.valueOf(s2); break;
                case MINUS : result = Double.valueOf(s1) - Double.valueOf(s2); break;
                case TIMES : result = Double.valueOf(s1) * Double.valueOf(s2); break;
                case DIVISION : result = Double.valueOf(s1) / Double.valueOf(s2); break;
                default : result = null;
            }
            return result;
    
        }
    
        public static void main(String[] args) { 
            //String math = "9+(3-1)*3+10/2";
            String math = "12.8 + (2 - 3.55)*4+10/5.0";
            try { 
                doCalc(doMatch(math));
            } catch (Exception e) { 
                e.printStackTrace();
            }
        }
    
    }

**运行结果**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMzcxNTU2_size_16_color_FFFFFF_t_70 6]

## 递归 ##

**递归就是方法自己调用自己, 且每次调用时传入不同变量**  
递归的出现是帮助解决复杂问题, 简化代码

**递归代码举例**

public static int factorial(int n) { 
    	if (n == 1) { 
    		return 1;
    	} else { 
    		return factorial(n - 1) * n;
    }}

### 递归使用的场景 ###

*  如阶乘, 复制整个文件夹的实现, 以及商城项目中商品分类树的添加和删除逻辑
 *  各种数学问题如: 8皇后问题 , 汉诺塔, 阶乘问题, 迷宫问题, 球和篮子的问题(google编程大赛)
 *  各种算法中也会使用到递归，比如快排，归并排序，二分查找，分治算法等.
 *  将用栈解决的问题–>第归代码比较简洁

### 递归原则 ###

*  执行一个方法时，就创建一个新的受保护的独立空间(栈空间)
 *  方法的局部变量是独立的，不会相互影响, 比如n变量
 *  如果方法中使用的是引用类型变量(比如数组)，就会共享该引用类型的数据.
 *  **递归必须向退出递归的条件逼近，否则就是无限递归**,出现StackOverflowError，死龟了:)
 *  当一个方法执行完毕，或者遇到return，就会返回，遵守谁调用，就将结果返回给谁，同时当方法执行完毕或者返回时，该方法也就执行完毕。

#### 递归实现迷宫问题 ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMzcxNTU2_size_16_color_FFFFFF_t_70 7]  
**思路分析**

*  使用二维数组模拟迷宫,8行7列.
 *  使用1代表挡板,不能行动, 2代表可以移动, 3代表是死路
 *  设置坐标(1,1)为起点,(6,5)为终点
 *  方法一采取下右上左的策略, 方法二采取上右下左
 *  在没有使用算法的情况下如果寻找最小路径?  
    **将所有策略写成方法, 然后将路径放入集合中, 统计集合的大小并比较即可得到最短路径**

**代码实现**

/** * 迷宫回溯问题 * * @author TimePause * @create 2020-01-26 21:26 */
    public class MiGong { 
    
        public static void main(String[] args) { 
            // 先创建一个二维数组(8行7列)，模拟迷宫
            // 地图
            int[][] map = new int[8][7];
            // 使用1 表示墙
            // 上下全部置为1(第0行-第6行的列)
            for (int i = 0; i < 7; i++) { 
                map[0][i] = 1;
                map[7][i] = 1;
            }
    
            // 左右全部置为1(第0列-第7列的行)
            for (int i = 0; i < 8; i++) { 
                map[i][0] = 1;
                map[i][6] = 1;
            }
            //设置挡板, 1 表示
            map[3][1] = 1;
            map[3][2] = 1;
    // map[1][2] = 1;
    // map[2][2] = 1;
    
            // 输出地图
            System.out.println("地图的情况");
            for (int i = 0; i < 8; i++) { 
                for (int j = 0; j < 7; j++) { 
                    System.out.print(map[i][j] + " ");
                }
                System.out.println();
            }
    
            //使用递归回溯给小球找路
            //setWay(map, 1, 1);
            setWay2(map, 1, 1);
    
            //输出新的地图, 小球走过，并标识过的递归
            System.out.println("小球走过，并标识过的 地图的情况");
            for (int i = 0; i < 8; i++) { 
                for (int j = 0; j < 7; 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 setWay(int[][] map, int i, int j) { 
            if(map[6][5] == 2) {  // 通路已经找到ok
                return true;
            } else { 
                if(map[i][j] == 0) {  //如果当前这个点还没有走过
                    //按照策略 下->右->上->左 走
                    map[i][j] = 2; // 假定该点是可以走通.
                    if(setWay(map, i+1, j)) { //向下走
                        return true;
                    } else if (setWay(map, i, j+1)) {  //向右走
                        return true;
                    } else if (setWay(map, i-1, j)) {  //向上
                        return true;
                    } else if (setWay(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) {  // 通路已经找到ok
                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;
                }
            }
        }
    
    }

采取第一种策略(下右上左)  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMzcxNTU2_size_16_color_FFFFFF_t_70 8]

采取第二种策略(上右下左)  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMzcxNTU2_size_16_color_FFFFFF_t_70 9]

### 8皇后问题 ###

> 8皇后问题, 作为回溯算法的经典案例, 于1848年提出: 在8x8 的国际象棋上摆放着八个皇后, 使其不能相互攻击, 即: 在同一列或同一斜线上, 有多少种摆法.(92)

**思路图解**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMzcxNTU2_size_16_color_FFFFFF_t_70 10]  
**具体思路**  
![在这里插入图片描述][20200129213816823.png]  
实现代码

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

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMzcxNTU2_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/2020011220433860.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMzcxNTU2,size_16,color_FFFFFF,t_70
[stack]: https://baike.baidu.com/item/%E6%A0%88/12808149?fr=aladdin
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMzcxNTU2_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200112204535583.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMzcxNTU2,size_16,color_FFFFFF,t_70
[20200112204535829.png]: https://img-blog.csdnimg.cn/20200112204535829.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMzcxNTU2_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200112205018169.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMzcxNTU2,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMzcxNTU2_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20200113104929959.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMzcxNTU2,size_16,color_FFFFFF,t_70
[20200113165223596.png]: https://img-blog.csdnimg.cn/20200113165223596.png
[20200113165411754.png]: https://img-blog.csdnimg.cn/20200113165411754.png
[20200113211308315.png]: https://img-blog.csdnimg.cn/20200113211308315.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMzcxNTU2_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20200114173741963.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMzcxNTU2,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMzcxNTU2_size_16_color_FFFFFF_t_70 5]: https://img-blog.csdnimg.cn/20200114205056925.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMzcxNTU2,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMzcxNTU2_size_16_color_FFFFFF_t_70 6]: https://img-blog.csdnimg.cn/20200122115158511.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMzcxNTU2,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMzcxNTU2_size_16_color_FFFFFF_t_70 7]: https://img-blog.csdnimg.cn/20200126214231505.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMzcxNTU2,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMzcxNTU2_size_16_color_FFFFFF_t_70 8]: https://img-blog.csdnimg.cn/20200126215212489.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMzcxNTU2,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMzcxNTU2_size_16_color_FFFFFF_t_70 9]: https://img-blog.csdnimg.cn/20200126215123990.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMzcxNTU2,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMzcxNTU2_size_16_color_FFFFFF_t_70 10]: https://img-blog.csdnimg.cn/20200129211523418.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMzcxNTU2,size_16,color_FFFFFF,t_70
[20200129213816823.png]: https://img-blog.csdnimg.cn/20200129213816823.png