第 5 章栈

喜欢ヅ旅行 2022-11-24 14:27 102阅读 0赞

# 第 5 章 栈 #

## 1、栈的基本介绍 ##

### 1.1、栈的实际需求 ###

*  请计算表达式：\[7*2*2-5+1-5+3-3\] 的值
 *  请问: 计算机**底层**是如何运算得到结果的？ 注意不是简单的把算式列出运算，因为我们看这个算式 7 \* 2 \* 2 - 5，但是计算机怎么理解这个算式的
 *  对计算机而言， 它接收到的就是一个**字符串**， 我们讨论的是这个问题：**栈**

![image-20200714141702173][]

### 1.2、栈的基本性质 ###

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

![image-20200714141818548][]

### 1.3、栈的应用场景 ###

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

## 2、数组模拟栈 ##

### 2.1、代码思路 ###

*  maxSize ：栈的大小（数组的大小）
 *  arr ：用来模拟栈的数组
 *  top ：指向当前栈顶元素，初始值为 -1 ，表示栈空
 *  判断栈满：**top == maxSize** ，即已经到达数组最后一个位置
 *  判断栈空：**top == -1**
 *  入栈：**arr\[++top\] = arr;**
 *  出栈：**return arr\[top–\] ;**

![image-20200806154218722][]

### 2.2、代码实现 ###

*  栈的定义

//定义一个 ArrayStack 表示栈
    class ArrayStack {
        
    	private int maxSize; // 栈的大小
    	private int[] stack; // 数组，数组模拟栈，数据就放在该数组
    	private int top = -1;// 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;
    	}
    
    	// 入栈-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 static void main(String[] args) {
        
        // 测试一下ArrayStack 是否正确
        // 先创建一个ArrayStack对象->表示栈
        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("exit: 退出程序");
            System.out.println("push: 表示添加数据到栈(入栈)");
            System.out.println("pop: 表示从栈取出数据(出栈)");
            System.out.println();
            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) {
        
                        // TODO: handle exception
                        System.out.println(e.getMessage());
                    }
                    break;
                case "exit":
                    scanner.close();
                    loop = false;
                    break;
                default:
                    break;
            }
        }
    
        System.out.println("程序退出~~~");
    }

*  程序运行结果

show: 表示显示栈
    exit: 退出程序
    push: 表示添加数据到栈(入栈)
    pop: 表示从栈取出数据(出栈)
    
    请输入你的选择
    push
    请输入一个数
    1
    show: 表示显示栈
    exit: 退出程序
    push: 表示添加数据到栈(入栈)
    pop: 表示从栈取出数据(出栈)
    
    请输入你的选择
    push
    请输入一个数
    2
    show: 表示显示栈
    exit: 退出程序
    push: 表示添加数据到栈(入栈)
    pop: 表示从栈取出数据(出栈)
    
    请输入你的选择
    push
    请输入一个数
    3
    show: 表示显示栈
    exit: 退出程序
    push: 表示添加数据到栈(入栈)
    pop: 表示从栈取出数据(出栈)
    
    请输入你的选择
    push
    请输入一个数
    4
    show: 表示显示栈
    exit: 退出程序
    push: 表示添加数据到栈(入栈)
    pop: 表示从栈取出数据(出栈)
    
    请输入你的选择
    push
    请输入一个数
    5
    栈满
    show: 表示显示栈
    exit: 退出程序
    push: 表示添加数据到栈(入栈)
    pop: 表示从栈取出数据(出栈)
    
    请输入你的选择
    show
    stack[3]=4
    stack[2]=3
    stack[1]=2
    stack[0]=1
    show: 表示显示栈
    exit: 退出程序
    push: 表示添加数据到栈(入栈)
    pop: 表示从栈取出数据(出栈)
    
    请输入你的选择
    pop
    出栈的数据是 4
    show: 表示显示栈
    exit: 退出程序
    push: 表示添加数据到栈(入栈)
    pop: 表示从栈取出数据(出栈)
    
    请输入你的选择
    pop
    出栈的数据是 3
    show: 表示显示栈
    exit: 退出程序
    push: 表示添加数据到栈(入栈)
    pop: 表示从栈取出数据(出栈)
    
    请输入你的选择
    pop
    出栈的数据是 2
    show: 表示显示栈
    exit: 退出程序
    push: 表示添加数据到栈(入栈)
    pop: 表示从栈取出数据(出栈)
    
    请输入你的选择
    pop
    出栈的数据是 1
    show: 表示显示栈
    exit: 退出程序
    push: 表示添加数据到栈(入栈)
    pop: 表示从栈取出数据(出栈)
    
    请输入你的选择
    pop
    栈空，没有数据~
    show: 表示显示栈
    exit: 退出程序
    push: 表示添加数据到栈(入栈)
    pop: 表示从栈取出数据(出栈)
    
    请输入你的选择

