线性结构：栈

偏执的太偏执、 2022-11-06 11:59 230阅读 0赞

### 目录 ###

*  第一章 栈介绍
 *  第二章 栈实现
 *   *  2.1、实现代码
     *  2.2、测试代码
 *  第三章 栈实战
 *   *  3.1、计算器的设计与实现
     *  3.2、程序的基本框架结构
     *  3.2、去除表达式所有空格
     *  3.3、替换表达式乘法符号
     *  3.4、表达式转为中缀集合
     *  3.5、中缀转为后缀表达式
     *  3.6、开始计算后缀表达式

--------------------

> 项目地址：https://gitee.com/caochenlei/data-structures

# 第一章 栈介绍 #

存储货物或供旅客住宿的地方，可引申为仓库、中转站 。例如：我们现在生活中的酒店，在古时候叫客栈，是供旅客休息的地方，旅客可以进客栈休息，休息完毕后就离开客栈。我们把生活中的栈的概念引入到计算机中，就是供数据休息的地方，它是一种数据结构，数据既可以进入到栈中， 又可以从栈中出去。

栈（Stack）又名堆栈，它是一种基于先进后出（FILO-First In Last Out）且运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。

![e3f80c2c0ddeb2e21b3ff19c00b89a92.png][]

进栈（PUSH）算法的实现（S代表堆栈、TOP代表栈顶、E代表变量）：

*  ①、进栈前首先检查栈是否已满，满则溢出，不满则转去执行②
 *  ②、置TOP=TOP+1
 *  ③、S(TOP)=E

出栈（POP）算法的实现（S代表堆栈、TOP代表栈顶、E代表变量）：

*  ①、出栈前先检查是否已为空栈，空则下溢，不空则转去执行②
 *  ②、E=S(TOP)
 *  ③、置TOP=TOP-1

# 第二章 栈实现 #

## 2.1、实现代码 ##

public class Stack<E> { 
        private E[] elements;   //存放堆栈元素
        private int maxSize;    //存放堆栈大小
        private int top;        //堆栈栈顶指针
    
        public Stack(int capacity) { 
            top = -1;
            maxSize = capacity;
            elements = (E[]) new Object[capacity];
        }
    
        //判断堆栈是否为空
        public boolean isEmpty() { 
            return top == -1;
        }
    
        //判断堆栈是否已满
        public boolean isFull() { 
            return top == maxSize - 1;
        }
    
        //获取堆栈元素个数
        public int size() { 
            return top + 1;
        }
    
        //进栈操作
        public void push(E e) { 
            //判断堆栈是否已满
            if (isFull()) { 
                throw new RuntimeException("堆栈已满，无法操作！");
            }
            //进栈操作
            top++;
            elements[top] = e;
        }
    
        //出栈操作
        public E pop() { 
            //判断堆栈是否为空
            if (isEmpty()) { 
                throw new RuntimeException("堆栈为空，无法操作！");
            }
            //出栈操作
            E e = elements[top];
            top--;
            return e;
        }
    
        //查看栈顶
        public E peek() { 
            //判断堆栈是否为空
            if (isEmpty()) { 
                throw new RuntimeException("堆栈为空，无法操作！");
            }
            //查看栈顶
            return elements[top];
        }
    
        @Override
        public String toString() { 
            //获取堆栈有效元素
            StringBuilder sb = new StringBuilder();
            sb.append("[");
            for (int i = 0; i <= top; i++) { 
                sb.append(" " + elements[i] + " ");
            }
            sb.append("]");
            //返回堆栈详细信息
            return "Stack{" +
                    "elements=" + sb.toString() +
                    ", eleSize=" + size() +
                    ", maxSize=" + maxSize +
                    ", top=" + top +
                    '}';
        }
    }

## 2.2、测试代码 ##

public class StackTest { 
        public static void main(String[] args) { 
            Stack<String> stack = new Stack<>(4);
    
            System.out.println("==========第一块输出内容：开始==========");
            System.out.println(stack);
            stack.push("张三");
            stack.push("李四");
            stack.push("王五");
            System.out.println(stack);
            System.out.println("==========第一块输出内容：结束==========");
            System.out.println();
    
            System.out.println("==========第二块输出内容：开始==========");
            System.out.println(stack.peek());
            System.out.println("==========第二块输出内容：结束==========");
            System.out.println();
    
            System.out.println("==========第三块输出内容：开始==========");
            System.out.println(stack);
            System.out.println(stack.pop());
            System.out.println(stack.pop());
            System.out.println(stack.pop());
            System.out.println(stack);
            System.out.println("==========第三块输出内容：结束==========");
        }
    }

