一、栈的理解


1. 栈的一个实际需求


QQ截图20200806110500.jpg
如计算一个数学表达式可以使用到栈。
**

2.栈的介绍(文字以及图示)

QQ截图20200806110555.jpg
QQ截图20200806110640.jpg

3. 栈的应用场景

QQ截图20200806110717.jpg

二、数组栈的实现

实现说明

QQ截图20200807111952.jpgQQ截图20200807112000.jpg

实现代码

源代码：**ArrayStackDemo.java**

说明：这里有判断栈已满、判断栈为空、入栈操作、出栈操作、遍历栈的多个方法。
判断栈已满：return top == maxSize-1;
判断栈为空：return top == -1;
入栈操作：判断栈是否满，top++;arrStack[top]=num;
出栈操作：判断栈是否为空，保存现有数据，top位置下移，进行返回
遍历栈：从上到下，top-0 进行遍历

  1. class ArrayStack{
  2.     //设置栈的最大容量
  3.     private int maxSize;
  4.     //创建数组
  5.     private int[] arrStack;
  6.     //栈顶默认为-1
  7.     private int top = -1;
  9.     public ArrayStack(int maxSize) {
  10.         //根据参数来开辟空间
  11.         this.maxSize = maxSize;
  12.         arrStack = new int[maxSize];
  13.     }
  15.     //判断栈是否已满
  16.     public boolean isFull() {
  17.         return top == maxSize-1;
  18.     }
  20.     //判断栈是否为空
  21.     public boolean isEmpty() {
  22.         return top == -1;
  23.     }
  25.     //进行入栈操作
  26.     public void pushStack(int num) {
  27.         //判断栈是否已满
  28.         if(isFull()) {
  29.             System.out.println("栈已满，无法入栈！");
  30.             return;
  31.         }
  32.         //进行入栈操作
  33.         arrStack[++top] = num;
  34.         System.out.println("入栈成功");
  35.     }
  37.     //进行出栈操作
  38.     public int popStack() {
  39.         if(isEmpty()) {
  40.             throw new RuntimeException("栈空，无法出栈！");
  41.         }
  42.         int value = arrStack[top];
  43.         top--;
  44.         return value;
  45.     }
  47.     //进行遍历栈
  48.     public void showStack() {
  49.         //判断栈是否为空
  50.         if(isEmpty()) {
  51.             System.out.println("栈为空无法遍历！");
  52.             return;
  53.         }
  54.         System.out.println("栈从上至下结果：");
  55.         for(int i=top;i>=0;i--) {
  56.             System.out.println(arrStack[i]+" ");
  57.         }
  58.     }
  60. }

测试代码：(已测试，能够实现)

  1. package StackExer;
  3. import java.util.Scanner;
  5. public class ArrayStackDemo {
  6.     public static void main(String[] args) {
  7.         ArrayStack arrayStack = new ArrayStack(3);
  8.         Scanner scanner = new Scanner(System.in);
  9.         //用于接收进行的操作
  10.         String str = new String();
  11.         boolean flag = true;
  13.         while(flag) {
  14.             System.out.println("show :展示栈中数据");
  15.             System.out.println("push :进行入栈操作");
  16.             System.out.println("pop :进行出栈操作");
  17.             System.out.println("exit :退出程序");
  18.             System.out.println();
  19.             System.out.println("请输入你想要进行的操作：");
  20.             str = scanner.next();
  22.             switch (str) {
  23.             case "show"://遍历栈中的数据
  24.                 arrayStack.showStack();
  25.                 break;
  26.             case "push"://进行入栈操作
  27.                 System.out.println("请输入您想要入栈的数字：");
  28.                 int num = scanner.nextInt();
  29.                 arrayStack.pushStack(num);
  30.                 break;
  31.             case "pop"://进行出栈操作
  32.                 try {
  33.                     int value = arrayStack.popStack();
  34.                     System.out.println("出栈的数字为：" + value);
  35.                 } catch (Exception e) {
  36.                     System.out.println(e.getMessage());
  37.                 }
  38.                 break;
  39.             case "exit":
  40.                 flag = false;
  41.                 break;
  42.             }
  44.         }
  45.     }
  47. }

