新星计划Day8【数据结构与算法】 栈Part2

👩‍💻博客主页：京与旧铺的博客主页

✨欢迎关注🖱点赞🎀收藏⭐留言✒

🔮本文由京与旧铺原创，csdn首发！

😘系列专栏：java学习

👕参考网课：尚硅谷

💻首发时间：🎞2022年5月2日🎠

🎨你做三四月的事，八九月就会有答案，一起加油吧

🀄如果觉得博主的文章还不错的话，请三连支持一下博主哦

🎧最后的话，作者是一个新人，在很多方面还做的不好，欢迎大佬指正，一起学习哦，冲冲冲

图片

🛒导航小助手🎪

👢036 前缀 中缀 后缀表达式规则

前缀表达式（波兰表达式）

• 前缀表达式又称波兰式，前缀表达式的运算符位于操作数之前

• 举例说明：(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 + 5 × 6 –

后缀表达式的计算机求值

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

例如: (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，由此得出最终结果

🎎037 逆波兰计算器分析和实现（1）

• 输入一个逆波兰表达式(后缀表达式)，使用栈(Stack), 计算其结果

• 支持小括号和多位数整数，因为这里我们主要讲的是数据结构，因此计算器进行简化，只支持对整数的计算。

• 思路分析

• 代码完成

 import java.util.ArrayList;
 import java.util.List;
 import java.util.Stack;
 ​
 /**
  * @author wuyou
  */
 public class PolandNotation {
     public static void main(String[] args) {
         // 定义一个逆波兰表达式
         // (3+4)*5-6 => 3 4 + 5 * 6 -
         String suffixExpression = "3 4 + 5 * 6 -";
         // 先将3 4 + 5 * 6 - 放入一个链表，配合栈完成计算
         List<String> listString = getListString(suffixExpression);
         System.out.println(calculate(listString));
     }
 ​
     /**
      * 将逆波兰表达式的数据和运算符依次放到ArrayList中
      * @param suffixExpression 逆波兰表达式
      * @return 链表
      */
     public static List<String> getListString(String suffixExpression) {
         // 将suffixExpression分割
         String[] split = suffixExpression.split(" ");
         List<String> list = new ArrayList<>();
         for (String element : split) {
             list.add(element);
         }
         return list;
     }
 ​
     /**
      * 计算逆波兰表达式最终结果
      * @param stringList 数据和运算符链表
      * @return 计算结果
      */
     public static int calculate(List<String> stringList) {
         // 创建一个栈即可
         Stack<String> stack = new Stack<>();
         // 遍历链表
         for (String element : stringList){
             // 使用正则表达式来取出数，匹配多位数
             if (element.matches("\\d+")) {
                 // 入栈
                 stack.push(element);
             } else {
                 // pop出两个数，并进行运算再入栈
                 int num2 = Integer.parseInt(stack.pop());
                 int num1 = Integer.parseInt(stack.pop());
                 int res = 0;
                 if (element.equals("+")) {
                     res = num1 + num2;
                 } else if (element.equals("-")) {
                     res = num1 - num2;
                 } else if (element.equals("*")) {
                     res = num1 * num2;
                 } else if (element.equals("/")) {
                     res = num1 / num2;
                 } else {
                     throw new RuntimeException("运算符有误");
                 }
                 // 把res 入栈
                 stack.push(res + "");
             }
         }
         return Integer.valueOf(stack.pop());
     }
 }
 ​

🧣039 中缀转后缀表达式思路分析

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

具体步骤如下:

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

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

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

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

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

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

  • 否则，将s1栈顶的运算符弹出并压入到s2中，再次与s1中新的栈顶运算符相比

• 遇到括号时：

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

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

• ........

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

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

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

🎃040 中缀转后缀表达式代码实现

 /**
  * @author wuyou
  */
 public class Calculator {
     public static void main(String[] args) {
         // 测试运算
         String expression1 = "33+2+2*6-2";
         String expression2 = "7*22*2-5+1-5+3-4";
         String expression3 = "4/2*3-4*2-3-99";
         String expression4 = "1*1*1*3*2/3";
         String expression5 = "11*1*1*3*2/3";
         String expression6 = "1000*23";
 ​
         // 创建两个栈：数栈、符号栈
         ListStack1 numStack = new ListStack1(10);
         ListStack1 operationStack = new ListStack1(10);
 ​
         test(expression1, numStack, operationStack);
         test(expression2, numStack, operationStack);
         test(expression3, numStack, operationStack);
         test(expression4, numStack, operationStack);
         test(expression5, numStack, operationStack);
         test(expression6, numStack, operationStack);
     }
 ​
     /**
      * 测试方法，测试表达式的结果，并且打印结果
      * @param expression 表达式
      * @param numStack 数字栈
      * @param operationStack 符号栈
      */
     public static void test(String expression, ListStack1 numStack, ListStack1 operationStack) {
         // 用于扫描
         int index = 0;
         // 将每次扫描得到的char保存到ch
         char ch = ' ';
 ​
         // 开始while循环的扫描expression
         while (true) {
             // 依次得到expression的每一个字符
             ch = getCharByIndex(expression, index);
             // 判断ch是什么，然后做相应的处理
             if (isOperation(ch)) {
                 // 运用管道过滤器风格，处理运算符
                 operationSolve1(ch, numStack, operationStack);
             } else {
                 // 数直接入数栈，对值为ASCII值-48
                 // 当处理多位数时候，不能立即入栈，可能是多位数，调用过滤器处理多位数
                 index = numSolve1(expression, index, numStack);
             }
             // 让index+1，并判断是否扫描到expression最后
             index++;
             if (index >=  expression.length()) {
                 break;
             }
         }
         // 最后只剩下两个数和一个运算符
         int res = cal((int) numStack.pop(), (int) numStack.pop(), (char) operationStack.pop());
         System.out.printf("表达式: %s = %d\n", expression, res);
     }
 ​
     /**
      * 获取表达式的下标位置为index的字符
      * @param expression 表达式
      * @param index 下标
      * @return
      */
     public static char getCharByIndex(String expression, int index) {
         return expression.charAt(index);
     }
 ​
     /**
      * 处理数字入栈的情况，包含处理多位数的情况，并且返回到操作表达式当前的下标
      * @param expression 表达式
      * @param index 下标
      * @param numStack 数字栈
      * @return 新的下标
      */
     public static int numSolve1(String expression, Integer index, ListStack1 numStack) {
         int end = index + 1;
         for (; end < expression.length(); end++) {
             char ch = getCharByIndex(expression, end);
             // 判断是不是数字
             if (!isOperation(ch)) {
                 continue;
             } else {
                 break;
             }
         }
         String numStr = expression.substring(index, end);
         // 数据入栈
         numStack.push(Integer.valueOf(numStr));
         // 因为test函数进行了+1，所以这里进行-1，避免给重复添加
         return end - 1;
     }
 ​
     /**
      * 符号过滤器1，判断当前是否具有字符
      * @param ch 运算符
      * @param numStack 数字栈
      * @param operationStack 运算符栈
      */
     public static void operationSolve1(char ch, ListStack1 numStack, ListStack1 operationStack) {
         // 判断当前符号栈是否具有操作符
         if (!operationStack.isEmpty()) {
             operationSolve2(ch, numStack, operationStack);
             return;
         } else {
             operationStack.push(ch);
             return;
         }
     }
 ​
     /**
      * 符号过滤器2，处理字符优先级，递归调用过滤器1
      * @param ch 运算符
      * @param numStack 数字栈
      * @param operationStack 运算符栈
      */
     public static void operationSolve2(char ch, ListStack1 numStack, ListStack1 operationStack) {
         // 比较优先级
         if (priority(ch) <= priority((Character) operationStack.peek())) {
             // 调用过滤器3进行计算
             operationSolve3(numStack,operationStack);
             // 递归调用过滤器1，不能递归调用过滤器2，因为可能存在当前运算符栈为空的情况
             operationSolve1(ch, numStack, operationStack);
             return;
         } else {
             // 直接将运算符加入到运算符栈中
             operationStack.push(ch);
             return;
         }
     }
 ​
     /**
      * 符号过滤器3，进行运算
      * @param numStack 数字栈
      * @param operationStack 运算符栈
      */
     public static void operationSolve3(ListStack1 numStack, ListStack1 operationStack) {
         // 定义相关变量
         int num1 = (int) numStack.pop();
         int num2 = (int) numStack.pop();
         char operation = (char) operationStack.pop();
         int res = cal(num1, num2, operation);
         // 把运算结果加到数栈
         numStack.push(res);
         return;
     }
 ​
     /**
      * 返回运算符的优先级，数字越大，运算符越高
      * @param operation 运算符
      * @return
      */
     public static int priority(char operation) {
         if (operation == '*' || operation == '/') {
             return 1;
         } else if (operation == '+' || operation == '-') {
             return 0;
         } else {
             // 假设目前的表达式只有 + - * /
             return -1;
         }
     }
 ​
     /**
      * 判断是不是运算符
      * @param val 字符
      * @return 是不是运算符
      */
     public static boolean isOperation(char val) {
         return val == '+' || val == '-' || val =='*' || val == '/';
     }
 ​
     /**
      * 计算结果
      * @param num1 操作数1，先出栈的数
      * @param num2 操作数2，后出栈的数
      * @param operation 操作符
      * @return 计算结果
      */
     public static int cal(int num1, int num2, char operation) {
         // 用于存放运算的结果
         int res = 0;
         switch (operation) {
             case '+':
                 res = num1 + num2;
                 break;
             case '-':
                 // num1是先弹出来的数，为被减数
                 res = num2 - num1;
                 break;
             case '*':
                 res = num1 * num2;
                 break;
             case '/':
                 // num1是先弹出来的数，为被除数
                 res = num2 / num1;
             default:
                 break;
         }
         return res;
     }
 }
 ​
 /**
  * 表示链表的一个节点
  */
 class Node1{
     Object element;
     Node1 next;
 ​
     public Node1(Object element) {
         this(element, null);
     }
 ​
     /**
      * 头插法插入节点
      * @param element 新增节点的value
      * @param n 原来的头节点
      */
     public Node1(Object element, Node1 n) {
         this.element = element;
         next = n;
     }
 ​
     public Object getElement() {
         return element;
     }
 ​
     public void setElement(Object element) {
         this.element = element;
     }
 ​
     public Node1 getNext() {
         return next;
     }
 ​
     public void setNext(Node1 next) {
         this.next = next;
     }
 }
 ​
 /**
  * 用链表实现堆栈
  */
 class ListStack1 {
     /**
      * 栈顶元素
      */
     Node1 header;
     /**
      * 栈内元素个数
      */
     int elementCount;
     /**
      * 栈的大小
      */
     int size;
 ​
     /**
      * 构造函数，构造一个空的堆栈
      */
     public ListStack1() {
         header = null;
         elementCount = 0;
         size = 0;
     }
 ​
     /**
      * 通过构造器 自定义栈的大小
      * @param size 栈的大小
      */
     public ListStack1(int size) {
         header = null;
         elementCount = 0;
         this.size = size;
     }
 ​
     /**
      * 设置堆栈大小
      * @param size 堆栈大小
      */
     public void setSize(int size) {
         this.size = size;
     }
 ​
     /**
      * 设置栈顶元素
      * @param header 栈顶元素
      */
     public void setHeader(Node1 header) {
         this.header = header;
     }
 ​
     /**
      * 获取堆栈长度
      * @return 堆栈长度
      */
     public int getSize() {
         return size;
     }
 ​
     /**
      * 返回栈中元素的个数
      * @return 栈中元素的个数
      */
     public int getElementCount() {
         return elementCount;
     }
 ​
     /**
      * 判断栈是否为空
      * @return 如果栈是空的，返回真，否则，返回假
      */
     public boolean isEmpty() {
         if (elementCount == 0) {
             return true;
         }
         return false;
     }
 ​
     /**
      * 判断栈满
      * @return 如果栈是满的，返回真，否则，返回假
      */
     public boolean isFull() {
         if (elementCount == size) {
             return true;
         }
         return false;
     }
 ​
     /**
      * 把对象入栈
      * @param value 对象
      */
     public void push(Object value) {
         if (this.isFull()) {
             throw new RuntimeException("Stack is Full");
         }
         header = new Node1(value, header);
         elementCount++;
     }
 ​
     /**
      * 出栈，并返回被出栈的元素
      * @return 被出栈的元素
      */
     public Object pop() {
         if (this.isEmpty()) {
             throw new RuntimeException("Stack is empty");
         }
         Object obj = header.getElement();
         header = header.getNext();
         elementCount--;
         return obj;
     }
 ​
     /**
      * 返回栈顶元素
      * @return 栈顶元素
      */
     public Object peek() {
         if (this.isEmpty()) {
             throw new RuntimeException("Stack is empty");
         }
         return header.getElement();
     }
 }
 ​

🏅042 完整版逆波兰计算器

完整版的逆波兰计算器，功能包括如下：

• 支持 + - * / ( )

• 多位数，支持小数

• 兼容处理, 过滤任何空白字符，包括空格、制表符、换页符

 package com.atguigu.reversepolishcal;
 ​
 import java.util.ArrayList;
 import java.util.Collections;
 import java.util.List;
 import java.util.Stack;
 import java.util.regex.Pattern;
 ​
 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();
         }
     }
 ​
 }
 ​

下期预告：力扣每日一练之二维数组上篇Day4

觉得文章写的不错的亲亲们，点赞评论走一波，爱你们哦！🥗