• 数据结构与算法（Java）--栈和递归

    数据结构与算法（java)–链表

    数据结构与算法（Java）–栈和递归

    数据结构与算法（java)–排序算法及查找

    数据结构与算法（java)–哈希表

    数据结构与算法（Java）–数结构

    数据结构与算法（Java）–图结构

    数据结构与算法（Java）–常见算法

    leetcode hot100

    栈

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

    应用场景

    • 子程序递归调用。如JVM中的虚拟机栈
    • 表达式转换（中缀转后缀）与求值
    • 二叉树的遍历
    • 图的深度优先遍历

    实现

    数组

    • 定义top表示栈顶，初始值为-1
    • 入栈的操作，先让top++，再放入数组
    • 出栈操作，先取出元素，在让top–
    • top == -1时，栈空
    • top == maxSize-1时，栈满

    代码

    //定义一个栈
class ArrayStack{
    private int maxSize;//栈的大小
    private int[] stack; //模拟栈的数组
    private int top = -1;//初始化为栈顶

    public ArrayStack(int maxSize) {
        this.maxSize = maxSize;
        stack = new int[this.maxSize];
    }
    //栈满
    public boolean ifFull(){
        return top == maxSize -1;
    }
    //栈空
    public boolean isEmpty(){
        return top == -1;
    }
    public void push(int value){
        if (ifFull()){
            System.out.println("栈满");
            return;
        }
        //压栈
        top ++;
        stack[top] = value;
    }
    public int pop(){
        if (isEmpty()){
            throw new RuntimeException("栈空，没有数据");
        }
        int res = stack[top];
        top --;
        return res;
    }
    //遍历
    public void list(){
        if (isEmpty()){
            System.out.println("栈空，没有数据");
        }
        for (int i = top; i>= 0; i--){
            System.out.print(stack[i] + " ");
        }
        System.out.println();
    }

}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47

    链表实现

    public class LinkedStackDemo {
    public static void main(String[] args) {
        LinkedStack linkedStack = new LinkedStack();
        linkedStack.push(1);
        linkedStack.push(2);
        linkedStack.show();
        Node head = linkedStack.getHead();
        reverseLinked(head);
        linkedStack.show();
    }
    public static  void reverseLinked(Node head){

        Node cur = head.getNext();
        Node next = null;
        Node reverse = new Node();
        while(cur != null){
            next = cur.getNext();
            cur.setNext(reverse.getNext());
            reverse.setNext(cur);
            cur = next;
        }
        head.setNext(reverse.getNext());
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    //链栈
class LinkedStack{
    //定义一个头节点
    Node head = new Node();
    public Node getHead(){
        return head;
    }
    //定义栈大小
    private int maxSize = 5;
    private int top = -1;
    public boolean isFull(){
        return top == maxSize-1;
    }
    public boolean isEmpty(){
        return top == -1;
    }
    public void push(int value){
        Node temp = head;
        if (isFull()){
            return;
        }
        while (temp.getNext()!=null){
           temp = temp.getNext();
        }
        Node res = new Node(value);
        temp.setNext(res);
        top ++;
    }
    public void show(){
        Node temp = head.getNext();
        if (isEmpty()){
            return;
        }
        while (temp != null){
            System.out.print(temp.getData() + " ");
            temp = temp.getNext();
        }
        System.out.println();
    }

    public int pop(){
        Node temp = head;
        if (isEmpty()){
            return -1;
        }
        top --;
        temp = temp.getNext();
        int res  = temp.getData();
        System.out.println("出栈的数为" + res);
        return res;
    }

}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    class Node{
    private int data;
    private Node next;

    public Node() {
    }

    public Node(int data) {
        this.data = data;
    }

    public Node(Node next) {
        this.next = next;
    }
    //省略getter、setter方法
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16

    应用

    综合计算式（中缀表达式）

    在这里插入图片描述

    1.准备一个索引index来帮助我们遍历表达式

    2.如果index位置上的元素是一个数字，就直接入栈

    3.如果index位置上的元素是一个符号

    • 如果符号栈为空，直接入栈
    • 如果符号栈不为空，有操作符，进行比较
      • index位置上的符号的优先级小于或等于栈顶符号的优先级，则弹出两个数栈中的元素和符号栈中的一个符号，并且进行计算。将运算结果放入数栈中，并将index位置上的符号压入符号栈
      • index位置上的符号的优先级大于符号栈栈顶符号的优先级，则将该符号压入符号栈

    4.当表达式遍历完毕后，就弹出数栈中的2个数字和符号栈中的1个符号进行运算，并将运行结果入栈

    5.最终数栈中只有一个值，这个值便是运算结果
    注意：
    读取的是字符，所以存入数字前需要减去0的ASCII码
    如果数字是多位数，需要一直读，读到下一位不是数字为止，然后将读到的字符进行拼接，然后一起压入数栈

    一位运算实现
    public class StackCounter {
    public static void main(String[] args) {
        String experssion = "7+2*6-2";
        //创建两个栈
        ArrayStack2 numberStack = new ArrayStack2(10);
        ArrayStack2 operStack = new ArrayStack2(10);
        int index = 0;//用于扫描
        int num1 = 0, num2 = 0;
        int oper = 0;
        int res = 0;
        char ch =' ' ;//将每次扫描得到的char放入
        //开始循环
        while(true){
            //依次得到每一个字符
            ch = experssion.substring(index,index+1).charAt(0);
            //判断ch是什么，然后做相应的处理
            if(operStack.isOper(ch)){//如果是符号
                if (!operStack.isEmpty()){//如果符号栈不为空
                    //如果是符号，进行比较，如果当前操作符的优先级小于或等于栈中运算符
                    if (operStack.priority(ch) <=operStack.priority(operStack.pick())) {
                        num1 = numberStack.pop();
                        num2 = numberStack.pop();
                        oper = operStack.pop();
                        res = numberStack.cal(num1,num2,oper);
                        numberStack.push(res);
                        operStack.push(ch);
                    }else {
                        operStack.push(ch);
                    }
                }else{
                    //如果为空直接入栈
                    operStack.push(ch);//如果

                }

            }else{//如果是数，则直接入栈
                numberStack.push(ch - 48);//ASCII码转换为数字
            }
            //index+1.是否扫描到expersion最后
            index++;
            if (index >= experssion.length()){
                break;
            }
        }
        while(true){
            //如果符号栈为空，则结算结束，数栈中只有一个数字
            if (operStack.isEmpty()){
                break;
            }
            num1 = numberStack.pop();
            num2 = numberStack.pop();
            oper = operStack.pop();
            res = numberStack.cal(num1,num2,oper);
            numberStack.push(res);

        }
        //将数栈中最后一个打印出来
        System.out.println("表达式为："+experssion+"结果为："+numberStack.pop());


    }
}
//先创建一个栈，需要扩展功能
class ArrayStack2{
    private int maxSize;//栈的大小
    private int[] stack; //模拟栈的数组
    private int top = -1;//初始化为栈顶

    public ArrayStack2(int maxSize) {
        this.maxSize = maxSize;
        stack = new int[this.maxSize];
    }
    //栈满
    public boolean ifFull(){
        return top == maxSize -1;
    }
    //栈空
    public boolean isEmpty(){
        return top == -1;
    }
    public void push(int value){
        if (ifFull()){
            System.out.println("栈满");
            return;
        }
        top ++;
        stack[top] = value;
    }
    public int pop(){
        if (isEmpty()){
            throw new RuntimeException("栈空，没有数据");
        }
        int res = stack[top];
        top --;
        return res;
    }
    //遍历
    public void list(){
        if (isEmpty()){
            System.out.println("栈空，没有数据");
        }
        for (int i = top; i>= 0; i--){
            System.out.print(stack[i] + " ");
        }
        System.out.println();
    }
    //返回运算符的优先级，优先级使用数字表示，数字越大，优先级越高
    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;
        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;
    }
    //返回当前栈顶的方法
    public int pick(){
        return stack[top];
    }

}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115
    • 116
    • 117
    • 118
    • 119
    • 120
    • 121
    • 122
    • 123
    • 124
    • 125
    • 126
    • 127
    • 128
    • 129
    • 130
    • 131
    • 132
    • 133
    • 134
    • 135
    • 136
    • 137
    • 138
    • 139
    • 140
    • 141
    • 142
    • 143
    • 144
    • 145
    • 146
    • 147
    • 148
    多位运算实现
    public class StackCounter {
    public static void main(String[] args) {
        String experssion = "70+2*6-4+8";
        //创建两个栈
        ArrayStack2 numberStack = new ArrayStack2(10);
        ArrayStack2 operStack = new ArrayStack2(10);
        int index = 0;//用于扫描
        int num1 = 0, num2 = 0;
        int oper = 0;
        int res = 0;
        String s = "";//用于拼接多位数
        char ch = ' ';//将每次扫描得到的char放入
        //开始循环
        while (true) {
            //依次得到每一个字符
            ch = experssion.substring(index, index + 1).charAt(0);
            //判断ch是什么，然后做相应的处理
            if (operStack.isOper(ch)) {//如果是符号
                if (!operStack.isEmpty()) {//如果符号栈不为空
                    //如果是符号，进行比较，如果当前操作符的优先级小于或等于栈中运算符
                    if (operStack.priority(ch) <= operStack.priority(operStack.pick())) {
                        num1 = numberStack.pop();
                        num2 = numberStack.pop();
                        oper = operStack.pop();
                        res = numberStack.cal(num1, num2, oper);
                        numberStack.push(res);
                        operStack.push(ch);
                    } else {
                        //否则直接入栈
                        operStack.push(ch);
                    }
                }else{
                    operStack.push(ch);
                }
            }else {//如果是数，则直接入栈
                //当处理多位数时，不能发现是一个数就立即入栈，在处理数时，需要向expression的表达式再看一位index，如果是符号就可以入栈
                //需要定义一个字符串变量用于拼接。
                s += ch;
                //是否是表达式的最后一位
                if (index == experssion.length() - 1) {
                    numberStack.push(Integer.parseInt(s));
                } else {
                    //判断下一个字符是不是数字，如果是数字就继续扫描
                    if (operStack.isOper(experssion.substring(index + 1, index + 2).charAt(0))) {
                        //如果是符号就可以入栈
                        numberStack.push(Integer.parseInt(s));//字符串转为整数
                        //清空s
                        s = "";
                    }
                }
            }
            //index+1.是否扫描到expersion最后
            index++;
            if (index >= experssion.length()) {
                break;
            }
        }
        while (true) {
            //如果符号栈为空，则结算结束，数栈中只有一个数字
            if (operStack.isEmpty()) {
                break;
            }
            num1 = numberStack.pop();
            num2 = numberStack.pop();
            oper = operStack.pop();
            res = numberStack.cal(num1, num2, oper);
            numberStack.push(res);
        }//将数栈中最后一个打印出来
        System.out.println("表达式为：" + experssion + "结果为：" + numberStack.pop());


    }

}

//先创建一个栈，需要扩展功能
class ArrayStack2{
    private int maxSize;//栈的大小
    private int[] stack; //模拟栈的数组
    private int top = -1;//初始化为栈顶

    public ArrayStack2(int maxSize) {
        this.maxSize = maxSize;
        stack = new int[this.maxSize];
    }
    //栈满
    public boolean ifFull(){
        return top == maxSize -1;
    }
    //栈空
    public boolean isEmpty(){
        return top == -1;
    }
    public void push(int value){
        if (ifFull()){
            System.out.println("栈满");
            return;
        }
        top ++;
        stack[top] = value;
    }
    public int pop(){
        if (isEmpty()){
            throw new RuntimeException("栈空，没有数据");
        }
        int res = stack[top];
        top --;
        return res;
    }
    //遍历
    public void list(){
        if (isEmpty()){
            System.out.println("栈空，没有数据");
        }
        for (int i = top; i>= 0; i--){
            System.out.print(stack[i] + " ");
        }
        System.out.println();
    }
    //返回运算符的优先级，优先级使用数字表示，数字越大，优先级越高
    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;
        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;
    }
    //返回当前栈顶的方法
    public int pick(){
        return stack[top];
    }


}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115
    • 116
    • 117
    • 118
    • 119
    • 120
    • 121
    • 122
    • 123
    • 124
    • 125
    • 126
    • 127
    • 128
    • 129
    • 130
    • 131
    • 132
    • 133
    • 134
    • 135
    • 136
    • 137
    • 138
    • 139
    • 140
    • 141
    • 142
    • 143
    • 144
    • 145
    • 146
    • 147
    • 148
    • 149
    • 150
    • 151
    • 152
    • 153
    • 154
    • 155
    • 156
    • 157
    • 158
    • 159
    • 160
    • 161
    • 162

    存在的问题：因为栈是用的整型数组，所以计算除法的时候，无法转化成double

    逆波兰计算器

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

    正常的表达式逆波兰表达式
    a+ba b +
    a+(b-c)a b c - +
    a+(b-c)*da b c – d * +
    a+d*(b-c)a d b c - * +
    a=1+3a 1 3 + =

    在这里插入图片描述

    中缀转后缀

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

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

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

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

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

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

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

    5. 遇到括号时：

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

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

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

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

    如“1+（（2+3）x 4）-5”；步骤如下
    在这里插入图片描述

    实现

    import java.util.*;

public class PolandNatation {
    public static void main(String[] args) {
        //将中缀表达式转换为后缀表达式
        String experssion = "1+((2+3)*4)-5";
        List<String> infixExperssionList = toInfixExperssionList(experssion);
        System.out.println(infixExperssionList);
        List<String> pareSuffixExperssion = parseSuffixExpersion(infixExperssionList);//将中缀表达式转换为后缀表达式
        System.out.println(pareSuffixExperssion);
        System.out.println("结果为：" + calculate(pareSuffixExperssion));
        //定义一个逆波兰表达式
        /*String suffixExpression = "4 5 * 8 - 60 + 8 2 / +";
        //为了方便，逆波兰表达式的数字和空格隔开
        //思路
        //先将"3 4 + 5 * 6 -" 放入ArrayList中
        //4*5-8+60+8/2
        //4 5 * 8 - 60 + 8 2 / +
        //将ArrayList传递给一个方法，这个方法使用配合栈完成计算
        List rpnList = getListString(suffixExpression);
        System.out.println("rpnList " + rpnList);
        int res = calculate(rpnList);
        System.out.println("计算结果为：" + res);*/

    }
    //将中缀表达式转换成对应的List
    public static List<String> toInfixExperssionList(String s){
        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(String.valueOf(c));
                i++;
            }else{//如果是一个数们需要考虑多位数问题
                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;

    }
    //将得到的中缀表达式对应的list 转换为后缀表达式对应的list
    public static List<String> parseSuffixExpersion(List<String> ls){
        //定义两个栈
        Stack<String> s1 = new Stack<String>();
        //因为s2在整个转换过程中没有pop操作，而且还要逆序输出，因此直接使用List
        List<String> s2 = new ArrayList<String>();
        //遍历ls
        for (String item:ls){
            if (item.matches("\\d+")){
                s2.add(item);
            }else if(item.equals("(")){
                s1.push(item);
            }else if(item.equals(")")){
                while(!s1.peek().equals("(")){
                    s2.add(s1.pop());//s1一次弹出到s2
                }
                s1.pop();//将（弹出s1 消除(
            }else{
                //当item运算符的优先级小于s1栈顶运算符的优先级时，s1栈顶的运算符弹出栈，压入到s2
                while (s1.size()!= 0 && Operation.getValue(s1.peek()) >= Operation.getValue(item)){
                    s2.add(s1.pop());
                }
                //把当前item运算符，压入栈中
                s1.push(item);
            }
        }
        while(s1.size()!= 0){
            s2.add(s1.pop());
        }
        return s2;//顺序输出即可
    }
    //优先级比较高低的方法

    //将一个逆波兰表达式，依次将数据和运算符放入ArrayList中
    public static List<String> getListString(String suffixExperssion){
        //将suffixExperssion分割
        String[] split = suffixExperssion.split(" ");//把字符串分隔开
        List<String> list = new ArrayList<String>();//创建一个新的序列
        for (String ele:split){
            list.add(ele);
        }
        return list;
    }
    //完成运算
    public static int calculate(List<String> ls){
        //创建栈，只需要一个栈即可
        Stack<String> stack = new Stack<String>();
        //遍历list
        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("运算符有误");
                }
                stack.push(String.valueOf(res));
            }
        }
        return Integer.parseInt(stack.pop());
    }
}
//编写一个类
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;
    }
}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115
    • 116
    • 117
    • 118
    • 119
    • 120
    • 121
    • 122
    • 123
    • 124
    • 125
    • 126
    • 127
    • 128
    • 129
    • 130
    • 131
    • 132
    • 133
    • 134
    • 135
    • 136
    • 137
    • 138
    • 139
    • 140
    • 141
    • 142
    • 143
    • 144
    • 145
    • 146
    • 147
    • 148
    • 149
    • 150
    • 151
    • 152
    • 153

    完整逆序表达式计算器

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

    参考

    import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Stack;