三、链表栈的实现

源代码：ListStackDemo.java

三步骤(创建节点+方法说明+测试)

首先创建栈的节点：

  1. //创建栈中的节点
  2. class Node{
  3.     public int value;
  4.     public Node next;
  6.     public Node(int value) {
  7.         this.value = value;
  8.     }
  10. }

创建栈：使用链表实现
说明：包含了**判断栈是否为空、栈是否满、入栈操作、出栈操作、遍历栈、获取栈顶元素。

判断栈是否为空：return top==-1;
判断栈是否已满：return top == maxSize-1;

入栈操作：
① 判断栈是否已满
② 上移top，判断top是否为1，是的话创建栈底的元素bottomNode并赋值topNode；
不是第一次那么根据top来使用辅助节点进行上移节点到栈顶位置，temp.next = new Node(val),topNode = new Node(value);

出栈操作：
① 判断是否为空
② 使用辅助节点temp以及事先存储号topNode的值。
③ 使用辅助节点找到出栈节点的前一个，为栈顶元素赋值topNode = temp;，接着删除temp的下一个节点，temp.next=null，最后返回value

获取栈顶元素：return topNode.value

遍历操作：
根据top创建一维数组，遍历链表同时给数组赋值，最后根据top从后往前遍历数组输出即可。

  1. //创建管理栈的类
  2. class ListStack{
  3.     //栈底节点
  4.     private Node bottomNode;
  5.     //栈顶节点
  6.     private Node topNode;
  7.     //栈的最大容量
  8.     private int maxSize;
  9.     //指向最高的位置
  10.     private int top = -1;
  12.     //构造器设置栈中的最大容量
  13.     public ListStack(int maxSize) {
  14.         this.maxSize = maxSize;
  15.     }
  17.     //判断栈为空
  18.     public boolean isEmpty() {
  19.         return top == -1;
  20.     }
  22.     //判断栈已满
  23.     public boolean isFull() {
  24.         return top == maxSize-1;
  25.     }
  27.     //进行入栈操作
  28.     public void pushList(int value) {
  29.         //判断栈是否已满
  30.         if(isFull()) {
  31.             System.out.printf("栈已满，无法入栈！\n\n");
  32.             return;
  33.         }
  34.         top++;//首先上移top
  35.         if(top == 0) {
  36.             //创建栈底元素以及设置栈顶元素
  37.             bottomNode = new Node(value);
  38.             topNode = new Node(value);
  39.         }else {
  40.             //其他插入情况
  41.             //使用辅助节点
  42.             Node temp = bottomNode;
  43.             for(int i=1;i<=top-1;i++) {
  44.                 temp = temp.next;//将辅助节点上移到插入元素之前
  45.             }
  46.             //进行入栈操作
  47.             temp.next = new Node(value);
  48.             //栈顶也要进行赋值
  49.             topNode = new Node(value);
  50.         }
  51.         System.out.printf("%d入栈成功!\n\n",value);
  52.     }
  55.     //进行出栈操作
  56.     public int popList() {
  57.         //判断栈中数据是否为空
  58.         if(isEmpty()) {
  59.             throw new RuntimeException("栈中数据为空，无法出栈!");
  60.         }
  61.         //使用辅助节点
  62.         Node temp = bottomNode;
  63.         //变量保存最后栈中元素
  64.         int value = topNode.value;
  65.         //指向栈顶位置-1
  66.         top--;
  67.         //使temp到达出栈的前一个顶点
  68.         for(int i=0;i<=top-1;i++) {
  69.             temp = temp.next;
  70.         }
  71.         //更新栈顶元素
  72.         topNode = temp;
  73.         if(top==-1) {
  74.             //出栈最后一个元素时
  75.             bottomNode = null;
  76.             topNode = null;
  77.         }else {
  78.             temp.next = null;//清除栈顶元素            
  79.         }
  80.         return value;
  81.     }
  83.     //遍历栈
  84.     public void showList() {
  85.         //判断是否为空
  86.         if(isEmpty()) {
  87.             System.out.printf("栈中数据为空，无法遍历!\n\n");
  88.             return;
  89.         }
  90.         //顶一个辅助节点
  91.         Node temp = bottomNode;
  92.         //创建一个数组
  93.         int []arr = new int[top+1];
  94.         for(int i=0;i<=top;i++) {
  95.             arr[i] = temp.value;
  96.             temp = temp.next;
  97.         }
  99.         //进行 反向打印数组的value值
  100.         for(int i=top;i>=0;i--) {
  101.             System.out.printf("a[%d]=%d  ",i,arr[i]);
  102.         }
  103.         System.out.println();
  104.     }
  106.     //查看栈顶元素
  107.     public int getTopNode() {
  108.         //判断是否为空
  109.         if(isEmpty()) {
  110.             throw new RuntimeException("栈中数据为空，无法查看栈顶！");
  111.         }
  112.         return topNode.value;
  113.     }
  115. }