==========第一块输出内容：开始==========
    Stack{ elements=[], eleSize=0, maxSize=4, top=-1}
    Stack{ elements=[ 张三  李四  王五 ], eleSize=3, maxSize=4, top=2}
    ==========第一块输出内容：结束==========
    
    ==========第二块输出内容：开始==========
    王五
    ==========第二块输出内容：结束==========
    
    ==========第三块输出内容：开始==========
    Stack{ elements=[ 张三  李四  王五 ], eleSize=3, maxSize=4, top=2}
    王五
    李四
    张三
    Stack{ elements=[], eleSize=0, maxSize=4, top=-1}
    ==========第三块输出内容：结束==========

# 第三章 栈实战 #

## 3.1、计算器的设计与实现 ##

设计的目标：

实现高级计算器来计算`(1+((2+3)×4)-5)%10/0.5`的值，运算符支持加、减、乘、除、取余，数字支持多位数、小数，但是不支持负数计算，例如：`-3+2`。

前置的知识：

**中缀表达式：** 中缀表达式就是我们平常生活中使用的表达式，例如：`1+3*2`，`2-(1+3)`等等，中缀表达式的特点是：二元运算符总是置于两个操作数中间。中缀表达式是人们最喜欢的表达式方式，因为简单，易懂。但是对于计算机来说就不是这样了，因为中缀表达式的运算顺序不具有规律性。不同的运算符具有不同的优先级，如果计算机执行中缀表达式，需要解析表达式语义，做大量的优先级相关操作。

**后缀表达式：** 后缀表达式也叫逆波兰式（Reverse Polish notation，RPN，或逆波兰记法），后缀表达式的特点是：将运算符写在操作数之后。我们平时写`a+b`，这是中缀表达式，写成后缀表达式就是：`ab+`，`(a+b)*c-(a+b)/e`的后缀表达式为：

→`((a+b)*c)-((a+b)/e)`

→`((a+b)*c)((a+b)/e)-`

→`((a+b)c*)((a+b)e/)-`

→`(ab+c*)(ab+e/)-`

→`ab+c*ab+e/-`

<table> 
 <thead> 
  <tr> 
   <th>中缀表达式</th> 
   <th>后缀表达式</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>a+b</td> 
   <td>ab+</td> 
  </tr> 
  <tr> 
   <td>a+(b-c)</td> 
   <td>abc-+</td> 
  </tr> 
  <tr> 
   <td>a+(b-c)*d</td> 
   <td>abc-d*+</td> 
  </tr> 
  <tr> 
   <td>a*(b-c)+d</td> 
   <td>abc-*d+</td> 
  </tr> 
 </tbody> 
</table>

最终的效果：

去除表达式所有空格：(1+((2+3)×4)-5)%10/0.5
    替换表达式乘法符号：(1+((2+3)*4)-5)%10/0.5
    表达式转为中缀集合：[(, 1, +, (, (, 2, +, 3, ), *, 4, ), -, 5, ), %, 10, /, 0.5]
    中缀转为后缀表达式：[1, 2, 3, +, 4, *, +, 5, -, 10, %, 0.5, /]
    开始计算后缀表达式：12.0

## 3.2、程序的基本框架结构 ##

//计算器主程序
    public class Calculator { 
        public static void main(String[] args) { 
            String expression = "(1+((2+3)×4)-5)%10/0.5";
    
            //1.去除表达式所有空格
    
            //2.替换表达式乘法符号
    
            //3.表达式转为中缀集合
    
            //4.中缀转为后缀表达式
    
            //5.开始计算后缀表达式
    
        }
        
        //上边的五个方法需要写在这里...
    }
    
    //计算器运算符
    class Operator { 
        private static int ADD_PRIORITY = 1;//代表加法运算符优先级
        private static int SUB_PRIORITY = 1;//代表减法运算符优先级
        private static int MUL_PRIORITY = 2;//代表乘法运算符优先级
        private static int DIV_PRIORITY = 2;//代表除法运算符优先级
        private static int SUR_PRIORITY = 2;//代表取余运算符优先级
    
        //判断是否是数字值
        public static boolean isNumber(String s) { 
            return s.matches(("^(\\-|\\+)?\\d+(\\.\\d+)?$"));
        }
    
        //返回运算符优先级
        public static int getPriority(String operator) { 
            int result = 0;
            switch (operator) { 
                case "+": result = ADD_PRIORITY; break;
                case "-": result = SUB_PRIORITY; break;
                case "*": result = MUL_PRIORITY; break;
                case "/": result = DIV_PRIORITY; break;
                case "%": result = SUR_PRIORITY; break;
                default:  break;
            }
            return result;
        }
    }