import java.util.regex.Pattern;


public class CompersionPolandNatation {

    /**
     * 匹配 + - * / ( ) 运算符
     */
    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 Double 计算结果
     */
    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;
    }

    /**
     * 功能描述：完整版逆波兰计算器测试
     *
     * @param args 命令行
     * @author cakin
     * @date 2021/3/6
     */
    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();
        }
    }
}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115
    • 116
    • 117
    • 118
    • 119
    • 120
    • 121
    • 122
    • 123
    • 124
    • 125
    • 126
    • 127
    • 128
    • 129
    • 130
    • 131
    • 132
    • 133
    • 134
    • 135
    • 136
    • 137
    • 138
    • 139
    • 140
    • 141
    • 142
    • 143
    • 144
    • 145
    • 146
    • 147
    • 148
    • 149
    • 150
    • 151
    • 152
    • 153
    • 154
    • 155
    • 156
    • 157
    • 158
    • 159
    • 160
    • 161
    • 162
    • 163
    • 164
    • 165
    • 166
    • 167
    • 168
    • 169
    • 170
    • 171
    • 172
    • 173
    • 174
    • 175
    • 176
    • 177
    • 178
    • 179
    • 180
    • 181
    • 182
    • 183
    • 184
    • 185
    • 186
    • 187
    • 188
    • 189
    • 190
    • 191
    • 192
    • 193
    • 194
    • 195
    • 196
    • 197
    • 198
    • 199
    • 200
    • 201
    • 202
    • 203
    • 204
    • 205
    • 206
    • 207
    • 208
    • 209
    • 210
    • 211
    • 212
    • 213
    • 214
    • 215
    • 216
    • 217
    • 218
    • 219
    • 220
    • 221

    递归

    概述

    递归就是方法自己调用自己,每次调用时传入不同的变量.递归有助于编程者解决复杂的问题,同时可以让代码变得简洁。并且递归用到了虚拟机栈

    关注点

    1. 找整个递归的终止条件：递归应该在什么时候结束？
    2. 找返回值：应该给上一级返回什么信息？
    3. 本级递归应该做什么：在这一级递归中，应该完成什么任务？

    场景

    八皇后问题 汉诺塔 求阶乘 迷宫问题 球和篮子 各种排序算法

    调用机制

    程序执行到一个方法时，就会开辟一个独立的空间(栈空间)，每个空间的数据（局部变量）是独立的

    eg.阶乘问题

    package com.atguigu.recusion;

