数据结构之栈

出栈(pop)和入栈(push)

应用场景

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

  使用栈实现计算器（中缀表达式）

  package com.xiaolu.stack;
  /**
   * @author 林小鹿
   * @version 1.0
   * 使用栈编写计算器
   */
  public class Calculator {
      public static void main(String[] args) {
          String expression = "70+2*6-4";
          // 创建两个栈，数栈和符号栈
          ArrayStack numStack = new ArrayStack(10);
          ArrayStack operStack = new ArrayStack(10);
          // 定义需要的相关变量
          int index = 0; // 用于扫描的索引
          int num1 = 0;
          int num2 = 0;
          int oper = 0;
          int res = 0;
          char ch = ' '; // 将每次扫描得到char保存到ch
          String keepNum = ""; // 用于拼接多位数
          // 开始循环扫描expression 依次得到每一个字符
          while (true) {
              ch = expression.substring(index, index+1).charAt(0);
              // 判断ch是什么，然后做相应的处理
              if (operStack.isOper(ch)) {// 如果是运算符
                  if (!operStack.isEmpty()) {
                      //如果符号栈有操作符，就进行比较，如果当前的操作符的优先级小于或者等于栈中的操作符，就需要从数栈中pop出两个数，
                      //在从符号栈中pop出一个符号，进行运算，将得到结果，入数栈，然后将当前的操作符入符号栈
                      if (operStack.priority(ch) 
                          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);
                  }
              } else { //  如果是数，直接入数栈
  //                numStack.push(ch - 48); // 字符 '1' == 数字 1 【只能处理个位数】
                  // 当处理数字时，不能发现是一个数就立即入栈，因为它可能是多位数
                  // 在处理数字是=时，需要向expression 的表达式的index 后再看一位，如果是数就继续扫描，如果是符号才入栈
                  // 处理多位数
                  keepNum += ch;
                  // 如果ch已经是expression的最后一位，直接入栈
                  if (index == expression.length() - 1) {
                      numStack.push(Integer.parseInt(keepNum));
                  } else {
                      // 判断下一个字符是不是数字，如果是数字就继续扫描，如果是运算符，则入栈
                      if (operStack.isOper(expression.substring(index + 1, index + 2).charAt(0))) {
                          // 如果最后一位是运算符，则入栈 此时的 keepNum = "1" 或 "123"
                          numStack.push(Integer.parseInt(keepNum));
                          // 清空 keepNum
                          keepNum = "";
                      }
                  }
              }
              // 让index自增并判断是否扫描到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 出就是结果
          System.out.printf("表达式%s = %d", expression, numStack.pop());
      }
  }
  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;
      }
      // 入栈
      public void push(int value) {
          if (isFull()) {
              System.out.println("栈满");
              return;
          }
          top++;
          stack[top] = value;
      }
      // 出栈
      public int pop() {
          if (isEmpty()) {
              throw new RuntimeException("栈空，没有数据");
          }
          int value = stack[top];
          top--;
          return value;
      }
      // 显示栈的情况[遍历栈]，遍历时，需要从栈顶开始显示数据
      public void list() {
          if (isEmpty()) {
              System.out.println("栈空，没有数据");
          }
          // 需要从栈顶开始显示数据
          for (int i = top; i >= 0; i--) {
              System.out.printf("stack[%d]=%d\n", i, stack[i]);
          }
      }
      // 返回栈顶的值，但不是真正的pop
      public int peek() {
          return stack[top];
      }
      // 返回运算符的优先级，优先级是程序员来确定，优先级使用数字表示
      // 数字越大，优先级越高
      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; // 用于存放计算的结果
          switch (oper) {
              case '+':
                  res = num2 + num1;
                  break;
              case '-':
                  res = num2 - num1;
                  break;
              case '*':
                  res = num2 * num1;
                  break;
              case '/':
                  res = num2 / num1;
                  break;
          }
          return res;
      }
  }
  

  前缀表达式

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

  举例说明：(3+4)×5-6对应的前缀表达式就是 - X + 3 4 5 6

  前缀表达式的计算机求值

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

  例如：(3+4)×5-6对应的前缀表达式就是 - X + 3 4 5 6，针对前缀表达式求值步骤如下：

  1)从右至左扫描，将6、5、4、3压入堆栈

  2)遇到+运算符，因此弹出3和4(3为栈顶元素，4为次顶元素)，计算出3+4的值，得7，再将7入栈

  3)接下来是 X 运算符，因此弹出7和5，计算出7X5=35，将35入栈

  4)最后是 - 运算符，计算出35 - 6的值，即29，由此得出最终结果

  中缀表达式

  中缀表达式就是常见的运算表达式，如(3+4)×5-6

  中缀表达式的求值是我们人最熟悉的，但是对计算机来说却不好操作，因此，在计算结果时，往往会将中缀表达式转成其它表达式来操作(一般转成后缀表达式.)

  后缀表达式

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

    后缀表达式的计算机求值

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

    例如：(3+4)×5-6对应的后缀表达式就是3 4 + 5 × 6 -，针对后缀表达式求值步骤如下：

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

    代码

    package com.xiaolu.stack;
    import java.util.ArrayList;
    import java.util.List;
    import java.util.Stack;
    /**
     * @author 林小鹿
     * @version 1.0
     * (后缀表达式)逆波兰计算机
     */
    public class PolandNotation {
        public static void main(String[] args) {
            // 定义逆波兰表达式
            // (3+4)x5-6 => 3 4 + 5 x 6 -
            String suffixExpression = "3 4 + 5 * 6 -";
            // 1. 先将 suffixExpression 放到ArrayList中
            // 2. 将 ArrayList传递给一个方法，遍历ArrayList 配合栈完成计算
            List rpnList = getListString(suffixExpression);
            System.out.println(rpnList);
            int res = calculate(rpnList);
            System.out.println("计算机的结果=" + res);
        }
        // 将一个逆波兰表达式，依次将数据和运算符放入到ArrayList中·
        public static List getListString(String suffixExpression) {
            String[] s = suffixExpression.split(" ");
            List list = new ArrayList();
            for (String ele : s) {
                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 ls) {
            Stack stack = new Stack();
            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("运算符有误");
                    }
                    stack.push(res + "");
                }
            }
            return Integer.parseInt(stack.pop());
        }
    }
    

    中缀表达式转换成后缀表达式

    

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

    2. 从左至右扫描中缀表达式

    3. 遇到操作数时，将其压s2

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

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

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

       • 否则，将s1栈顶的运算符弹出并压入到s2中，再次转到(4.1步骤)与s1中新的栈顶运算符相比较

       • 遇到括号时：

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

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

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

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

    代码

    package com.xiaolu.stack;
    import java.util.ArrayList;
    import java.util.List;
    import java.util.Stack;
    /**
     * @author 林小鹿
     * @version 1.0
     * (后缀表达式)逆波兰计算机
     * 中缀表达式转成后缀表达式
     */
    public class PolandNotation {
        public static void main(String[] args) {
            //完成将一个中缀表达式转成后缀表达式的功能
            //1.1+((2+3)×4)-5=>转成123+4×+5
            //2。因为直接对str进行操作，不方便，因此先将"1+((2+3)×4)-5"=》中缀的表达式对应的L1st
            // 即"1+((2+3)×4)-5"=>ArrayList[1,+,(,(,2,+,3,),*,4,)-,5]
            String expression = "1+((2+3)*4)-5";
            List list = toInfixExpression(expression);
            System.out.println("中缀表达式：" + list);
            List parseSuffixExpressionList = parseSuffixExpressionList(list);
            System.out.println("后缀表达式：" + parseSuffixExpressionList);
            System.out.printf("expression=%d", calculate(parseSuffixExpressionList));
            /**
             // 定义逆波兰表达式
             // (3+4)x5-6 => 3 4 + 5 x 6 -
             String suffixExpression = "3 4 + 5 * 6 -";
             // 1. 先将 suffixExpression 放到ArrayList中
             // 2. 将 ArrayList传递给一个方法，遍历ArrayList 配合栈完成计算
             List rpnList = getListString(suffixExpression);
             System.out.println(rpnList);
             int res = calculate(rpnList);
             System.out.println("计算机的结果=" + res);
             **/
        }
        public static List parseSuffixExpressionList(List ls) {
            // 定义两个栈
            Stack s1 = new Stack(); // 符号栈
            // 因为存储中间结果s2栈在整个转换过程中没有pop操作，后面还需要逆序输出，因此可直接用List代替
            List s2 = new ArrayList();
            // 遍历ls
            for (String item : ls) {
                // 如果是一个数，直接入s2栈
                if (item.matches("\\d+")) {
                    s2.add(item);
                } else if (item.equals("(")) {
                    s1.push(item);
                } else if (item.equals(")")) {
                    while (!s1.peek().equals("(")) {
                        s2.add(s1.pop());
                    }
                    s1.pop(); // 消掉左括号
                } else {
                    //当item的优先级小于等于s1栈顶运算符，将s1栈顶的运算符弹出并加入到s2中，再次转到(4,1)与s1中新的栈顶运算符相比较
                    while (s1.size() != 0 && Operation.getValue(item) 
                        s2.add(s1.pop());
                    }
                    // 还需要将item压入栈
                    s1.push(item);
                }
            }
            while (s1.size() != 0) {
                s2.add(s1.pop());
            }
            return s2; // 因为是存放到List，因此按顺序输出就是对应的后缀表达式对应的List
        }
        // 将中缀表达式转成对应的List
        public static List
            ArrayList
                // 如果c是一个非数字，需要加入到ls
                if ((c = s.charAt(i)) = 48 && (c = s.charAt(i)) 
                        str += c; // 拼接
                        i++;
                    }
                    ls.add(str);
                }
            } while (i = 48 && (c = s.charAt(i)) 
                    str += c; // 拼接
                    i++;
                }
                ls.add(str);
            }
        } while (i