测试代码：(已测试成功)

  1. package StackExer;
  3. import java.util.Scanner;
  5. public class ListStackDemo {
  6.     public static void main(String[] args) {
  7.         ListStack listStack = new ListStack(3);
  8.         Scanner scanner = new Scanner(System.in);
  9.         //用于接收进行的操作
  10.         String str = new String();
  11.         boolean flag = true;
  13.         while(flag) {
  14.             System.out.println("show :展示栈中数据");
  15.             System.out.println("push :进行入栈操作");
  16.             System.out.println("pop :进行出栈操作");
  17.             System.out.println("get :获取栈顶元素");
  18.             System.out.println("exit :退出程序");
  19.             System.out.println();
  20.             System.out.println("请输入你想要进行的操作：");
  21.             str = scanner.next();
  23.             switch (str) {
  24.             case "show"://遍历栈中的数据
  25.                 listStack.showList();
  26.                 break;
  27.             case "push"://进行入栈操作
  28.                 System.out.println("请输入您想要入栈的数字：");
  29.                 int num = scanner.nextInt();
  30.                 listStack.pushList(num);
  31.                 break;
  32.             case "pop"://进行出栈操作
  33.                 try {
  34.                     int value = listStack.popList();
  35.                     System.out.println("出栈的数字为：" + value);
  36.                 } catch (Exception e) {
  37.                     System.out.println(e.getMessage());
  38.                 }
  39.                 break;
  40.             case "exit":
  41.                 flag = false;
  42.                 break;
  43.             case "get":
  44.                 try {
  45.                     int value = listStack.getTopNode();
  46.                     System.out.println("栈顶元素为：" + value);
  47.                 } catch (Exception e) {
  48.                     System.out.println(e.getMessage());
  49.                 }
  50.                 break;
  51.             }
  53.         }
  54.     }
  55. }



**



**

四、栈实现综合计算器(中缀表达式) 实际应用


思路分析(题意+图解)

题意要求
QQ截图20200808152403.jpg

图解分析
QQ截图20200808152412.jpg

① 实现加减乘除(个位数运算+三部分实现)

源代码：Calculator.java

首先是数组栈的实现，增加获取栈顶元素值方法

  1. class ArrayStack2{
  2.     //设置栈的最大容量
  3.     private int maxSize;
  4.     //创建数组
  5.     private int[] arrStack;
  6.     //栈顶默认为-1
  7.     private int top = -1;
  9.     public ArrayStack2(int maxSize) {
  10.         //根据参数来开辟空间
  11.         this.maxSize = maxSize;
  12.         arrStack = new int[maxSize];
  13.     }
  15.     //判断栈是否已满
  16.     public boolean isFull() {
  17.         return top == maxSize-1;
  18.     }
  20.     //判断栈是否为空
  21.     public boolean isEmpty() {
  22.         return top == -1;
  23.     }
  25.     //进行入栈操作
  26.     public void pushStack(int num) {
  27.         //判断栈是否已满
  28.         if(isFull()) {
  29.             System.out.println("栈已满，无法入栈！");
  30.             return;
  31.         }
  32.         //进行入栈操作
  33.         arrStack[++top] = num;
  34.     }
  36.     //进行出栈操作
  37.     public int popStack() {
  38.         if(isEmpty()) {
  39.             throw new RuntimeException("栈空，无法出栈！");
  40.         }
  41.         int value = arrStack[top];
  42.         top--;
  43.         return value;
  44.     }
  46.     //进行遍历栈
  47.     public void showStack() {
  48.         //判断栈是否为空
  49.         if(isEmpty()) {
  50.             System.out.println("栈为空无法遍历！");
  51.             return;
  52.         }
  53.         System.out.println("栈从上至下结果：");
  54.         for(int i=top;i>=0;i--) {
  55.             System.out.println(arrStack[i]+" ");
  56.         }
  57.     }
  59.     //获取栈顶元素
  60.     public int getTopValue() {
  61.         if(isEmpty()) {
  62.             throw new RuntimeException("栈中为空，无法取出");
  63.         }
  64.         return arrStack[top];
  65.     }
  68. }