public class RecusionTest01 {
    public static void main(String[] args) {
        //回顾递归的调用机制
        System.out.println("res + " + factorial(2));
    }
    //阶乘问题
    public static int factorial(int n) {
        if (n == 1) {
            return 1;
        } else {
            return factorial(n - 1) * n; // 1 * 2 * 3
        }
    }
}



    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18

    规则

    1.执行一个方法时，就创建一个新的受保护的独立空间(栈空间)

    2.方法的变量是独立的，不会相互影响的

    3.如果方法中使用的是引用类型变量(比如数组)，就会共享该引用类型的数据

    4.递归必须向退出递归的条件逼近，否则就是无限递归，出现 StackOverflowError

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

    迷宫问题

    代码实现
    package com.atguigu.recusion;

public class MiGongTest01 {
    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("------MAP-----");
        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);
        //输出新的地图，小球走过的通路
        System.out.println("------NEWMAP-----");
        for(int i = 0; i <8 ;i++) {
            for (int j = 0; j < 7; j++) {
                System.out.print(map[i][j] + " ");
            }
            System.out.println();
        }
    }

    /**
     * 如果小球可以到达map[6][5]，则说明通路找到
     * 约定：当map[i][j]为0表示该点没有走过，1的时候为墙；2的时候表示一个通路；3表示该点探测过了，但是不通
     * 走迷宫时候的策略：下 右 上 左，如果该点走不通在回溯
     * @param map 地图
     * @param i 起始位置
     * @param j
     * @return
     */
    public static boolean setWay(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(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 {
                return false;
            }
        }
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    对迷宫问题的讨论
    1. 小球得到的路径，和程序员设置的找路策略有关即：找路的上下左右的顺序相关
    2. 再得到小球路径时，可以先使用(下右上左)，再改成(上右下左)，看看路径是不是有变化
    3. 测试回溯现象
    4. 思考: 如何求出最短路径? 思路代码实现.
    最短路径的代码实现
    package ch4;

import java.util.Scanner;

public class MiGong {
    static int n,m,endx,endy,min = 99999;
    static int[][] a = new int[51][51];
    static int[][] book = new int[51][51];
    public static void main(String[] args) {
        //读入n和m，n为行，m为列
        Scanner scanner = new Scanner(System.in);
        System.out.println("输入行：");
        n = scanner.nextInt();
        System.out.println("输入列：");
        m = scanner.nextInt();
        System.out.println("输入迷宫：");
        for (int i =1; i<=n ;i++){
            for (int j =1;j<=m;j++){
                a[i][j] = scanner.nextInt();
            }
        }
        scanner.close();
        int stratx = 1,starty = 1;
        endx = n;
        endy = m;
        //从起点开始搜索
        book[stratx][starty] = 1;//标记起点已经在路径中
        dfs(stratx,starty,0);
        System.out.println("最短的路径 " + min);
    }
    public static void dfs(int x, int y, int step){
        //定义四个方向
        int[][] next= {{0,1},{1,0},{0,-1},{-1,0}};
        int tx,ty;
        //判断是否到达出口
        if(x ==endx  && y == endy){
            //更新最小值
            if(step<=min)
                min = step;
            return;
        }
        //四种走法
        for(int k =0; k<4;k++){
           //计算下一个坐标点
           tx = x + next[k][0];
           ty = y + next[k][1];
           //判断是否越界，是否为障碍物，是否在路径中
            if(tx < 1|| tx > n || ty <1|| ty > n){
                continue;
            }
            if(a[tx][ty] == 0 && book[tx][ty] == 0){
                book[tx][ty]  = 1;//标记这个点已经做过了
                dfs(tx,ty,step+1);//开始尝试下一个点
                book[tx][ty] = 0;//尝试结束，取消这个点的标记

            }
        }
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59

    八皇后问题

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

    思路

    • 将第一个皇后放在第一行第一列
    • 将第二个皇后放在第二行第一列，判断是否会和其他皇后相互攻击，若会相互攻击，则将其放到第三列、第四列…知道不会相互攻击为止
    • 将第三个皇后放在第三行第一列，判断是否会和其他皇后相互攻击，若会相互攻击，则将其放到第三列、第四列…知道不会相互攻击为止，并以此类推，在摆放的过程中，有可能会改动前面所放的皇后的位置
    • 当得到一个正确的解时，就会回溯到上一行，由此来找出第一个皇后在第一行第一列的所有解
    • 再将第一个皇后放到第一行第二列，并重复以上四个步骤
    • 注意：
      • 棋盘本身应该是用二维数组表示，但是因为皇后所在的行数是固定的，所以可以简化为用一个一维数组来表示。其中的值代表皇后所在的列
      • 数组下标代表皇后所在行数，所以判断是否在同一行列斜线上时，只需要判断是否在同一列和同一斜线上即可
        • 是否同列判断：值是否相同
        • 是否同一斜线：行号-行号是否等于列号-列号，且列号相减要取绝对值
    package com.atguigu.recusion;

public class Queue8 {
    //定义一个max表示共有多少个皇后
    int max = 8;
    //定义一个数组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) {
        Queue8 queue8 = new Queue8();
        queue8.check(0);
        System.out.println(count);
        System.out.println(judgecount);
    }

    //编写一个方法，放置第n个皇后
    //check 每一次递归时，都有一次for循环，因此会有回溯
    private void check(int n){
        if(n == max){//开始放第九个皇后，放置结束
            print();
            count++;
            return;
        }
        //没有放置结束，依次放入皇后
        for (int i =0; i < max ;i++){
            //先把当前皇后，放到该行的第1列
            array[n] = i;
            //判断是否可以放置
            if(judge(n)){
                check(n+1);
            }
            //如果冲突就继续执行for循环，直到全部列找完
        }
    }
    //查看当我们放置第n个皇后，就去检测该皇后是否和前面已经摆放完的皇后冲突
    /**
     *
     * @param n 表示要放置的第n个皇后
     * @return
     */
    public boolean judge(int n){
        judgecount ++;
        for (int i = 0 ;i <n ; i++){
            //第一个条件：判断是否在同一列
            //第二个条件：判断是否在同一斜线，如果在同一斜线当前行-行的绝对值 = 当前列- 列的绝对值
            //因为n是递增的所以一定不同一行
            if(array[i] == array[n] || Math.abs(n-i) == Math.abs(array[n] - array[i]))
                return false;
        }
        return true;
    }
    //写一个方法将最后摆放的位置打印出来
    private void print(){
        for (int i=0;i<array.length;i++){
            System.out.print(array[i] + " ");
        }
        System.out.println();
    }

}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
  • 相关阅读:
    php实战案例记录(4)`include`和`require_once`的区别和用法
    SMART PLC星三角延时启动功能块(梯形图FC)
    搭建一个自己的轻量级二维码生成接口
    2023-2028年中国硫酸铝钾市场发展态势及未来发展趋势报告
    LabVIEW开发指针式压力仪表图像识别
    【Kubernetes系列】工作负载资源之DaemonSet
    测试只能干到35岁？35岁+的测试就会失业？
    安防监控系统/视频云存储/视频监控平台EasyCVR无法级联上级平台，该如何解决？
    如何开发一个基于node.js的CLI工具
    java通过http下载文件示例
  • 原文地址：https://blog.csdn.net/m0_47498874/article/details/126584280