学习来源–>传送门–>尚硅谷Java数据结构与java算法（Java数据结构与算法）

---

案例引入;
一个计算器的运算原理

比如说 输入 5*6+3-2 ;计算器收到的是一个字符串,他就得一个一个分隔这些字符;然后计算;

栈(Stack) 先进后出的有序列表结构;(FILO)
最先放入的元素在栈底,最后放入的在栈顶;

1.栈的基本实现

自定义实现的话,这里直接用数组作为底层存储数据结构;
初始化栈时,定义栈顶的指针为 -1 ;入栈一个,就让栈顶加+1;然后数组存入一个元素;出栈一个,就让栈顶减1;取出元素;

//用数组实现栈;
class StackByArray{//栈的容量;private int capacity;//栈顶指针; 默认指向 -1private int top = -1;//栈存储数据; 使用数组;private int[] data;//初始化;public StackByArray(int capacity) {this.capacity = capacity;data = new int[capacity];}//空栈判断;public boolean isEmpty(){return top == -1;}//判断满栈;public boolean isFull(){return top == capacity - 1;}//入栈方法;public void push(int ele){//先判断是否栈满;if(isFull()){System.out.println("栈满,不可入栈");return;}//指针上移;添加元素;top++;data[top] = ele;}//出栈方法;public int pop(){//先判断空栈;if(isEmpty()){throw  new RuntimeException("空栈,无法取出元素.");}//先把要出栈的元素值存起来;int temp = data[top];//指针下移;top--;System.out.println("出栈的是-->"+temp);return temp;}//遍历此栈;public void getAll(){//先去除空栈的情况;if(isEmpty()){System.out.println("空栈,不遍历");}for (int i = top; i >=0 ; i--) {System.out.println("栈内元素->"+data[i]);}}//获取查看的栈顶;public int getHead() {if (isEmpty()) {throw new RuntimeException("空栈,不用看栈顶");}System.out.println("当前栈顶为->" + data[top]);return data[top];}
}

测试

public class TestStack01 {//测试;public static void main(String[] args) {StackByArray stack = new StackByArray(6);//入栈;stack.push(3);stack.push(2);stack.push(1);stack.push(3);stack.push(6);stack.push(9);//栈满,不可入栈;stack.push(10);//遍历;stack.getAll();//看看栈顶;stack.getHead();System.out.println("---出栈-----");stack.pop();//看栈顶;stack.getHead();//遍历;stack.getAll();}
}

栈满,不可入栈
元素->9
元素->6
元素->3
元素->1
元素->2
元素->3
当前栈顶为->9
---出栈-----
出栈的是-->9
当前栈顶为->6
元素->6
元素->3
元素->1
元素->2
元素->3

2.使用栈实现一个基础的计算器(中缀表达式)

这里不考虑小括号

拿到一个表达式,数字直接就进左边的数字栈,
符号入栈时要分情况

若符号栈为空栈,这个符号直接入栈即可;
若符号栈不是空栈–>

1)待入栈的符号,优先级要是大于符号栈的栈顶优先级;直接入栈;
2)待入栈的符号,优先级小于或者说等于栈里的栈顶优先级,就让左边的数字栈出栈两个数字;符号栈出来一个栈顶符号;计算的结果存入数字栈; 然后 这个待入栈的元素才能入栈;

然后,表达式的数字和符号都分配结束后,分别出栈计算,最后数字栈的元素就是结果;

比如说计算 3 + 2 * 6 - 2

3进入数字栈 ;
+进入符号栈;
2进入数字栈;

* 进入符号栈时,先比较优先级; * 优先级高于+;
*直接进入符号栈;

然后6进入数字栈;

这时-要准备进入符号栈,但是-优先级小于栈顶* 的优先级;
在数字栈抛出6 和2,在符号栈抛出* ,2 * 6运算得到12 ;这个计算得到的12放入数字栈;
然后再把-放入符号栈

然后把2放入符号栈

弹出12 - 2 ,计算得到10; 这时栈顶指针指向了+;
然后让10 + 3 计算 得到 13 即可

注意在存放数字时,字符对应的ascall码不一样;
相差48

(1)初步实现

还是在之前的数组实现的栈基础上进行实现;

