Java数据结构与算法一2-阿里云开发者社区

双向链表

单链表存在问题：

只有一个方向，而双向链表可以向前或前后查找
单向链表不能自我删除，要有临时变量，双向链表可以实现自我删除

双向链表结构：

分析双向链表的CRUD

遍历：

和单链表一样，向前或向后查找

添加：默认添加到双向链表的最后

先找到双向链表的最后的这个节点（temp）

temp. next =newHeroNode

newHeroNode.pre = temp

修改

和单向链表一样

删除

自我删除某个节点

直接找到要删除的这个节点（temp）

temp.pre.next = temp.next (temp前一个直接指向temp的后一个节点)

temp.next.pre = temp.pre

单向环形链表

应用场景

Josephu(约瑟夫、约瑟夫环) 问题 Josephu 问题为：设编号为1，2，… n的n个人围坐一圈，约定编号为k（1<=k<=n）的人从1开始报数，数到m 的那个人出列，它的下一位又从1开始报数，数到m的那个人又出列，依次类推，直到所有人出列为止，由此产生一个出队编号的序列.

单向环形链表结构

Josehu 问题分析

先构成一个有n个结点的单循环链表，然后由k结点起从1开始计数，计到m时，对应结点从链表中删除，然后再从被删除结点的下一个结点又从1开始计数，直到最后一个结点从链表中删除算法结束

n = 5 ：有五个人
k = 1：从第一个人开始报数
m = 2 ，数两次

出队列报数顺序：

2 =》4 =》1=》5 =》3

分析思路

先创建第一个节点，让first指向该节点，并形成环形
后面让我们每创建一个新的节点，把该节点，加入到已经有的环形链表中

遍历环形链表

先让一个指针（变量）curBoy ，指向first节点
通过while循环遍历该环形链表curBoy.next = first

出队顺序

创建一个指针（变量）helper，开始指向环形链表的最后一个节点

报数前，先让 first 和 helper 移动 k - 1 次

报数时，让first 和 helper 指针同时移动 m - 1 次

将 first 指向这个小孩节点出圈

first = first.next

helper.next = first

原来的节点没有了任何的指向就会被垃圾回收

package com.linkedlist;
/**
 * @author Kcs 2022/8/10
 */
public class Josepfu {
    public static void main(String[] args) {
        //环形链表测试
        CircleSingleLinkedList circleSingleLinkedList = new CircleSingleLinkedList();
        //创建五个小孩节点
        circleSingleLinkedList.addBoy(100);
        //显示
        circleSingleLinkedList.showBoy();
        //出圈
        circleSingleLinkedList.countBoy(1, 2, 100);
    }
}
/**
 * 创建一个单向的环形链表
 */
class CircleSingleLinkedList {
    /**
     * 创建first节点
     */
    private Boy first = new Boy(-1);
    /**
     * 添加节点，构成环形链表
     */
    public void addBoy(int nums) {
        //数据判断
        if (nums < 1) {
            System.out.println("nums值需要大于1");
            return;
        }
        //临时变量
        Boy curBoy = null;
        //使用for创建环形链表
        for (int i = 1; i <= nums; i++) {
            //根据编号，创建节点
            Boy boy = new Boy(i);
            //第一个小孩节点
            if (i == 1) {
                first = boy;
                //形成环形
                first.setNext(first);
                //curBoy 指向第一个小孩节点
                curBoy = first;
            } else {
                //指向新建的节点
                curBoy.setNext(boy);
                boy.setNext(first);
                curBoy = boy;
            }
        }
    }
    /**
     * 遍历当前的环形链表
     */
    public void showBoy() {
        //判断链表是否为空
        if (first == null) {
            System.out.println("链表为空！！");
            return;
        }
        //first 节点不能移动，创建临时指针
        Boy curBoy = first;
        while (true) {
            System.out.printf("小孩的编号:%d\n", curBoy.getNo());
            //遍历结束
            if (curBoy.getNext() == first) {
                break;
            }
            //curBoy后移
            curBoy = curBoy.getNext();
        }
    }
    /**
     * 根据输入，计算出圈的顺序
     * @param startNo 开始的节点
     * @param countNum 数几下
     * @param nums 圈内总共有几个节点
     */
    public void countBoy(int startNo, int countNum, int nums) {
        //校验
        if (first == null || startNo < 1 || startNo > nums) {
            System.out.println("输入的数字有误。请重新输入");
            return;
        }
        //临时指针
        Boy helper = first;
        while (true) {
            //遍历借结束
            if (helper.getNext() == first) {
                break;
            }
            //helper后移
            helper = helper.getNext();
        }
        //报数前，先让 first 和 helper 移动 k - 1 次
        for (int i = 0; i < startNo - 1; i++) {
            first = first.getNext();
            helper = helper.getNext();
        }
        //报数时，让first 和 helper 指针同时移动 m - 1 次,循环操作，直到圈中只有一个人
        while (true) {
            //判断圈中只有一个人
            if (helper == first) {
                System.out.println("最后一个人了");
                break;
            }
            //让first 和 helper 指针同时移动 countNum - 1 ,出圈
            for (int i = 0; i < countNum - 1; i++) {
                first = first.getNext();
                helper = helper.getNext();
            }
            //first指向出圈的节点
            System.out.printf("小孩 %d 出圈\n", first.getNo());
            //first指向出圈小孩的节点
            first = first.getNext();
            helper.setNext(first);
        }
        System.out.printf("最后圈中的小孩的编号是%d", helper.getNo());
    }
}
/**
 * 创建一个Boy类，表示一个节点
 */