创建一个工具类为之后调用更加简便

包含三个方法：
① 判断是运算符还是数字，返回true为运算符，false为数字
② 根据传入字符来返回优先等级用1,0表示，1表示* / 0为+-，1优先级更高 0优先级低
③ 传入两个数一个运算符，根据运算符进行运算，返回运算值

  1. class Utils{
  2.     //判断是运算符还是数字
  3.     public static boolean isOper(char ch) {
  4.         return ch=='+' || ch=='*' || ch == '-' || ch=='/';
  5.     }
  7.     //给出优先级等级
  8.     public static int priority(int ch) {
  9.         if(ch == '*' || ch == '/') {
  10.             return 1;
  11.         }else if(ch == '+' || ch=='-') {
  12.             return 0;
  13.         }else {
  14.             throw new RuntimeException("无法检测出优先等级");
  15.         }
  16.     }
  18.     //根据运算符对两个数值进行运算
  19.     public static int operatorNum(int num1,int num2,int oper) {
  20.         int result = 0;
  21.         switch (oper) {
  22.         case '+':
  23.             result =  num1+num2;
  24.             break;
  25.         case '-':
  26.             result =  num1-num2;
  27.             break;
  28.         case '*':
  29.             result =  num1*num2;
  30.             break;
  31.         case '/':
  32.             result =  num1/num2;
  33.             break;
  34.         default:
  35.             break;
  36.         }
  37.         return result;
  38.     }
  39. }

实现计算器

前提准备：
使用两个栈，一个用来存放数字，一个用来存放运算符。
代码实现过程：
整体两个部分。
第一个部分是将对应表达式中数字以及运算符入栈，并且处理掉优先级高的运算符；
第二个部分就是处理剩下来优先级低的运算符，将所有运算符进行处理完，数字栈中最后只剩下一个数字那就是最后的结果。
更多细节部分查看上面的思路分析解决

  1. package StackExer;
  4. public class Calculator {
  5.     public static void main(String[] args) {
  6.         String str = "3*1+2*6-5";
  7.         //对str进行入栈操作，并且入栈过程中将对应之前优先级高的进行处理
  8.         int index = 0;//对应str的下标
  9.         char ch = ' ';//用于取对应下标的字符
  10.         //取出的两个数字
  11.         int num1 = 0;
  12.         int num2 = 0;
  13.         int oper = 0;//栈中取出的运算符
  14.         int result = 0;//算运算之和
  16.         //创建两个栈，一个数字栈、一个存放运算符栈
  17.         ArrayStack2 numStack = new ArrayStack2(10);
  18.         ArrayStack2 charStack = new ArrayStack2(10);
  20.         while(index<str.length()) {
  21.             ch = str.charAt(index);
  22.             //1.判断是数字还是运算符
  23.             if(Utils.isOper(ch)) {
  24.                 //是运算符时
  25.                 //2.判断字符栈中是否为空
  26.                 if(charStack.isEmpty()) {
  27.                     //直接入栈
  28.                     charStack.pushStack(ch);
  29.                 }else {
  30.                     //字符栈中不为空,进行判断优先级
  31.                     //3.待插入运算符与已插入的运算符进行优先级比较
  32.                     if(Utils.priority(ch)<=Utils.priority(charStack.getTopValue())) {
  33.                         //取出字符栈中的运算符
  34.                         oper = charStack.popStack();
  35.                         //注意num值取出的顺序
  36.                         num2 = numStack.popStack();
  37.                         num1 = numStack.popStack();
  38.                         result = Utils.operatorNum(num1, num2, oper);
  39.                         //将求出结果的值入栈
  40.                         numStack.pushStack(result);
  41.                         //将优先级低的入栈
  42.                         charStack.pushStack(ch);
  43.                     }else {
  44.                         //直接将运算符入栈
  45.                         charStack.pushStack(ch);
  46.                     }
  48.                 }
  49.             }else {
  50.                 //不是运算符
  51.                 numStack.pushStack(ch-'0');
  52.             }
  54.             index++;//向后移一位
  55.         }
  57.         //处理剩余优先级相同的
  58.         while(true) {
  59.             //当字符栈为空时，说明已经结束求值了
  60.             if(charStack.isEmpty()) {
  61.                 break;
  62.             }
  63.             //取出字符栈中的运算符
  64.             oper = charStack.popStack();
  65.             //注意num值取出的顺序
  66.             num2 = numStack.popStack();
  67.             num1 = numStack.popStack();
  68.             result = Utils.operatorNum(num1, num2, oper);
  69.             numStack.pushStack(result);
  70.         }
  72.         result = numStack.popStack();
  73.         System.out.println("表达式结果为："+result);
  75.     }
  77. }