public class CalculatorTest01 {public static void main(String[] args) {//测试;//输入计算的式子;String str = "2+9*8-1";//创建两个栈,一个放数字,一个放符号;StackByArray numStack = new StackByArray(15);StackByArray symbolStack = new StackByArray(15);//index,作为字符串的索引指针; 辅助作用;int index =0;//返回的结果;int result =0;//需要计算时的数字和符号;int num1 =0;int num2 =0;int symbol =0;//从公式中取出的字符char character = ' ';//现在要去遍历公式;取出单个字符;do {//注意取出单个字符时,这个index的值也在先向后移动;character = str.substring(index, index + 1).charAt(0);//判断运算符号;if (symbolStack.isSymbol(character)) {//里面还要分为两种情况; 空栈 ; 不是空栈的情况;if (!symbolStack.isEmpty()) {//1.运算字符栈不是空栈;那就继续分析这个栈的 栈顶元素优先级;if (symbolStack.getPriority(character) <= symbolStack.getPriority(symbolStack.getHead())) {//数字栈出两个数字;符号栈出一个符号;运算num1 = numStack.pop();num2 = numStack.pop();symbol = symbolStack.pop();result = numStack.getRes(num1, num2, symbol);//运算结果先放入数字栈;numStack.push(result);//然后再把符号放入符号栈;symbolStack.push(character);}//2.优先级大于运算符号栈的栈顶元素;else {symbolStack.push(character);}} else {//运算字符栈是空栈,直接入栈即可;symbolStack.push(character);}}//计算数字的;注意数字的字符 ascall吗实际差距为48;else {numStack.push(character - 48);}//终止条件;index++;} while (index < str.length());//以符号栈为空作为结束条件;while (!symbolStack.isEmpty()) {//计算;num1 = numStack.pop();num2 = numStack.pop();symbol = symbolStack.pop();result = numStack.getRes(num1, num2, symbol);//运算结果先放入数字栈;numStack.push(result);}System.out.println("-----计算结果为----->"+result);}
}//用数组实现的栈;
class StackByArray {//栈的容量;private int capacity;//栈顶指针; 默认指向 -1private int top = -1;//栈存储数据; 使用数组;private int[] data;//初始化;public StackByArray(int capacity) {this.capacity = capacity;data = new int[capacity];}//空栈判断;public boolean isEmpty() {return top == -1;}//判断满栈;public boolean isFull() {return top == capacity - 1;}//入栈方法;public void push(int ele) {//先判断是否栈满;if (isFull()) {System.out.println("栈满,不可入栈");return;}//指针上移;添加元素;top++;data[top] = ele;}//出栈方法;public int pop() {//先判断空栈;if (isEmpty()) {throw new RuntimeException("空栈,无法取出元素.");}//先把要出栈的元素值存起来;int temp = data[top];//指针下移;top--;System.out.println("出栈的是-->" + temp);return temp;}//遍历此栈;public void getAll() {//先去除空栈的情况;if (isEmpty()) {System.out.println("空栈,不遍历");}for (int i = top; i >= 0; i--) {System.out.println("栈内元素->" + data[i]);}}//获取查看的栈顶;public int getHead() {if (isEmpty()) {throw new RuntimeException("空栈,不用看栈顶");}System.out.println("当前栈顶为->" + data[top]);return data[top];}//首先是判断是否为符号;public boolean isSymbol(char symbol){return symbol=='+' || symbol=='-' || symbol=='*' || symbol=='/';}//给符号自定义优先级;越大优先级越高;public int getPriority(int symbol){if(symbol == '*' || symbol == '/'){return 1;}else if(symbol == '+' || symbol == '-'){return 0;} else {return -1;}}//计算的方法;public int getRes(int num1, int num2, int symbol){//得到的结果;int result =0;//判断计算的符号; 进行计算;switch (symbol){case '+':result = num2 + num1;break;case '-':result = num2 - num1;break;case '*':result = num2 * num1;break;case '/':result = num2 / num1;break;default:break;}return result;}
}

测试结果

当前栈顶为->43
当前栈顶为->42
出栈的是-->8
出栈的是-->9
出栈的是-->42
出栈的是-->1
出栈的是-->72
出栈的是-->45
出栈的是-->71
出栈的是-->2
出栈的是-->43
-----计算结果为----->73

这个计算的实现有基础功能,但是并不是很准确;
还有用字符表示数字;超过两位数字即无法计算;

(2)优化实现

在对字符进行判断时,要考虑到最后一个数字的情况,避免出现越界的异常错误

public class CalculatorTest02 {public static void main(String[] args) {//测试;//输入计算的式子;String str = "21+9/3-1*2-3";//创建两个栈,一个放数字,一个放符号;StackByArray numStack = new StackByArray(15);StackByArray symbolStack = new StackByArray(15);//index,作为字符串的索引指针; 辅助作用;int index =0;//返回的结果;int result =0;//需要计算时的数字和符号;int num1 =0;int num2 =0;int symbol =0;//从公式中取出的字符char character = ' ';//优化位置----------------------------------------->//优化时;这里多定义一个字符串;把两位数以上的数字字符拼接起来;String multipleStr = "";//现在要去遍历公式;取出单个字符;do {//注意取出单个字符时,这个index的值也在先向后移动;character = str.substring(index, index + 1).charAt(0);//判断运算符号;if (symbolStack.isSymbol(character)) {//里面还要分为两种情况; 空栈 ; 不是空栈的情况;if (!symbolStack.isEmpty()) {//1.运算字符栈不是空栈;那就继续分析这个栈的 栈顶元素优先级;if (symbolStack.getPriority(character) <= symbolStack.getPriority(symbolStack.getHead())) {//数字栈出两个数字;符号栈出一个符号;运算num1 = numStack.pop();num2 = numStack.pop();symbol = symbolStack.pop();result = numStack.getRes(num1, num2, symbol);//运算结果先放入数字栈;numStack.push(result);//然后再把符号放入符号栈;symbolStack.push(character);}//2.优先级大于运算符号栈的栈顶元素;else {symbolStack.push(character);}} else {//运算字符栈是空栈,直接入栈即可;symbolStack.push(character);}}//计算数字的;注意数字的字符 ascall吗实际差距为48;else {//numStack.push(character - 48);//优化位置----------------------------------------->//用定义的字符串拼接字符;multipleStr += character;//考虑最后一位字符的情况;if(index == str.length()-1){numStack.push(Integer.parseInt(multipleStr));}else {//截取字符是判断后面是否还有数字;if(symbolStack.isSymbol(str.substring(index+1,index+2).charAt(0))){numStack.push(Integer.parseInt(multipleStr));//清空拼接的字符串;multipleStr = "";}}}//终止条件;index++;} while (index < str.length());//以符号栈为空作为结束条件;while (!symbolStack.isEmpty()) {//计算;num1 = numStack.pop();num2 = numStack.pop();symbol = symbolStack.pop();result = numStack.getRes(num1, num2, symbol);//运算结果先放入数字栈;numStack.push(result);}System.out.println("-----计算结果为----->"+result);}
}//用数组实现的栈;
class StackByArray {//栈的容量;private int capacity;//栈顶指针; 默认指向 -1private int top = -1;//栈存储数据; 使用数组;private int[] data;//初始化;public StackByArray(int capacity) {this.capacity = capacity;data = new int[capacity];}//空栈判断;public boolean isEmpty() {return top == -1;}//判断满栈;public boolean isFull() {return top == capacity - 1;}//入栈方法;public void push(int ele) {//先判断是否栈满;if (isFull()) {System.out.println("栈满,不可入栈");return;}//指针上移;添加元素;top++;data[top] = ele;}//出栈方法;public int pop() {//先判断空栈;if (isEmpty()) {throw new RuntimeException("空栈,无法取出元素.");}//先把要出栈的元素值存起来;int temp = data[top];//指针下移;top--;System.out.println("出栈的是-->" + temp);return temp;}//遍历此栈;public void getAll() {//先去除空栈的情况;if (isEmpty()) {System.out.println("空栈,不遍历");}for (int i = top; i >= 0; i--) {System.out.println("栈内元素->" + data[i]);}}//获取查看的栈顶;public int getHead() {if (isEmpty()) {throw new RuntimeException("空栈,不用看栈顶");}System.out.println("当前栈顶为->" + data[top]);return data[top];}//首先是判断是否为符号;public boolean isSymbol(char symbol){return symbol=='+' || symbol=='-' || symbol=='*' || symbol=='/';}//给符号自定义优先级;越大优先级越高;public int getPriority(int symbol){if(symbol == '*' || symbol == '/'){return 1;}else if(symbol == '+' || symbol == '-'){return 0;} else {return -1;}}//计算的方法;public int getRes(int num1, int num2, int symbol){//得到的结果;int result =0;//判断计算的符号; 进行计算;switch (symbol){case '+':result = num2 + num1;break;case '-':result = num2 - num1;break;case '*':result = num2 * num1;break;case '/':result = num2 / num1;break;default:break;}return result;}
}

3.前缀,中缀,后缀表达式基础知识

前缀(波兰式) 运算符号在数字之前;
运算时 自右向左 扫描要计算的表达式;遇到数字就压入栈中;扫描到运算符号就弹出栈顶的两个数字;进行计算;算到的结果放入栈中;继续扫描表达式;
比如计算 (3+4) * 5 - 6 用前缀表达式写;就是- * + 3 4 5 6 ;

• 中缀表达式计算时,从右边开始扫描;遇到4个数字,那就全部压入栈中 栈底 6 -> 5 -> 4 -> 3 栈顶 ;
• 然后扫描到 + ,把栈顶的 3 和 4弹出;计算3+4 ;得出结果7,把7压入栈中;此时的栈;
• 栈底 6 -> 5 -> 7 -> 栈顶 ;
• 然后扫描到 - ,把栈顶的两个数字7 和 5弹出进行计算 7 * 5; 得到35 ;压入栈中;此时的栈;
• 栈底 6 -> 35 栈顶;
• 然后扫描到-,把两个数字35 和 6 弹出进行计算35 - 6 ;得到 29 此时扫描结束;得出结果;

中缀表达式就是平时常见的计算表达式;刚才在实现简易计算器时就已经用到了;

后缀表达式,也就是逆波兰表达式

例如计算(3+4) * 5 -6 时,用逆波兰表达式写出来就是3 4 + 5 * 6 -
从左向右扫描;

• 3 和 4 压入栈; 栈底 3-> 4 栈顶
• 扫描到+ ;弹出4 和 3,运算3 + 4 得到 7 ,压入栈中;
• 扫描到5,压入栈中;栈底 7 -> 5 栈顶;
• 扫描到* ,将7 和 5弹出;计算 7*5得到35,压入栈中’’
• 扫描到6;压入栈中 ;栈底 35 -> 6 栈顶;
• 扫描到-,将35 和 6 弹出;计算35 -6得到29;此时已扫描结束;

4. 逆波兰计算器简易实现

本次实现的计算器比较简易,仅支持整数,小数位没有优化;

public class ReversePolandTest01 {public static void main(String[] args) {//例如计算 (12+8) * 6 -10 ;//直接把数字和运算符用空格隔开;方便用字符串的方法分隔为一个个的数组;String suffixStr = "12 8 + 6 * 10 - ";//考虑用封装的方法将字符串分隔放到集合中;List<String> strings = toList(suffixStr);//System.out.println(strings);//计算;int i = toGetRes(strings);System.out.println(i);//得出结果110}//字符串存到集合;public static List<String> toList(String str) {//空格分隔字符串;String[] s = str.split(" ");//创建集合;准备存入字符串数组;ArrayList<String> arrayList = new ArrayList<>();Collections.addAll(arrayList, s);return arrayList;}//传入的集合计算;public static int toGetRes(List<String> list) {//创建一个栈即可;主要存数字;Stack<String> stack = new Stack<>();//把集合中的数取出;for (String s : list) {if (s.matches("\\d+")) {//若取到的是数字,直接入栈;stack.push(s);} else {int result = 0;//栈里出两个数字;注意计算时,第二次弹出的数字在前;int num1 = Integer.parseInt(stack.pop());int num2 = Integer.parseInt(stack.pop());//其他的字符进行匹配;if (s.equals("+")) {result = num2 + num1;} else if (s.equals("-")) {result = num2 - num1;} else if (s.equals("*")) {result = num2 * num1;} else if (s.equals("/")) {result = num2 / num1;} else {throw new RuntimeException("符号错误");}stack.push("" + result);}}return Integer.parseInt(stack.pop());}
}

5.中缀 转 后缀 表达式

1 + (( 2 + 3 ) * 4 ) - 5

从左至右扫描中缀表达式 ;
1放入栈S2

+ 入栈 S1

( 直接放入栈S1

2 入栈 S2 ;( 入栈S1

由于扫描到+ ;S1栈顶为 括号( ;那么+直接入栈S1

扫描到) ,就把S1的符号弹出压入S2,直到遇到一个( 左括号,并且( 左括号和)右括号消除;

扫描到*,直接放入S1;扫描到4,直接放入S2;

扫描到)右括号,那么直接把S1的运算符*弹出,放入到S1 ;直到遇到( 左括号;( 左括号 和) 右括号消除;

扫描到-,由于-和S1栈顶的+优先级相同,那么就先把S1的+弹出放入S2;

此时S1为空,直接把-放入S1;扫描到5,放入S2

S1中的元素依次弹出,进入S2

最终依次把S2的元素弹出,得到的表达式的逆序就是后缀表达式

具体实现

那么,在具体转换之前,还是像逆波兰计算器那样;
先把前缀表达式的字符串一个一个分隔开;存入集合;
在转为后缀表达式时,就不使用栈了;直接用集合;最终转换的也无需反转

public class InfixToSuffixTest {public static void main(String[] args) {//例如计算 (12+8) * 6 -10 ;//1.中缀表达式存入集合;String infixStr = "(12+8)*6-10";List<String> infixToList = infixToList(infixStr);//得到的中缀表达式集合;System.out.println(infixToList);//[(, 12, +, 8, ), *, 6, -, 10]//2.中缀表达式 集合 转为后缀表达式 集合;List<String> list = infixToSuffixList(infixToList);System.out.println(list);// [12, 8, +, 6, *, 10, -]//计算int i1 = toGetRes(list);System.out.println(i1); //110}//例如:  (12+8) * 6 -10//把中缀表达式的字符串存入集合;public static  List<String> infixToList(String infixStr){//定义要返回的集合;List<String> list = new ArrayList<>();//指针;int index = 0 ;//拼接数字使用;StringBuilder strs;//取出的字符;char ch;do{//非数字直接添加;if((ch = infixStr.charAt(index)) < 48 || (ch = infixStr.charAt(index)) > 57 ){list.add(ch+"");index ++;}else {//需要拼接数字;strs = new StringBuilder();while(index < infixStr.length() && (ch = infixStr.charAt(index)) >= 48 && (ch = infixStr.charAt(index)) <= 57 ){strs.append(ch);index ++;}list.add(strs.toString());}}while (index<infixStr.length());return list;}//存放中缀表达式的集合转为存放后缀表达式的集合;public static List<String> infixToSuffixList(List<String> infixList){//定义栈;存放符号;Stack<String> s1 = new Stack<>();//返回的结果集合;List<String> s2 = new ArrayList<>();//取出字符串的字符;for (String s : infixList) {//数字放入即可;if(s.matches("\\d+")){s2.add(s);}else if(s.equals("(")){//左括号,直接放入符号栈;s1.push(s);}//右括号,需要判断;else if(s.equals(")")){//把符号栈的符号放入集合;直到 ( 为止,且消除();while (!s1.peek().equals("(")){s2.add(s1.pop());}//抛出左括号;s1.pop();}else {//运算符比较优先级;  若符号栈的栈顶优先级 大于等于 要放入的符号;while (s1.size()!=0 && getPriority(s1.peek()) >= getPriority(s)){s2.add(s1.pop());}s1.push(s);}}//符号栈元素压入集合;while (s1.size()!=0){s2.add(s1.pop());}//返回即可;return s2;}//符号的优先级;public static int getPriority(String symbol){int result = 0;switch (symbol){case "+" :result = 1;break;case "-":result = 1;break;case "*":result = 2;break;case "/":result =2;break;default:break;}return result;}//传入的集合计算;public static int toGetRes(List<String> list) {//创建一个栈即可;主要存数字;Stack<String> stack = new Stack<>();//把集合中的数取出;for (String s : list) {if (s.matches("\\d+")) {//若取到的是数字,直接入栈;stack.push(s);} else {int result = 0;//栈里出两个数字;注意计算时,第二次弹出的数字在前;int num1 = Integer.parseInt(stack.pop());int num2 = Integer.parseInt(stack.pop());//其他的字符进行匹配;switch (s) {case "+":result = num2 + num1;break;case "-":result = num2 - num1;break;case "*":result = num2 * num1;break;case "/":result = num2 / num1;break;default:throw new RuntimeException("符号错误");}stack.push("" + result);}}return Integer.parseInt(stack.pop());}//之前的后缀 字符串 转为集合;public static List<String> toList(String str) {//空格分隔字符串;String[] s = str.split(" ");//创建集合;准备存入字符串数组;ArrayList<String> arrayList = new ArrayList<>();Collections.addAll(arrayList, s);return arrayList;}
}