### 2.3、数组模拟栈全部代码 ###

public class ArrayStackDemo {
        
    
    	public static void main(String[] args) {
        
    		// 测试一下ArrayStack 是否正确
    		// 先创建一个ArrayStack对象->表示栈
    		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("exit: 退出程序");
    			System.out.println("push: 表示添加数据到栈(入栈)");
    			System.out.println("pop: 表示从栈取出数据(出栈)");
    			System.out.println();
    			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) {
        
    					// TODO: handle exception
    					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;// 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;
    	}
    
    	// 入栈-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]);
    		}
    	}
    
    }

### 2.4、课后练习 ###

*  使用链表模拟栈

## 3、栈实现综合计算器(中缀表达式) ##

### 3.1、代码思路 ###

*  栈分为两个栈：
    
     *  **数栈（numStack）**：存储表达式中的数字
     *  **符号栈（operStack）**：存储表达式中的符号
 *  扫描表达式（这里并没有考虑括号）：
    
     *  **对于数：扫描到数，则直接压入数栈**
     *  对于运算符：扫描到运算符，分为如下几种情况：
        
         *  **如果符号栈为空，则直接入栈**
         *  **如果符号栈不为空**：
            
             *  **如果当前扫描到的运算符的优先级 <= 符号栈栈顶的运算符的优先级**，说明上次的运算符优先级较高，先执行优先级高的运算
                
                 *  从数栈中弹出两个数，根据符号栈栈顶的运算符进行运算（优先级高，就先算出来）
                 *  然后将计算的结果压入栈中
                 *  再将当前运算符压入符号栈
             *  **如果当前扫描到的运算符的优先级 > 符号栈栈顶的运算符的优先级**，说明上次的运算符优先级较低，直接压入符号栈
 *  何时停止循环？
    
     *  处理完表达式，退出循环
     *  即表达式下标（index）的值大于表达式（expression）的长度
     *  代码：**index >= expression.length()**
 *  表达式扫描完成：
    
     *  此时符号栈中的运算符优先级都相同
     *  从数栈中弹出两个数，再从符号栈中弹出一个运算符，进行运算，计算结果放回数栈中
     *  何时停止循环？符号栈为空则停止：**operStack.isEmpty()**
     *  表达式的值？符号栈为空时，数栈栈顶还有一个元素，这个元素的值就是表达式的值
 *  举例：3+2\*6-2
    
     *  首先
        
         *  将 3 压入数栈
         *  将 + 压入符号栈
         *  将 2 压入数栈
    
        2
        3	  +
        数栈	符号栈
    
     *  由于 \* 优先级大于 + ，所以将 \* 压入 符号栈，然后将 6 压入数栈
    
        6
        2	  *
        3	  +
        数栈	符号栈
    
     *  由于 - 优先级低于 \* ，所以从数栈中弹出两个数（6 和 2），从符号栈中弹出一个运算符（\*），进行运算，运算结果再压入数栈，然后将 - 压入符号栈
    
        12	  -
        3	  +
        数栈	符号栈
    
     *  将 2 压入数栈，表达式处理完毕
    
        2
        12	  -
        3	  +
        数栈	符号栈
    
     *  重复此过程，直至符号栈为空：从数栈中弹出两个数，再从符号栈中弹出一个运算符，进行运算，计算结果放回数栈中
    
        10
        3	  +
        数栈	符号栈
    
        13
        数栈	符号栈

![image-20200806154735790][]

### 3.2、代码实现 ###

*  栈的定义：专为计算器而生的栈
 *  对于乘除法特别说明：由于**栈先进后**出的特点，num1 是运算符后面的数（减数、除数），num2 是运算符前的数（被减数、被除数），**特别需要注意减法与除法的顺序**
    
     *  **res = num2 - num1;**
     *  **res = num2 / num1;**