② 解决①中只能计算个位数的加减乘除(可以多位数)

源代码：Calculator.java

修改过程

说明：修改位置是判断读取是数字时的操作，可以对数字进行拼接。
QQ截图20200809111120.jpg

  1. package StackExer;
  4. public class Calculator {
  5.     public static void main(String[] args) {
  6.         String str = "3*1+2*600-500";
  7.         //对str进行入栈操作，并且入栈过程中将对应之前优先级高的进行处理
  8.         int index = 0;//对应str的下标
  9.         char ch = ' ';//用于取对应下标的字符
  10.         //取出的两个数字
  11.         int num1 = 0;
  12.         int num2 = 0;
  13.         int oper = 0;//栈中取出的运算符
  14.         int result = 0;//算运算之和
  15.         String keepNum = "";
  17.         //创建两个栈，一个数字栈、一个存放运算符栈
  18.         ArrayStack2 numStack = new ArrayStack2(10);
  19.         ArrayStack2 charStack = new ArrayStack2(10);
  21.         while(index<str.length()) {
  22.             ch = str.charAt(index);
  23.             //1.判断是数字还是运算符
  24.             if(Utils.isOper(ch)) {
  25.                 //是运算符时
  26.                 //2.判断字符栈中是否为空
  27.                 if(charStack.isEmpty()) {
  28.                     //直接入栈
  29.                     charStack.pushStack(ch);
  30.                 }else {
  31.                     //字符栈中不为空,进行判断优先级
  32.                     //3.待插入运算符与已插入的运算符进行优先级比较
  33.                     if(Utils.priority(ch)<=Utils.priority(charStack.getTopValue())) {
  34.                         //取出字符栈中的运算符
  35.                         oper = charStack.popStack();
  36.                         //注意num值取出的顺序
  37.                         num2 = numStack.popStack();
  38.                         num1 = numStack.popStack();
  39.                         result = Utils.operatorNum(num1, num2, oper);
  40.                         //将求出结果的值入栈
  41.                         numStack.pushStack(result);
  42.                         //将优先级低的入栈
  43.                         charStack.pushStack(ch);
  44.                     }else {
  45.                         //直接将运算符入栈
  46.                         charStack.pushStack(ch);
  47.                     }
  49.                 }
  50.             }else {
  51.                 //是数字
  52.                 //需要考虑多位数情况
  53.                 //判断是否为最后一位
  54.                 if(index == str.length()-1) {
  55.                     //直接入栈即可
  56.                     numStack.pushStack(ch-'0');
  57.                 }else {
  58.                     //判断下一个是否是运算符
  59.                     if(Utils.isOper(str.charAt(index+1))) {
  60.                         //是的话直接入栈
  61.                         numStack.pushStack(ch-'0');//直接入栈
  62.                     }else {
  63. //                        //不是进行拼接
  64. //                        keepNum = String.valueOf(ch);
  65. //                        index++;
  66. //                        keepNum += str.charAt(index);
  67. //                        //这里进行入栈
  68. //                        numStack.pushStack(Integer.valueOf(keepNum));
  69.                         //首先接收这个数字
  70.                         keepNum = String.valueOf(ch);
  71.                         //进行循环判断拼接数字(下一个不越界同时下一个是数字的情况执行)
  72.                         while((index+1 <= str.length()-1)&&!Utils.isOper(str.charAt(index+1))) {
  73.                             keepNum += str.charAt(index+1);
  74.                             index++;
  75.                         }
  76.                         //将组成的数字入栈
  77.                         numStack.pushStack(Integer.valueOf(keepNum));
  78.                     }
  79.                 }
  81.             }
  82.             keepNum = "";//将keepNum进行清空
  83.             if(index == str.length()-1) {
  84.                 break;
  85.             }
  87.             index++;//向后移一位
  88.         }
  90.         //处理剩余优先级相同的
  91.         while(true) {
  92.             //当字符栈为空时，说明已经结束求值了
  93.             if(charStack.isEmpty()) {
  94.                 break;
  95.             }
  96.             //取出字符栈中的运算符
  97.             oper = charStack.popStack();
  98.             //注意num值取出的顺序
  99.             num2 = numStack.popStack();
  100.             num1 = numStack.popStack();
  101.             result = Utils.operatorNum(num1, num2, oper);
  102.             numStack.pushStack(result);
  103.         }
  105.         result = numStack.popStack();
  106.         System.out.println("表达式结果为："+result);
  108.     }
  110. }