class Boy {
    /**
     * 编号
     */
    private int no;
    /**
     * 下一个节点
     */
    private Boy next;
    public Boy(int no) {
        this.no = no;
    }
    public int getNo() {
        return no;
    }
    public void setNo(int no) {
        this.no = no;
    }
    public Boy getNext() {
        return next;
    }
    public void setNext(Boy next) {
        this.next = next;
    }
}

栈 stack

先入后出的有序列表

栈(stack)是限制线性表中元素的插入和删除只能在线性表的同一端进行的一种特殊线性表。允许插入和删除的一端，为变化的一端，称为栈顶(Top)，另一端为固定的一端，称为栈底(Bottom)

最先放入栈中元素在栈底，最后放入的元素在栈顶，而删除元素刚好相反，最后放入的元素最先删除，最先放入的元素最后删除

出栈（pop）、入栈（push）结构

应用场景

子程序的调用：在跳往子程序前，会先将下个指令的地址存到堆栈中，直到子程序执行完后再将地址取出，以回到原来的程序中

处理递归调用：和子程序的调用类似，只是除了储存下一个指令的地址外，也将参数、区域变量等数据存入堆栈中

表达式的转换 [ 中缀表达式转后缀表达式 ] 与求值(实际解决)

二叉树的遍历

图形的深度优先( depth一first )搜索法

栈的快速入门

用数组模拟栈
栈顶：定义变量初始值 top = -1
入栈：top++，stack[top] = data
出栈：int value = stack[top] ,top – ,return value

package com.stack;
import java.util.Scanner;
/**
 * 栈
 * @author Kcs 2022/8/11
 */
public class ArrayStackDemo {
    public static void main(String[] args) {
        //测试
        ArrayStack stack = new ArrayStack(4);
        String key = "";
        //控制菜单是否退出
        boolean loop = true;
        Scanner scanner = new Scanner(System.in);
        while (loop) {
            System.out.println("show:显示栈内所有的数据");
            System.out.println("push:添加数据到栈(入栈)");
            System.out.println("pop:从栈中取出数据(出栈)");
            System.out.println("exit:退出栈");
            System.out.println("你的选择是：");
            key = scanner.next();
            switch (key) {
                case "show":
                    stack.list();
                    break;
                case "push":
                    System.out.println("请输入一个数字：");
                    int value = scanner.nextInt();
                    stack.push(value);
                    break;
                case "pop":
                    try {
                        int res = stack.pop();
                        System.out.printf("出栈的数据%d\n", res);
                    } catch (Exception e) {
                        System.out.println(e.getMessage());
                    }
                    break;
                case "exit":
                    scanner.close();
                    loop = false;
                    break;
                default:
                    break;
            }
        }
        System.out.println("程序退出,欢迎下次再来！！！");
    }
}
/**
 * 定义一个ArrayStack 表示栈
 */
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 isFull() {
        return top == maxSize - 1;
    }
    /**
     * 栈空
     */
    public boolean isEmpty() {
        return top == -1;
    }
    /**
     * 入栈
     */
    public void push(int value) {
        //判断是否栈满
        if (isFull()) {
            System.out.println("栈满");
            return;
        }
        top++;
        stack[top] = value;
    }
    /**
     * 出栈
     */
    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]);
        }
    }
}

栈实现综合案例-计算器

思路分析（使用中缀表达式）

计算式：7 * 2 * 2 - 5 + 1- 5 * 3 - 3

首先创建两个栈

数栈（numStack）：存放数

符号栈（operStack）：存放运算符

通过一个index 值，来遍历表达式

扫描到一个数字，就直接加入数栈

扫描到一个运算符，则有两种情况

若当前符号栈为空，就直接入栈