//先创建一个栈,直接使用前面创建好
    //定义一个 CalcStack 表示栈, 需要扩展功能
    class CalcStack {
        
    	private int maxSize; // 栈的大小
    	private int[] stack; // 数组，数组模拟栈，数据就放在该数组
    	private int top = -1;// top表示栈顶，初始化为-1
    
    	// 构造器
    	public CalcStack(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;
    	}
    
    }

*  综合计算器代码：对多位数进行了判断，使得程序可处理多位数的运算

public static void main(String[] args) {
        
        // 根据前面老师思路，完成表达式的运算
        String expression = "7*2*2-5+1-5+3-4"; // 如何处理多位数的问题？
        // 创建两个栈，一个数栈，一个符号栈
        CalcStack numStack = new CalcStack(10);
        CalcStack operStack = new CalcStack(10);
        // 定义需要的相关变量
        int index = 0;// 用于扫描
        int num1 = 0;
        int num2 = 0;
        int oper = 0;
        int res = 0;
        char ch = ' '; // 将每次扫描得到char保存到ch
        String keepNum = ""; // 用于拼接 多位数
        // 开始while循环的扫描expression
        while (true) {
        
            // 依次得到expression 的每一个字符
            ch = expression.substring(index, index + 1).charAt(0);
            // 判断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); //? "1+3" '1' => 1
                // 分析思路
                // 1. 当处理多位数时，不能发现是一个数就立即入栈，因为他可能是多位数
                // 2. 在处理数，需要向expression的表达式的index 后再看一位,如果是数就进行扫描，如果是符号才入栈
                // 3. 因此我们需要定义一个变量 字符串，用于拼接
    
                // 处理多位数
                keepNum += ch;
    
                // 如果ch已经是expression的最后一位，就直接入栈
                if (index == expression.length() - 1) {
        
                    numStack.push(Integer.parseInt(keepNum));
                } else {
        
    
                    // 判断下一个字符是不是数字，如果是数字，就继续扫描，如果是运算符，则入栈
                    // 注意是看后一位，不是index++
                    if (operStack.isOper(expression.substring(index + 1, index + 2).charAt(0))) {
        
                        // 如果后一位是运算符，则入栈 keepNum = "1" 或者 "123"
                        numStack.push(Integer.parseInt(keepNum));
                        // 重要的!!!!!!, 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出，就是结果
        res = numStack.pop();
        System.out.printf("表达式 %s = %d", expression, res);
    }

*  程序运行结果

表达式 7*2*2-5+1-5+3-4 = 18

### 3.3、综合计算器全部代码 ###

public class Calculator {
        
    
    	public static void main(String[] args) {
        
    		// 根据前面老师思路，完成表达式的运算
    		String expression = "7*2*2-5+1-5+3-4"; // 如何处理多位数的问题？
    		// 创建两个栈，一个数栈，一个符号栈
    		CalcStack numStack = new CalcStack(10);
    		CalcStack operStack = new CalcStack(10);
    		// 定义需要的相关变量
    		int index = 0;// 用于扫描
    		int num1 = 0;
    		int num2 = 0;
    		int oper = 0;
    		int res = 0;
    		char ch = ' '; // 将每次扫描得到char保存到ch
    		String keepNum = ""; // 用于拼接 多位数
    		// 开始while循环的扫描expression
    		while (true) {
        
    			// 依次得到expression 的每一个字符
    			ch = expression.substring(index, index + 1).charAt(0);
    			// 判断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); //? "1+3" '1' => 1
    				// 分析思路
    				// 1. 当处理多位数时，不能发现是一个数就立即入栈，因为他可能是多位数
    				// 2. 在处理数，需要向expression的表达式的index 后再看一位,如果是数就进行扫描，如果是符号才入栈
    				// 3. 因此我们需要定义一个变量 字符串，用于拼接
    
    				// 处理多位数
    				keepNum += ch;
    
    				// 如果ch已经是expression的最后一位，就直接入栈
    				if (index == expression.length() - 1) {
        
    					numStack.push(Integer.parseInt(keepNum));
    				} else {
        
    
    					// 判断下一个字符是不是数字，如果是数字，就继续扫描，如果是运算符，则入栈
    					// 注意是看后一位，不是index++
    					if (operStack.isOper(expression.substring(index + 1, index + 2).charAt(0))) {
        
    						// 如果后一位是运算符，则入栈 keepNum = "1" 或者 "123"
    						numStack.push(Integer.parseInt(keepNum));
    						// 重要的!!!!!!, 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出，就是结果
    		res = numStack.pop();
    		System.out.printf("表达式 %s = %d", expression, res);
    	}
    
    }
    
    //先创建一个栈,直接使用前面创建好
    //定义一个 CalcStack 表示栈, 需要扩展功能
    class CalcStack {
        
    	private int maxSize; // 栈的大小
    	private int[] stack; // 数组，数组模拟栈，数据就放在该数组
    	private int top = -1;// top表示栈顶，初始化为-1
    
    	// 构造器
    	public CalcStack(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;
    	}
    
    }

### 3.4、课后练习 ###

*  加入小括号的判断：小括号内的运算需要优先执行，也即小括号的优先级最高
 *  我的代码思路如下：
    
     *  **但凡遇到左括号，直接入符号栈**，之后的操作和之前的一样
     *  **直至遇到右括号**，此时可以依次将符号栈中的符号弹出，与数栈中的数做运算
     *  **直至符号栈弹出左括号为止，此时，括号内的运算已执行完毕**

## 4、前缀 中缀 后缀表达式 ##

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

#### 4.1.1、前缀表达式 ####

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

#### 4.1.2、前缀表达式的计算机求值 ####

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

### 4.2、中缀表达式 ###

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

### 4.3、后缀表达式 ###

#### 4.3.1、后缀表达式 ####

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

<table> 
 <thead> 
  <tr> 
   <th>正常的表达式</th> 
   <th>逆波兰表达式</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>a+b</td> 
   <td>a b +</td> 
  </tr> 
  <tr> 
   <td>a+(b-c)</td> 
   <td>a b c - +</td> 
  </tr> 
  <tr> 
   <td>a+(b-c)*d</td> 
   <td>a b c – d * +</td> 
  </tr> 
  <tr> 
   <td>a+d*(b-c)</td> 
   <td>a d b c - * +</td> 
  </tr> 
  <tr> 
   <td>a=1+3</td> 
   <td>a 1 3 + =</td> 
  </tr> 
 </tbody> 
</table>

#### 4.3.2、后缀表达式的计算机求值 ####

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

## 5、逆波兰计算器 ##

### 5.1、计算器说明 ###

*  输入一个逆波兰表达式(后缀表达式)， 使用栈(Stack)，计算其结果
 *  支持小括号和多位数整数， 因为这里我们主要讲的是数据结构， 因此计算器进行简化， 只支持对整数的计算

### 5.2、代码思路 ###

*  **计算后缀表达式无需考虑运算符优先级问题，所以只需要一个数栈即可**
 *  分为两种情况：
    
     *  **遇到数：压入数栈**
     *  **遇到运算符：从数栈中弹出两个数，进行计算，计算结果压入数栈**
 *  何时计算完成？处理完表达式就代表计算完成

### 5.3、代码实现 ###

*  出栈的两个数：num2 和 num1
    
     *  num2 先出栈，所以 num2 是减数或除数
     *  num1 后出栈，所以 num1 是被减数或被除数

public class PolandNotation {
        
    
    	public static void main(String[] args) {
        
    		
    		//先定义给逆波兰表达式
    		// 4 * 5 - 8 + 60 + 8 / 2 => 4 5 * 8 - 60 + 8 2 / + 
    		//说明为了方便，逆波兰表达式 的数字和符号使用空格隔开
    		String suffixExpression = "4 5 * 8 - 60 + 8 2 / +"; // 76
    		//思路
    		//1. 先将逆波兰表达式 => 放到ArrayList中
    		//2. 将 ArrayList 传递给一个方法，遍历 ArrayList 配合栈 完成计算
    		
    		List<String> list = getListString(suffixExpression);
    		System.out.println("rpnList=" + list);
    		int res = calculate(list);
    		System.out.println("计算的结果是=" + res);
    
    	}
    	
    	//将一个逆波兰表达式， 依次将数据和运算符 放入到 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());
    	}
    
    }

*  程序运行结果

rpnList=[4, 5, *, 8, -, 60, +, 8, 2, /, +]
    计算的结果是=76

## 6、中缀表达式转后缀表达式 ##

### 6.1、代码思路 ###

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

1.  初始化两个栈：**运算符栈operStack**和**储存中间结果的栈tempStack**；
2.  **从左至右扫描中缀表达式；**
3.  **遇到操作数时，将其压tempStack；**
4.  **遇到运算符时，比较其与operStack栈顶运算符的优先级：**
    
    1.  **如果operStack为空，或栈顶运算符为左括号“(”，则直接将此运算符入tempStack栈（分如下两种情况）**
        
         *  operStack 栈顶为空：之前的优先级别高的运算已经处理完成，已经得到了一个结果，将当前运算符直接压入 operStack 栈即可
         *  operStack 栈顶为左括号：我都挨着左括号了，我要和它同生共死！当把我从operStack 出栈，用于运算后，这对括号中的表达式的值也就计算出来了
    2.  **如果当前运算符优先级比栈顶运算符的高，也将运算符压入tempStack（当前运算符优先级高，先执行运算）**
    3.  **否则，当前运算符优先级 <= 栈顶运算符优先级，将operStack栈顶的运算符弹出并压入到tempStack中（operStack 栈顶运算符优先级高，先执行运算），再次转到(4.1)与operStack中新的栈顶运算符相比较**（分如下两种情况）；
        
         *  一直循环，将 tempStack 栈顶元素取出，直到在 operStack 栈中找到比当前运算符优先级高的运算符，让其先执行运算
         *  如果在 tempStack 栈中找不到比当前运算符优先级高的运算符，则会直接将 operStack 栈掏空，然后将当前运算符压入 tempStack 栈中（放在栈底）
5.  **遇到括号时：**
    
    1.  如果是左括号“(”，则直接压入operStack，等待与其配对的右括号，因为括号中的表达式需要优先运算
    2.  如果是右括号“)”，则依次弹出operStack栈顶的运算符，并压入tempStack，直到遇到左括号为止，此时将这一对括号丢弃（此时括号内的运算完成，并将结果压入了tempStack）
6.  重复步骤2至5，直到表达式的最右边
7.  **将operStack中剩余的运算符依次弹出并压入tempStack**（operStack 栈中剩下的运算都是优先级相同的运算符，按顺序执行即可）
8.  **依次弹出tempStack中的元素并输出，结果的逆序即为中缀表达式对应的后缀表达式**

![image-20200806163150886][]

### 6.2、举例说明 ###

*  举例说明：将中缀表达 式“1+((2+3)×4)-5”转换为后缀表达式的过程如下
 *  因此结果为：“1 2 3 + 4 × + 5 –”

<table> 
 <thead> 
  <tr> 
   <th>扫描到的元素</th> 
   <th>tempStack(栈底-&gt;栈顶)</th> 
   <th>operStack(栈底-&gt;栈顶)</th> 
   <th>说明</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>1</td> 
   <td>1</td> 
   <td>空</td> 
   <td>数字，直接入栈</td> 
  </tr> 
  <tr> 
   <td>+</td> 
   <td>1</td> 
   <td>+</td> 
   <td>s1为空，运算符直接入栈</td> 
  </tr> 
  <tr> 
   <td>(</td> 
   <td>1</td> 
   <td>+ (</td> 
   <td>左括号，直接入栈</td> 
  </tr> 
  <tr> 
   <td>(</td> 
   <td>1</td> 
   <td>+ ( (</td> 
   <td>同上</td> 
  </tr> 
  <tr> 
   <td>2</td> 
   <td>1 2</td> 
   <td>+ ( (</td> 
   <td>数字</td> 
  </tr> 
  <tr> 
   <td>+</td> 
   <td>1 2</td> 
   <td>+ ( ( +</td> 
   <td>s1栈顶为左括号，运算符直接入栈</td> 
  </tr> 
  <tr> 
   <td>3</td> 
   <td>1 2 3</td> 
   <td>+ ( ( +</td> 
   <td>数字</td> 
  </tr> 
  <tr> 
   <td>)</td> 
   <td>1 2 3 +</td> 
   <td>+ (</td> 
   <td>右括号，弹出运算符直至遇到左括号</td> 
  </tr> 
  <tr> 
   <td>×</td> 
   <td>1 2 3 +</td> 
   <td>+ ( ×</td> 
   <td>s1栈顶为左括号，运算符直接入栈</td> 
  </tr> 
  <tr> 
   <td>4</td> 
   <td>1 2 3 + 4</td> 
   <td>+ ( ×</td> 
   <td>数字</td> 
  </tr> 
  <tr> 
   <td>)</td> 
   <td>1 2 3 + 4 ×</td> 
   <td>+</td> 
   <td>右括号，弹出运算符直至遇到左括号</td> 
  </tr> 
  <tr> 
   <td>-</td> 
   <td>1 2 3 + 4 × +</td> 
   <td>-</td> 
   <td>-与+优先级相同，因此弹出+，再压入-</td> 
  </tr> 
  <tr> 
   <td>5</td> 
   <td>1 2 3 + 4 × + 5</td> 
   <td>-</td> 
   <td>数字</td> 
  </tr> 
  <tr> 
   <td>到达最右端</td> 
   <td><strong>1 2 3 + 4 × + 5 -</strong></td> 
   <td>空</td> 
   <td>s1中剩余的运算符</td> 
  </tr> 
 </tbody> 
</table>

### 6.3、代码实现 ###

*  将中缀表达式转为对应的 List ：将数字和运算符分开，存储在 `List<String>` 对象中

// 方法：将 中缀表达式转成对应的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;// 返回
    }

*  将中缀表达式（List）转为后缀表达式（List）
    
     *  如果是一个数，加入tempList
     *  如果是 ( ，则直接入operStack（括号内的表达式优先计算）
     *  如果是 ) ，则依次弹出 operStack 栈顶的运算符，并压入 tempList ，直到遇到左括号为止，此时将这一对括号丢弃（括号内的表达式优先计算）
     *  否则比较当前运算符和栈顶运算符优先级
        
         *  当前运算符优先级 > 栈顶运算符，将当前运算符压入 operStack 栈中（当前运算符优先级较高，先进行运算）
         *  当前运算符优先级 <= 栈顶运算符，将 operStack 栈顶运算符取出，压入 tempList 中，再次对新的栈顶元素进行优先级判断（之前的运算符优先级较高，先进行运算）

// 即 ArrayList [1,+,(,(,2,+,3,),*,4,),-,5] =》 ArrayList [1,2,3,+,4,*,+,5,–]
    // 方法：将得到的中缀表达式对应的List => 后缀表达式对应的List
    public static List<String> parseSuffixExpreesionList(List<String> ls) {
        
        // 定义两个栈
        Stack<String> operStack = new Stack<String>(); // 符号栈
        // 说明：因为tempList 这个栈，在整个转换过程中，没有pop操作，而且后面我们还需要逆序输出
        // 因此比较麻烦，这里我们就不用 Stack<String> 直接使用 List<String> tempList
        // Stack<String> tempStack = new Stack<String>(); // 储存中间结果的栈tempStack
        List<String> tempList = new ArrayList<String>(); // 储存中间结果的tempList
    
        // 遍历ls
        for (String item : ls) {
        
            if (item.matches("\\d+")) {
         // 如果是一个数，加入tempList
                tempList.add(item);
            } else if (item.equals("(")) {
         // 如果是 ( ，则直接入operStack
                operStack.push(item);
            } else if (item.equals(")")) {
         // 如果是 ) ，则将括号内的值算出，并压入 tempList）
                // 如果是右括号“)”，则依次弹出operStack栈顶的运算符，并压入tempList，直到遇到左括号为止，此时将这一对括号丢弃
                while (!operStack.peek().equals("(")) {
        
                    tempList.add(operStack.pop());
                }
                operStack.pop();// !!! 将 ( 弹出 s1栈， 消除小括号
            } else {
         // 否则比较当前运算符和栈顶运算符优先级
                // 当item的优先级小于等于operStack栈顶运算符,
                // 将operStack栈顶的运算符弹出并加入到tempList中，再次转到(4.1)与operStack中新的栈顶运算符相比较
                // 问题：我们缺少一个比较优先级高低的方法
                while (operStack.size() != 0 && Operation.getValue(operStack.peek()) >= Operation.getValue(item)) {
        
                    tempList.add(operStack.pop());
                }
                // 还需要将item压入栈
                operStack.push(item);
            }
        }
    
        // 将operStack中剩余的运算符依次弹出并加入tempList
        while (operStack.size() != 0) {
        
            tempList.add(operStack.pop());
        }
    
        return tempList; // 注意因为是存放到List, 因此按顺序输出就是对应的后缀表达式对应的List
    
    }

*  测试代码：
    
     *  将中缀表达式转为对应的 List
     *  将中缀表达式 List 转为后缀表达式 List
     *  调用逆波兰计算器执行计算

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)); // ?
    
    }

*  程序运行结果

中缀表达式对应的List=[1, +, (, (, 2, +, 3, ), *, 4, ), -, 5]
    后缀表达式对应的List[1, 2, 3, +, 4, *, +, 5, -]
    expression=16

### 6.4、中缀表达式转后缀表达式完整代码 ###

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)); // ?
    
    	}
    
    	// 方法：将 中缀表达式转成对应的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 [1,+,(,(,2,+,3,),*,4,),-,5] =》 ArrayList [1,2,3,+,4,*,+,5,–]
    	// 方法：将得到的中缀表达式对应的List => 后缀表达式对应的List
    	public static List<String> parseSuffixExpreesionList(List<String> ls) {
        
    		// 定义两个栈
    		Stack<String> operStack = new Stack<String>(); // 符号栈
    		// 说明：因为tempList 这个栈，在整个转换过程中，没有pop操作，而且后面我们还需要逆序输出
    		// 因此比较麻烦，这里我们就不用 Stack<String> 直接使用 List<String> tempList
    		// Stack<String> tempStack = new Stack<String>(); // 储存中间结果的栈tempStack
    		List<String> tempList = new ArrayList<String>(); // 储存中间结果的tempList
    
    		// 遍历ls
    		for (String item : ls) {
        
    			if (item.matches("\\d+")) {
         // 如果是一个数，加入tempList
    				tempList.add(item);
    			} else if (item.equals("(")) {
         // 如果是 ( ，则直接入operStack
    				operStack.push(item);
    			} else if (item.equals(")")) {
         // 如果是 ) ，则将括号内的值算出，并压入 tempList）
    				// 如果是右括号“)”，则依次弹出operStack栈顶的运算符，并压入tempList，直到遇到左括号为止，此时将这一对括号丢弃
    				while (!operStack.peek().equals("(")) {
        
    					tempList.add(operStack.pop());
    				}
    				operStack.pop();// !!! 将 ( 弹出 s1栈， 消除小括号
    			} else {
         // 否则比较当前运算符和栈顶运算符优先级
    				// 当item的优先级小于等于operStack栈顶运算符,
    				// 将operStack栈顶的运算符弹出并加入到tempList中，再次转到(4.1)与operStack中新的栈顶运算符相比较
    				// 问题：我们缺少一个比较优先级高低的方法
    				while (operStack.size() != 0 && Operation.getValue(operStack.peek()) >= Operation.getValue(item)) {
        
    					tempList.add(operStack.pop());
    				}
    				// 还需要将item压入栈
    				operStack.push(item);
    			}
    		}
    
    		// 将operStack中剩余的运算符依次弹出并加入tempList
    		while (operStack.size() != 0) {
        
    			tempList.add(operStack.pop());
    		}
    
    		return tempList; // 注意因为是存放到List, 因此按顺序输出就是对应的后缀表达式对应的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 LEFT_BRACKET  = 0;
    	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 = LEFT_BRACKET;
    			break;
    		case "+":
    			result = ADD;
    			break;
    		case "-":
    			result = SUB;
    			break;
    		case "*":
    			result = MUL;
    			break;
    		case "/":
    			result = DIV;
    			break;
    		default:
    			System.out.println("不存在该运算符" + operation);
    			break;
    		}
    		return result;
    	}
    
    }

## 7、完整版逆波兰计算器 ##

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();
            }
        }
    
    }

[image-20200714141702173]: /images/20221124/0114a879327442e9bec87d00d1af08d8.png
[image-20200714141818548]: /images/20221124/c2e24e311cc247e39e3584e391d2d958.png
[image-20200806154218722]: /images/20221124/bafb9909d0e24b0a8314852cc5e43037.png
[image-20200806154735790]: /images/20221124/a54c23f20e6f479f9629278c66926fd7.png
[image-20200806163150886]: /images/20221124/6471cd9065c94444b790c7c52ee85c00.png