运行结果：**计算成功**
QQ截图20200809111240.jpg

五、前缀、中缀、后缀表达式(逆波兰表达式) 概述

① 前缀表达式介绍

QQ截图20200809122259.jpg

  • 计算流程

QQ截图20200809122342.jpg

② 中缀表达式介绍

QQ截图20200809122532.jpg

③ 后缀表达式介绍

QQ截图20200809122602.jpg

  • 求值过程

QQ截图20200809122609.jpg

六 、逆波兰计算器分析与实现

总体源代码：ReversedPolish.java
测试代码：ConfixTest.java
**

① 分析说明(中缀表达式转后缀表达式)

例子说明：
QQ截图20200811102532.jpg
需要通过两个栈进行处理，但为了方便用于存储后缀表达式的栈使用list集合来进行处理
① s1作为栈用来存储运算符或()符号。
② s2由于存储后缀表达式进行出栈取出之后还要进行反转才能获得，所以我们使用list集合来替代。

需要两个方法：
方法一：将String字符串表达式转化为List集合。
方法二：将中缀表达式(list集合)转化为后缀表达式

方法二详细步骤：
首先遍历list获取String字符串item
① 如果item是数字，那么直接保存到s2(list)中。
② 如果item是(，直接保存到s1(栈)中。
③ 如果item是)，那么不断出栈存放到s2(list)中，直到栈中的(前，最后将( 符号出栈。
④ 如果item是运算符的话，那么循环比较栈顶以及item的优先级，条件：栈中有内容以及栈中优先级比item优先级大的话，进行出栈放入s2(list)中，最后item放入到s2(list)中；如果item优先级比栈顶大的话直接将item放入s2(list)中。
⑤ 最后遍历完list之后，将栈中的运算符依次出栈到s2(list)集合中保存

代码实现

  1. package StackExer;
  3. import java.util.ArrayList;
  4. import java.util.List;
  5. import java.util.Stack;
  7. //逆波兰表达式计算器
  8. public class ReversedPolish {
  9.     //中缀表达式转为后缀表达式的两个方法
  10.     //① 中缀表达式(String字符串)转为list形式存储数字以及其他运算符
  11.     public static List<String> toInfixExpressionList(String str) {
  12.         //当不符合表达式时返回null值的list
  13.         if(str == null || str == "" || str.length()==0) {
  14.             return new ArrayList<>();
  15.         }
  16.         //创建一个list
  17.         List<String> list = new ArrayList<>();
  19.         int index = 0;
  20.         char ch = 0;
  21.         String s = "";
  22.         do {
  23.             ch = str.charAt(index);
  24.             //判断为数字还是其他符号
  25.             if(ch<48 || ch >57) {
  26.                 //是其他符号
  27.                 list.add(""+ch);
  28.                 index++;
  29.             }else {
  30.                 s="";
  31.                 //首先进行拼接 有个位数或多位数的情况
  32.                 while(index<str.length() && str.charAt(index)>=48 && str.charAt(index)<=57) {
  33.                     s += str.charAt(index);
  34.                     index++;
  35.                 }
  36.                 list.add(s);
  37.             }
  38.         }while(index<str.length());
  41.         return list;
  42.     }
  44.     //② 将中缀表达式(list存储)转为后缀表达式
  45.     public static List<String> infixToSuffixExpression(List<String> list){
  46.         //创建一个栈、一个list集合   栈用来存放运算符   集合的话用于存放后缀表达式
  47.         Stack<String> stack = new Stack<>();
  48.         List<String> SuffixList = new ArrayList<>();
  50.         for(String item:list) {
  51.             //如果是数字直接添加入集合
  52.             if(item.matches("\\d+")) {
  53.                 SuffixList.add(item);
  54.             }else if(item.equals("(")) {
  55.                 //如果是(，那么直接入栈
  56.                 stack.push(item);
  57.             }else if(item.equals(")")) {
  58.                 //将栈中的运算符进行出栈直到(前都添加到list中
  59.                 while(!stack.peek().equals("(")) {
  60.                     SuffixList.add(stack.pop());
  61.                 }
  62.                 //将栈中(出栈
  63.                 stack.pop();
  64.             }else {
  65.                 //剩下来的是优先级的问题
  66.                 //若是item比栈中的优先级小时出栈并添加到集合中
  67.                 while(stack.size()!=0&&Operation.getValue(stack.peek())>=Operation.getValue(item)) {
  68.                     //若栈中有(则不比较直接跳出while
  69.                     if(Operation.getValue(stack.peek()) == 0) {
  70.                         break;
  71.                     }
  72.                     //将栈中优先级比item大的出栈到list集合中
  73.                     SuffixList.add(stack.pop());
  74.                 }
  75.                 //将item放入list集合中
  76.                 stack.push(item);
  77.             }
  78.         }
  80.         //最后还要将栈中的剩余的添加到list中
  81.         while(stack.size()!=0) {
  82.             SuffixList.add(stack.pop());
  83.         }
  85.         return SuffixList;
  86.     }
  88. }
  90. class Operation{
  91.     private static int ADD = 1;
  92.     private static int SUB = 1;
  93.     private static int MUL = 2;
  94.     private static int DIV = 2;
  96.     public static int getValue(String oper) {
  97.         int result = 0;
  98.         switch (oper) {
  99.         case "+":
  100.             result =  ADD;
  101.             break;
  102.         case "-":
  103.             result =  SUB;
  104.             break;
  105.         case "*":
  106.             result =  MUL;
  107.             break;
  108.         case "/":
  109.             result =  DIV;
  110.             break;
  111.         default:
  112.             break;
  113.         }
  114.         return result;
  115.     }
  116. }

② 分析说明(后缀表达式求值)

源代码：ReversedPolish.java

QQ截图20200810145315.jpg
将中缀表达式转为后缀表达式：
(5+3)6+20 => 53+620+
(4+5)/3(3+2) => 45+3/32+

计算思路：
对后缀表达式从左到右进行扫描，遇到数字进行入栈操作，遇到运算符即出栈两次，后出栈数字 对先出栈数字进行运算再将结果入栈，重复操作指导扫描完整个表达式即可，最终栈中只会存在一个那就是结果。

代码实现

需要两个方法：一个是将已编号的后缀表达式转为list集合方式存储；另一个则是进行计算。
这里只需要一个栈即可只用来存放对应数字，根据运算符进行出栈运算即可。

  1. package StackExer;
  3. import java.util.ArrayList;
  4. import java.util.List;
  5. import java.util.Stack;
  7. //逆波兰表达式计算器
  8. public class ReversedPolish {
  9.     public static void main(String[] args) {
  10.         // 首先写一个逆波兰表达式 (5+3)*12-20  => 76
  11.         String str = "5 3 + 12 * 20 -";
  12.         // 将String中的各个数转为List集合
  13.         List<String> list = parseSuffixExpreesionList(str);
  14.         System.out.println(list);
  15.         int result = calcuate(list);
  16.         System.out.println("最后运算结果为：" + result);
  17.     }
  19.     //后缀表达式相关的两个方法    
  20.     //① 将普通String类型转化为List类型
  21.     public static List<String> parseSuffixExpreesionList(String str) {
  22.         String[] strings = str.split(" ");
  23.         //创建一个集合
  24.         List<String> list = new ArrayList<>();
  25.         for(String s:strings) {
  26.             list.add(s);
  27.         }
  28.         return list;
  29.     }
  31.     //② 根据传入的list中进行计算
  32.     public static int calcuate(List<String> list) {
  33.         //创建一个栈
  34.         Stack<String> stack = new Stack<>();
  35.         int num1 = 0;
  36.         int num2 = 0;
  37.         int result = 0;
  38.         //进行遍历
  39.         for(String str:list) {
  40.             if(str.matches("\\d+")) {
  41.                 //匹配1获取多位数字,直接入栈
  42.                 stack.push(str);
  43.             }else {
  44.                 //从栈中取出两个数
  45.                 num2 = Integer.valueOf(stack.pop());
  46.                 num1 = Integer.valueOf(stack.pop());
  47.                 //获取到运算符 分别进行加减乘除
  48.                 if(str.equals("+")) {
  49.                     result = num1+num2;
  50.                 }else if(str.equals("-")) {
  51.                     result = num1-num2;
  52.                 }else if(str.equals("*")) {
  53.                     result = num1*num2;
  54.                 }else if(str.equals("/")) {
  55.                     result = num1/num2;
  56.                 }else {
  57.                     throw new RuntimeException("无法获取运算符进行运算！");
  58.                 }
  59.                 //还要将计算结果入栈
  60.                 stack.push(String.valueOf(result));
  61.             }
  62.         }
  63.         //最后存在栈中的则是最后运算符结果
  64.         return Integer.valueOf(stack.pop());
  65.     }
  66. }

运行结果：
QQ截图20200810145930.jpg

总体测试(中缀->后缀->求解)

  1. package com.mjj.test;
  3. import java.util.List;
  5. import org.junit.Test;
  7. import StackExer.ReversedPolish;
  9. public class ConfixTest {
  10.     @Test
  11.     public void test() {
  12.         String str = "1+((2+3)*40)-5";
  13.         List<String> list = ReversedPolish.toInfixExpressionList(str);
  14.         System.out.println("中缀表达式(list)："+list);//[1, +, (, (, 2, +, 3, ), *, 4, ), -, 5]
  16.         List<String> infixToSuffixExpression = ReversedPolish.infixToSuffixExpression(list);
  17.         System.out.println("后缀表达式(list)："+infixToSuffixExpression);//[1,2,3,+,4,*,+,5,–]
  18.         //[1, +, 2, +, 3, *, 4, -, 5]
  20.         //通过后缀表达式来求得结果
  21.         int result = ReversedPolish.calcuate(infixToSuffixExpression);
  22.         System.out.println("Expression = "+result);
  23.     }
  24. }

运行结果：
QQ截图20200811143029.jpg

七、逆波兰计算器完整版(参考)

功能说明

QQ截图20200811144128.jpg

源代码

ReversePolishMultiCalc.java

整理者：长路 时间：2020/8/6-2020/8/11