若符号栈不为空，就进行比较，如果当前的操作符的优先级小于或等于栈中的操作符，则从数栈中pop数两个数，再从符号栈中pop出一个符号，进行运算，将其结果进入数栈，将当前的操作符入符号栈

如果当前的操作符的优先级大于栈中的操作符，就直接入符号栈

当表达式扫描完毕，就顺序的从数栈和符号栈中pop出相应的数和符号，并运行

最后在数栈只有一个数字，既是结果

处理多位数问题

不能发现一个数就立即入栈，可能是多位数

处理数式，需要项expression的表达式的index，后看一位，若是数九进行扫描，若是符号才入栈

定义一个字符串变量，进行拼接

package com.stack;
/**
 * @author Kcs 2022/8/12
 */
public class Calculator {
    public static void main(String[] args) {
        //扫描表达式
        String expression = "5456*2+5";
        //创建两个栈，数栈，符号栈
        ArrayCalStack numStack = new ArrayCalStack(10);
        ArrayCalStack operStack = new ArrayCalStack(10);
        //扫描变量
        int index = 0;
        int num1 = 0;
        int num2 = 0;
        int oper = 0;
        int res = 0;
        //用于每次扫描得到的char保存到ch
        char ch = ' ';
        //用于拼接多位数
        String keyNum = "";
        //循环扫描
        while (true) {
            //依次得到每一个字符
            ch = expression.substring(index, index + 1).charAt(0);
            //判断是否为符号
            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);
                }
            } else {
                //如果是数字就直接入数栈(存在多位数问题)
                //处理多位数
                keyNum += ch;
                //如果ch为expression最后的一位
                if (index == expression.length()-1){
                    numStack.push(Integer.parseInt(keyNum));
                }else {
                    //判断下一位是否为数字，若为数字，则进行扫描，若是运算符，则入符号栈
                    if (operStack.isOper(expression.substring(index + 1, index + 2).charAt(0))){
                        //如果后一位为运算符则入栈，keepNum ="112"
                        numStack.push(Integer.parseInt(keyNum));
                        //清空keepNum
                        keyNum = "";
                    }
                }
            }
            //让index + 1 ,判断是否扫描到最后
            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 result = numStack.pop();
        System.out.printf("表达式%s = %d", expression, result);
    }
}
/**
 * ArrayCalStack
 */
class ArrayCalStack {
    /**
     * 栈的的大小
     */
    private int maxSize;
    /**
     * 数组模拟栈
     */
    private int[] stack;
    /**
     * 初始化栈顶
     */
    private int top = -1;
    /**
     * 构造方法
     */
    public ArrayCalStack(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;
    }
    /**
     * 入栈
     */
    public void push(int value) {
        //判断是否栈满
        if (isFull()) {
            System.out.println("栈满");
            return;
        }
        top++;
        stack[top] = value;
    }
    /**
     * 出栈
     */
    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 var) {
        return var == '+' || var == '-' || var == '*' || var == '/';
    }
    /**
     * 计算方法
     */
    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;
    }
}

前缀(波兰表达式)

前缀表达式的运算符位于操作数之前

(3+4)×5-6 对应的前缀表达式就是 - × + 3 4 5 6

计算机求职

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

(3+4)×5-6 对应的前缀表达式就是 - × + 3 4 5 6 的表达式的求值步骤

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

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

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

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

中缀

最常见的运算规则

后缀

运算符位于操作数之后

(3+4)×5-6 对应的后缀表达式就是 3 4 + 5 × 6 –

计算规则

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

从左至右扫描，将3和4压入堆栈；

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

将5入栈；

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

将6入栈；

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

逆波兰计算器

输入一个逆波兰表达式（后缀表达式）使用栈（Stack）计算其结果
支持小括号和多位数，只对整数计算

分析

定义一个逆波兰表达式
依次将逆波兰表达式的数据和运算符存入到ArrayList中
ArrayList 传递给一个方法，遍历ArrayList,配合栈，完成计算

package com.stack;
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
/**
 * @author Kcs 2022/8/13
 */
public class PolandNotation {
    public static void main(String[] args) {
        //定义一个逆波兰表达式 (3+4)×5-6 ,4 5 * 8 - 60 + 8 2 / +,存在空格符号
        String suffixExpression = "4 5 * 8 - 60 + 8 2 / +";
        //将ArrayList传递给一个方法，遍历
        List<String> list = getListString(suffixExpression);
        System.out.println("list=" + list);
        int res = calculate(list);
        System.out.println("result = " + res);
    }
    /**
     * 表达式 存入ArrayList中
     * @param suffixExpression
     * @return String[]
     */
    public static List<String> getListString(String suffixExpression) {
        //将表达式分割
        String[] spilt = suffixExpression.split(" ");
        List<String> list = new ArrayList<String>();
        for (String ele : spilt) {
            list.add(ele);
        }
        return list;
    }
    // 逆波兰表达式的运算
    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("运算符有问题，不属于四则运算符号");
                }
                stack.push("" + res);
            }
        }
        //最后留在栈里的数据是运算结果
        return Integer.parseInt(stack.pop());
    }
}