## 3.2、去除表达式所有空格 ##

//1.去除表达式所有空格
    expression = expression.replaceAll("\\s+", "");
    System.out.println("去除表达式所有空格：" + expression);

## 3.3、替换表达式乘法符号 ##

//2.替换表达式乘法符号
    expression = expression.replaceAll("×", "*");
    System.out.println("替换表达式乘法符号：" + expression);

## 3.4、表达式转为中缀集合 ##

//3.表达式转为中缀集合
    List<String> infixList = strToInfixList(expression);
    System.out.println("表达式转为中缀集合：" + infixList);

private static List<String> strToInfixList(String expression) { 
        //1.创建集合
        List<String> list = new ArrayList<>();
        //2.定义指针
        int i = 0;
        //3.获取字符
        char c;
        //4.循环遍历
        do { 
            //如果此字符非数字，直接加入到集合中
            if ((c = expression.charAt(i)) < '0' || (c = expression.charAt(i)) > '9') { 
                list.add(String.valueOf(c));
                i++;
            }
            //如果此字符是数字，还需要考虑多位数以及小数部分
            else { 
                String str = "";
                while ((i < expression.length() && (c = expression.charAt(i)) >= '0' && (c = expression.charAt(i)) <= '9')
                       || (i < expression.length() && (c = expression.charAt(i)) == '.')) { 
                    str += c;
                    i++;
                }
                list.add(str);
            }
        } while (i < expression.length());
        //5.返回集合
        return list;
    }

## 3.5、中缀转为后缀表达式 ##

//4.中缀转为后缀表达式
    List<String> suffixList = infixToSuffixList(infixList);
    System.out.println("中缀转为后缀表达式：" + suffixList);

private static List<String> infixToSuffixList(List<String> list) { 
        //1.定义一个符号栈
        Stack<String> s1 = new Stack<>();
        //2.储存最后的结果
        List<String> s2 = new ArrayList<>();
        //3.循环遍历集合
        for (String item : list) { 
            //如果是数字，直接入s2
            if (Operator.isNumber(item)) { 
                s2.add(item);
            }
            //如果左括号，直接入s1
            else if (item.equals("(")) { 
                s1.push(item);
            }
            //如果右括号，则依次弹出s1栈顶的运算符并压入s2，直到遇到左括号为止，此时将这一对括号消除
            else if (item.equals(")")) { 
                while (s1.size() != 0 && !s1.peek().equals("(")) { 
                    s2.add(s1.pop());
                }
                s1.pop();//消除左括号
            }
            //当item的优先级小于等于s1栈顶运算符, 将s1栈顶的运算符弹出并加入到s2中，直到item的优先级大于s1栈顶运算符为止
            else { 
                while (s1.size() != 0 && Operator.getPriority(item) <= Operator.getPriority(s1.peek())) { 
                    s2.add(s1.pop());
                }
                s1.push(item);//item入s1
            }
        }
        //4.处理剩余运算符
        while (s1.size() != 0) { 
            s2.add(s1.pop());
        }
        //5.返回最终的结果
        return s2;
    }

## 3.6、开始计算后缀表达式 ##

//5.开始计算后缀表达式
    double result = calculate(suffixList);
    System.out.println("开始计算后缀表达式：" + result);

private static double calculate(List<String> list) { 
        //1.创建一个堆栈
        Stack<String> stack = new Stack<>();
        //2.循环遍历集合
        for (String item : list) { 
            //如果是数字，该数字入栈
            if (Operator.isNumber(item)) { 
                stack.push(item);
            }
            //如果非数字，计算后入栈
            else { 
                double num2 = Double.parseDouble(stack.pop());
                double num1 = Double.parseDouble(stack.pop());
                double 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 if (item.equals("%")) { 
                    res = num1 % num2;
                }
                stack.push(String.valueOf(res));
            }
        }
        //3.返回运算结果
        return Double.parseDouble(stack.pop());
    }

[e3f80c2c0ddeb2e21b3ff19c00b89a92.png]: /images/20221023/36b3bb682b7c4035ba6efaa56925ffed.png