一、栈

1. 运用场景

image.png
image.png

2. 代码实现

  1. package com.atguigu.stack;
  3. public class Calculator {
  4.     public static void main(String[] args) {
  5.         // 完成表达式的运算
  6.         String expression = "3+2*6-2";
  7.         // 创建2个栈，数栈和符号栈
  8.         ArrayStack2 numStack = new ArrayStack2(10);
  9.         ArrayStack2 operStack = new ArrayStack2(10);
  10.         // 定义需要的相关变量
  11.         int index = 0;  // 用于扫描
  12.         int num1 = 0;
  13.         int num2 = 0;
  14.         int oper = 0;
  15.         int result = 0;
  16.         String keepNum = null;
  17.         char ch = ' '; //将每次扫描得到的char保存到ch中
  18.         // 开始用while语句扫描expression
  19.         while (true) {
  20.             // 依次得到expression中的每一个字符
  21.             ch = expression.substring(index, index + 1).charAt(0);
  22.             // 判断是数字还是符号
  23.             if (operStack.isOper(ch)) {
  24.                 // 如果是运算符，则需要判断当前的符号栈是否为空
  25.                 if (!operStack.isEmpty()) {
  26.                     // 对符号进行优先级比较
  27.                     if (operStack.priority(ch) <= operStack.priority(operStack.peek())) {
  28.                         num1 = numStack.pop();
  29.                         num2 = numStack.pop();
  30.                         oper = operStack.pop();
  31.                         result = numStack.cal(num1, num2, (char) oper);
  32.                         // 把运算的结果入数栈
  33.                         numStack.push(result);
  34.                         // 把当前的运算符入符号栈
  35.                         operStack.push(ch);
  36.                     } else {
  37.                         // 如果为空则直接入栈
  38.                         operStack.push(ch);
  39.                     }
  40.                 }
  41.             } else {
  42.                 // 如果是数，则直接入数栈
  43.                 // 当是多位数时，不能发现是数就入数栈。需要向expression后再看一位，如果是数就继续扫描，如果是符号就入栈
  44.                 // 因此需要定义一个字符串变量
  45.                 keepNum += ch;
  46.                 if (index == expression.length() - 1) {
  47.                     numStack.push(Integer.parseInt(keepNum));  // 根据ASK码将字符转为数字
  48.                 } else {
  49.                     // 注意：只是往后看一位，不是index++
  50.                     if (!operStack.isOper(expression.substring(index + 1, index + 2).charAt(0))) {
  51.                         numStack.push(Integer.parseInt(keepNum));  // 根据ASK码将字符转为数字
  52.                         // 注意：keepNum需要清空
  53.                         keepNum = "";
  54.                     }
  55.                     // 让index+1并判断是否扫描到expression最后了
  56.                     index++;
  57.                     if (index >= expression.length()) {
  58.                         break;
  59.                     }
  60.                 }
  61.             }
  62.             // 当表达式扫描完毕，就顺序的从数栈和符号栈中pop出相应的数和符号，并运行
  63.             while (true) {
  64.                 // 如果符号栈为空，则计算到了最后，数栈中只有一个数字（即结果）
  65.                 if (operStack.isEmpty()) {
  66.                     break;
  67.                 }
  68.                 num1 = numStack.pop();
  69.                 num2 = numStack.cal(num1, num2, (char) oper);
  70.                 numStack.push(result);
  71.             }
  72.             System.out.printf("表达式%s=%d", expression, numStack.pop());
  73.         }
  74.     }
  76.     // 数字栈
  77.     static class ArrayStack2 {
  78.         // 定义栈的大小
  79.         private int maxSize;
  80.         private int[] stack;  // 数组模拟栈，int类型的元素
  81.         private int top = -1;  //栈底，初始化没有数据
  83.         // 构造器
  84.         public ArrayStack2(int maxSize) {
  85.             this.maxSize = maxSize;
  86.         }
  88.         public boolean inFull() {
  89.             return top == maxSize - 1;
  90.         }
  92.         public boolean isEmpty() {
  93.             return top == -1;
  94.         }
  96.         // 入栈
  97.         public void push(int value) {
  98.             // 先判断栈满没满
  99.             if (inFull()) {
  100.                 System.out.println("栈满！");
  101.                 return;
  102.             }
  103.             top++;
  104.             stack[top] = value;
  105.         }
  107.         // 出栈
  108.         public int pop() {
  109.             // 实质：将栈顶的数据返回
  110.             if (isEmpty()) {
  111.                 // 抛出异常
  112.                 throw new RuntimeException("空栈，没有数据");
  113.             }
  114.             int value = stack[top];
  115.             return value;
  116.         }
  118.         // 遍历栈,从栈顶往下遍历
  119.         public void list() {
  120.             if (isEmpty()) {
  121.                 System.out.println("空栈，没有数据");
  122.                 return;
  123.             }
  124.             for (int i = top; i > 0; i--) {
  125.                 System.out.printf("stack[%d]=%d出栈\n！", i, stack[i]);
  126.             }
  127.         }
  129.         // 返回运算符的优先级，优先级是程序员来定的。优先级使用数字来表示，数值越大，优先级越高
  130.         public int priority(int oper) {
  131.             if (oper == '*' || oper == '/') {
  132.                 return 1;   // 乘法和除法的优先级高
  133.             } else if (oper == '+' || oper == '-') {
  134.                 return 0;   // 加法和减法的优先级底
  135.             } else {
  136.                 return -1;   // 假设当前的计算式中只有加减乘除
  137.             }
  138.         }
  140.         // 判断是不是一个运算符
  141.         public boolean isOper(char val) {
  142.             return val == '*' || val == '/' || val == '+' || val == '-';
  143.         }
  145.         // 计算方法
  146.         public int cal(int num1, int num2, char oper) {
  147.             int res = 0; // res用于存放计算的结果
  148.             switch (oper) {
  149.                 case '+':
  150.                     res = num1 + num2;
  151.                     break;
  152.                 case '-':
  153.                     res = num2 - num1;
  154.                     break;
  155.                 case '*':
  156.                     res = num1 * num2;
  157.                     break;
  158.                 case '/':
  159.                     res = num2 / num1;
  160.                     break;
  161.             }
  162.             return res;
  163.         }
  165.         // 栈满
  166.         public int peek() {
  167.             return stack[top];
  168.         }
  169.     }
  170. }