中缀转后缀

将这个中缀表达式：1 + (( 2 + 3) × 4 ) - 5 ===》后缀表达式

分析步骤

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

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

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

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

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

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

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

遇到括号时：

如果是左括号 “(” ，则直接压入s1

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

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

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

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

package com.stack;
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
/**
 * @author Kcs 2022/8/13
 */
public class PolandNotation {
    public static void main(String[] args) {
        // 中缀 ===》后缀
        // 1 + (( 2 + 3) * 4 ) - 5 ===》1 2 3 + 4 * + 5 –
        String expression = "1+((2+3)*4)-5";
        List<String> infixExpressionList = toInfixExpressionList(expression);
        System.out.println("中缀表达式：" + infixExpressionList);
        List<String> suffixExpressionList = parseSuffixExpressionList(infixExpressionList);
        System.out.println("后缀表达式：" + suffixExpressionList);
        System.out.println("后缀表达式的结果 = " + calculate(suffixExpressionList));
    /**
     * 将中缀表达式转为List 上面的中缀表达式存入List得到的结果:[1, +, (, (, 2, +, 3, ), ×, 4, ), -, 5]
     */
    public static List<String> toInfixExpressionList(String s) {
        //存放中缀表达式内容
        ArrayList<String> list = new ArrayList<>();
        //定义指针，遍历中缀表达式
        int i = 0;
        //多位拼接
        String str;
        char c;
        do {
            //c为非数字
            if ((c = s.charAt(i)) < 48 || (c = s.charAt(i)) > 57) {
                list.add("" + c);
                //后移
                i++;
            } else {
                //多位数
                str = "";
                while (i < s.length() && (c = s.charAt(i)) >= 48 && (c = s.charAt(i)) <= 57) {
                    str += c;
                    i++;
                }
                list.add(str);
            }
        } while (i < s.length());
        return list;
    }
    /**
     * 将得到的中缀表达式转换成 后缀表达式
     */
    public static List<String> parseSuffixExpressionList(List<String> list) {
        // 定义栈 符号栈
        Stack<String> s1 = new Stack<String>();
        //存储中间结果的栈，使用List方便操作
        List<String> s2 = new ArrayList<String>();
        //遍历list
        for (String item : list) {
            //为数，入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();
            } else {
                //item的优先级比s1栈顶的优先级小,将s1栈顶的运算符弹出并压入到s2中，再次转到与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());
        }
        //存放到list，正常输入就是逆波兰表达式
        return s2;
    }
    /**
     * 表达式 存入ArrayList中
     * @param suffixExpression
     * @return String[]
     */
    public static List<String> getListString(String suffixExpression) {
        //将表达式分割
        String[] spilt = suffixExpression.split(" ");
        List<String> list = new ArrayList<String>();
        for (String ele : spilt) {
            list.add(ele);
        }
        return list;
    }
    // 逆波兰表达式的运算
    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("运算符有问题，不属于四则运算符号");
                }
                stack.push("" + 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;
    }
}

Java数据结构与算法一2

双向链表

分析双向链表的CRUD

单向环形链表

应用场景

Josehu 问题分析

分析思路

遍历环形链表

出队顺序

栈 stack

出栈（pop）、入栈（push）结构

应用场景

栈的快速入门

栈实现综合案例-计算器

思路分析（使用中缀表达式）

前缀(波兰表达式)

计算机求职

中缀

后缀

计算规则

逆波兰计算器

分析

中缀转后缀

分析步骤

热门文章

最新文章

相关课程

相关电子书

相关实验场景

热门

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件

Java数据结构与算法 一2

双向链表

分析双向链表的CRUD

单向环形链表

应用场景

Josehu 问题 分析

分析思路

遍历环形链表

出队顺序

栈 stack

出栈（pop） 、入栈（push）结构

应用场景

栈的快速入门

栈实现综合案例-计算器

思路分析 （使用中缀表达式）

前缀(波兰表达式)

计算机求职

中缀

后缀

计算规则

逆波兰计算器

分析

中缀转后缀

分析步骤

热门文章

最新文章

相关课程

相关电子书

相关实验场景

Java数据结构与算法一2

Josehu 问题分析

出栈（pop）、入栈（push）结构

思路分析（使用中缀表达式）