3. 栈的前缀、中缀和后缀表达式（逆波兰表达式）

3.1 前缀：波兰表达式

3.2 后缀：逆波兰表达式

  1. package com.atguigu.stack;
  3. import java.util.ArrayList;
  4. import java.util.List;
  5. import java.util.Stack;
  7. public class PolandNotationDemo {
  8.     public static void main(String[] args) {
  9.         // 先定义一个逆波兰表达式
  10.         // (3+4)*5-6  ==> 3 4 + 5 * 6 -
  11.         String suffixExpresson = "3 4 + 5 * 6 -";
  13.         List<String> rpnList = getListString(suffixExpresson);
  14.     }
  16.     /**
  17.      * 从最开始的方法--扫描字符串，改为将suffixExpression放入一个ArrayList中
  18.      * step2: 通过配合栈的形式，完成运算
  19.      */
  20.     // 将逆波兰表达式依次放入一个ArrayList中
  21.     public static List<String> getListString(String suffixExpresson) {
  22.         // 将suffixExpressopm进行分割
  23.         String[] splits = suffixExpresson.split(" ");
  24.         List<String> list = new ArrayList<String>();
  25.         for (String item : splits) {
  26.             list.add(item);
  27.         }
  28.         return list;
  29.     }
  31.     // 完成计算
  32.     public static int cal(List<String> ls) {
  33.         // 创建一个栈
  34.         Stack<String> stack = new Stack<String>();
  35.         for (String item : ls) {
  36.             // 使用正则表达式取数
  37.             if (item.matches("\\d+")) {
  38.                 // 匹配的是多位数
  39.                 stack.push(item);
  40.             } else {
  41.                 // pop出2个数并运算，然后入栈
  42.                 int num2 = Integer.parseInt(stack.pop());
  43.                 int num1 = Integer.parseInt(stack.pop());
  44.                 int res = 0;
  45.                 if (item.equals("+")) {
  46.                     res = num1 + num2;
  47.                 } else if (item.equals("-")) {
  48.                     res = num2 - num1;
  49.                 } else if (item.equals("*")) {
  50.                     res = num1 * num2;
  51.                 } else if (item.equals("/")) {
  52.                     res = num2 / num1;
  53.                 } else{
  54.                     throw new RuntimeException("运算符有问题！");
  55.                 }
  56.                 // 把res入栈
  57.                 stack.push(""+res);
  58.             }
  59.         }
  60.         return Integer.parseInt(stack.pop());
  61.     }
  62. }

4. 如何将中缀表达式转为后缀表达式

image.png

// 将中缀表达式转为后缀表达式
    public List<String> parseSuffixExpressionList(List<String> ls){
        // 定义2个栈
        Stack<String> s1= new Stack<String>();  // 符号栈
        // 说明：因为s2 这个栈，在这个转换过程中，没有pop操作，而且后面我们还需要逆序输出，因此比较麻烦
        // 这里我们不用栈的结构，直接使用List
//        Stack<String> s2= new Stack<String>();
        List<String> s2 = new ArrayList<String>();
        // 遍历ls
        for (String item : ls) {
            // 如果是一个数，就加入到s2
            if(item.matches("\\d+")){
                s2.add(item);
            }else if(item.equals("(")){
                s1.push(item);
            }else if(item.equals("(")){
                // 如果是右括号，则依次弹出s1栈顶的运算符，并压入s2，直到遇到左括号为止，此时将这一对括号丢弃
                while(!s1.peek().equals(")")){
                    s2.add(s1.pop());
                }
                s1.pop();  // 消除左括号
            }else{
                // 当item的优先级小于等于s1栈顶运算符，将s1栈顶的运算符弹出并加入到s2中，再次转到（4.1）与s1中新的栈顶运算符进行比较
                // 优先级比较高低的方法
                while(s1.size()!=0 && Operation.getValue(s1.peek()) >= Operation.getValue(item)){
                    s2.add(s1.pop());
                }
                // 还需要将item压入栈
                s1.push(item);
            }
            // 将s1的元素加入到s2中
            while (s1.size()!=0){
                s2.add(s1.pop());
            }
            return s2;  //因为是存放到List，因此按顺序存入就是逆波兰表达式
        }
        return s2;
    }

`比较运算符优先级的类：

// 编写比较运算符高低的类
class Operation{
    // 加减乘除的优先级
    private static int ADD = 1;
    private static int SUB = 1;
    private static int MUL = 2;
    private static int DIV = 2;
    // 写一个方法返回对应优先级的数字
    public static int getValue(String operation){
        int result = 0;
        switch (operation) {
            case "+":
                result=ADD;
                break;
            case "-":
                result=SUB;
                break;
            case "*":
                result=MUL;
                break;
            case "/":
                result=DIV;
                break;
            default:
                System.out.println("不存在该运算符！");
                break;
        }
        return result;
    }
}