栈：栈及计算器模拟

港控/mmm° 2023-02-27 13:57 4阅读 0赞

# 1，栈基本介绍 #

*  栈是一种先入后出的有序列表
 *  栈限制线性表中**元素的插入和删除只能在线性表的同一端**进行的一种特殊线性表。允许插入和删除的一端，为变化的一端，称为栈顶，另一端为固定的一端，称为栈底
 *  出栈（`pop`）入栈（`push`）原理图如下：  
    ![在这里插入图片描述][20200718135737834.png]

# 2，栈模拟代码演示 #

## 2.1，数组模拟 ##

package com.self.datastructure.stack;
    
    import lombok.Data;
    
    /** * 通过数组模拟栈数据结构 * @author LiYanBin * @create 2020-01-10 14:53 **/
    public class ArrayStackDemo { 
    
        public static void main(String[] args) { 
            ArrayStack arrayStack = new ArrayStack(10);
            for (int i = 0; i < 10; i++, arrayStack.push(i));
            arrayStack.showDetails();
        }
    
        @Data
        private static class ArrayStack { 
            private int count; // 数组有效数据数量
    
            private int capacity; // 数组总长度
    
            private int[] stack; // 底层数组
    
            private static final int DEFAULT_LENGTH = 10;
    
            public ArrayStack() { 
                this(DEFAULT_LENGTH);
            }
    
            public ArrayStack(int length) { 
                this.capacity = length;
                this.stack = new int[length];
            }
    
            // 添加数据, 添加到数组尾部
            public void push(int data) { 
                if (isFull()) { 
                    throw new IndexOutOfBoundsException("数组已满...");
                }
                stack[count++] = data;
            }
    
            // 弹出数据, 从数组尾部弹出
            public int pop() { 
                if (isEmpty()) { 
                    throw new IndexOutOfBoundsException("数组为空...");
                }
                return stack[--count];
            }
    
            // 判断数组是否已满
            public boolean isFull() { 
                return count == capacity;
            }
    
            // 判断数组是否为空
            public boolean isEmpty() { 
                return count == 0;
            }
    
            // 栈遍历, 从栈顶开始遍历
            public void showDetails() { 
                int tempCount = count;
                for (;tempCount > 0;) { 
                    System.out.println(stack[--tempCount]);
                }
            }
        }
    
    }

## 2.2，链表模拟 ##

package com.self.datastructure.stack;
    
    import lombok.Data;
    
    /** * 通过单向链表模拟栈数据结构 * @author LiYanBin * @create 2020-01-10 15:15 **/
    public class LinkedStackDemo { 
    
        public static void main(String[] args) { 
            LinkedStack linkedStack = new LinkedStack();
            for (int i = 0; i < 10; i++, linkedStack.push(i));
            for (int i = 0; i < 10; i++)
                System.out.println(linkedStack.pop().getData());
        }
    
    
        private static class LinkedStack { 
    
            // 头结点, 该几点不虚拟
            private Node head;
    
            // 添加链表节点到栈中
            public void push(int data) { 
                Node newNode = new Node(data);
                if (null == head) { 
                    head = newNode;
                } else { 
                    Node temp = head;
                    // 获取到最后一个有效节点
                    for (;null != temp.getNext(); temp = temp.getNext());
                    temp.setNext(newNode);
                }
            }
    
            public Node pop() { 
                // 节点为空处理
                if (isEmpty()) { 
                    throw new IndexOutOfBoundsException("链表为空...");
                }
                // 只存在头节点处理
                Node temp = head;
                if (null == head.getNext()) { 
                    head = null;
                    return temp;
                } else { 
                    // 获取到尾节点的上一个节点
                    for (temp = head; temp.getNext().getNext() != null; temp = temp.getNext());
                    // 获取的temp表示要获取节点的前置节点
                    // 返回目标节点, 并将前置节点的next为空置空
                    Node resultData = temp.getNext();
                    temp.setNext(null);
                    return resultData;
                }
            }
    
            public boolean isEmpty() { 
                return head == null;
            }
    
    
        }
    
        /** * 自定义链表 */
        @Data
        private static class Node { 
            private int data;
    
            private Node next;
    
            public Node(int data) { 
                this(data, null);
            }
    
            public Node(Node node) { 
                this(node.getData(), null);
            }
    
            public Node(int data, Node next) { 
                this.data = data;
                this.next = next;
            }
    
        }
    
    }

# 3，栈模拟计算器\_中缀表达式 #

## 3.1，基本思路 ##

*  定义两个栈对象进行数据存储，分别为数字栈对象和符号栈对象
    
     *  数组栈对运算数据进行存储
     *  符号栈对操作符号进行存储
 *  从左至右对数据依次入栈, 对应数据入对应栈
 *  对操作服务进行优先级排序, 排序优先级为 `( > / > * > - > +`
 *  符号栈数据入栈时, 判断栈顶数据优先级是否大于当前优先级
    
     *  如果小于或者等于当前优先级, 则数据依次入栈
     *  如果大于当前优先级, 则先从符号栈弹出一个符号, 并从数字栈弹出两个数字进行计算, 计算完成后, 数字入栈并继续该操作直到符合优先级小于
 *  对于带括号数据, 直接拎出括号部分进行计算完成后并入栈
 *  表达式遍历完成后, 依次弹出栈元素进行计算
 *  全部基于整数操作，未考虑小数

## 3.2，代码实现 ##

package com.self.datastructure.stack;
    
    import java.util.ArrayList;
    import java.util.List;
    import java.util.Stack;
    
    /** * 中缀表达式实现计算器 * 基本思路 * 1, 定义两个栈对象进行数据存储, 分别为数字栈对象和符号栈对象, 数组栈对运算数据进行存储, 符号栈对操作符号进行存储 * 2, 从左至右对数据依次入栈, 对应数据入对应栈 * 3, 对操作服务进行优先级排序, 排序优先级为 ( > / > * > - > + * 4, 符号栈数据入栈时, 判断栈顶数据优先级是否大于当前优先级 * 5, 如果小于或者等于当前优先级, 则数据依次入栈 * 6, 如果大于当前优先级, 则先从符号栈弹出一个符号, 并从数字栈弹出两个数字进行计算, 计算完成后, 数字入栈并继续该操作直到符合第5步 * 7, 对于带括号数据, 直接拎出括号部分进行计算并入栈 * 8, 表达式遍历完成后, 依次弹出栈元素进行计算 * 9, 暂时不考虑符号和小数 * @author LiYanBin * @create 2020-01-13 9:06 **/
    public class MiddleCalculateDemo { 
    
        public static void main(String[] args) { 
            System.out.println("最终结果: " + calculate("4-(3+(2-1))"));;
        }
    
        public static int calculate(String permission) { 
            // 表达式转数组, 按数字和符号位拆分, 暂不考虑负数
            String[] permissionArray = transformPermission(permission);
            // 数字栈
            Stack<Integer> numberStack = new Stack<>();
            // 符号栈
            Stack<String> operateStack = new Stack<>();
            // 依次获取元素进行处理
            for (int index = 0; index < permissionArray.length; index++) { 
                try { 
                    String element = permissionArray[index]; // 获取当前元素
                    if (element.matches("^[+-]?[0-9]+$")) { 
                        numberStack.push(Integer.valueOf(element)); // 数字位直接入栈
                        continue;
                    } else if (element.matches("^[+\\-*/]$")) { 
                        // 入栈符号, 入栈时对符号优先级进行排序
                        dealOperatePriority(numberStack, operateStack, element);
                        continue;
                    } else if (element.matches("^[(]$")) { 
                        // 括号进行处理, 从当前括号获取到匹配的括号, 即最后一个括号, 拼接一个完整的表达式递归处理
                        int endIndex = findMatchRightBracket(permissionArray, index);
                        String newPermission = combineBracketPermission(permissionArray, index, endIndex);
                        int bracketResult = calculate(newPermission);
                        numberStack.push(bracketResult);
                        // index直接后移
                        index = endIndex;
                    }
                } catch (Exception e) { 
                    System.out.println("发生错误: index: " + index);
                    e.printStackTrace();
                }
            }
            // 全部入栈完成后, 弹栈
            return doCalculate(numberStack, operateStack);
        }
    
        // 对栈顶操作符与当前操作符进行优先级判断
        // 如果栈顶优先级大于当前优先级, 则先对栈顶优先级进行计算
        // 如果栈顶优先级小于当前优先级, 弹出现有数据进行计算, 计算后重复操作
        private static void dealOperatePriority(Stack<Integer> numberStack, Stack<String> operateStack, String operate) { 
            if (operateStack.isEmpty()) { 
                operateStack.push(operate); // 为空直接入库处理
                return;
            }
            // 获取栈顶操作符
            String preOperate = operateStack.peek();
            // 获取优先级
            if (higgerPriority(operate, preOperate)) { 
                // 当前优先级高, 直接入栈
                operateStack.push(operate);
            } else { 
                // 当前优先级低, 弹栈历史数据进行计算
                Integer number1 = numberStack.pop();
                Integer number2 = numberStack.pop();
                operateStack.pop(); // 弹出
                Integer result = doCalculate(number1, number2, preOperate);
                numberStack.push(result);
                // 计算完成后, 递归该操作
                dealOperatePriority(numberStack, operateStack, operate);
            }
        }
    
        // 判断优先级
        private static boolean higgerPriority(String operate, String preOperate) { 
            int priorityCount = getPriorityCount(operate);
            int prePriorityCount = getPriorityCount(preOperate);
            return priorityCount >= prePriorityCount;
        }
    
        // 获取优先级代表的标志位
        private static int getPriorityCount(String operate) { 
            int priorityCount = 0;
            switch (operate) { 
                case "+": priorityCount = 1;
                    break;
                case "-": priorityCount = 2;
                    break;
                case "*": priorityCount = 3;
                    break;
                case "/": priorityCount = 4;
                    break;
            }
            return priorityCount;
        }
    
        // 最终计算栈数据
        private static int doCalculate(Stack<Integer> numberStack, Stack<String> operateStack) { 
            Integer number1 = numberStack.pop();
            Integer number2 = numberStack.pop();
            String operate = operateStack.pop();
            // 计算数据
            Integer result = doCalculate(number1, number2, operate);
            numberStack.push(result);
            // 两个栈都不为空, 继续递归进行计算
            if (!numberStack.isEmpty() && !operateStack.isEmpty()) { 
                result = doCalculate(numberStack, operateStack);
            }
            return result;
        }
    
        // 进行计算
        private static Integer doCalculate(Integer number1, Integer number2, String operate) { 
            switch (operate) { 
                case "+" :
                    return number1 + number2;
                case "-" :
                    return number2 - number1;
                case "*" :
                    return number1 * number2;
                case "/" :
                    return number2 / number1;
                default:
                    throw new RuntimeException("运算符无效...");
            }
        }
    
        // 获取括号内有效数据
        private static String combineBracketPermission(String[] permissionArray, int index, int endIndex) { 
            StringBuffer sb = new StringBuffer();
            for (index = index + 1; index < endIndex; index++) { 
                sb.append(permissionArray[index]);
            }
            return sb.toString();
        }
    
        // 匹配该左括号对应的右括号
        private static int findMatchRightBracket(String[] permissionArray, int currIndex) { 
            int matchingIndex = 0;
            // 获取到表达式组最后一个对应的), 为当前(的匹配括号
            for (currIndex = currIndex + 1; currIndex < permissionArray.length; currIndex++) { 
                if (")".equals(permissionArray[currIndex])) { 
                    matchingIndex = currIndex;
                }
            }
            return matchingIndex;
        }
    
        // 转换表达式为数组形式, 方便后续操作
        private static String[] transformPermission(String permission) { 
            List<String> lstPer = new ArrayList<>(10);
            char[] perArray = permission.toCharArray();
            StringBuffer sb = new StringBuffer();
            // 处理首元素带符号
            boolean isFirst = true;
            for (char data : perArray) { 
                // 截取符号位
                if ((data >= '0' && data <= '9') || (String.valueOf(data).matches("^[+-]$") && isFirst)) { 
                    sb.append(data);
                    isFirst = false;
                } else { 
                    // 数字位遍历完成, 入队列
                    if (0 != sb.length()) { 
                        lstPer.add(sb.toString());
                        sb.setLength(0);
                    }
                    // 关联入符号位
                    lstPer.add(String.valueOf(data));
                    if (String.valueOf(data).equals("(")) { 
                        isFirst = true;
                    }
                }
            }
            // 添加表达式最后一个数字元素
            // 最后一位如果为), 则sb长度为0, 不进行拼接
            if (0 != sb.length()) { 
                lstPer.add(sb.toString());
            }
            System.out.println("表达式转数组后: " + lstPer);
            String[] permissionAarray = new String[lstPer.size()];
            for (int i = 0; i < lstPer.size(); i++) { 
                permissionAarray[i] = lstPer.get(i);
            }
            return permissionAarray;
        }
    
    }

# 4，中缀表达式转后缀表达式 #

## 4.1，转换规则 ##

1.  初始化两个栈，运算符栈`s1`和数据元素栈`s2`
2.  从左至右扫描中缀表达式
3.  遇到数据元素时，直接压入到`s2`栈
4.  遇到运算符时，比较其与`s1`栈顶运算符的优先级
    
     *  如果`s1`栈为空，或者栈顶运算符为左括号`(`，则直接将运算符入栈
     *  如果当前运算符优先级比栈顶运算符优先级高，则将运算符直接压入`s1`
     *  如果当前运算符优先级小于等于栈顶运算符，则将符号栈`s1`的栈顶运算符弹出并压入到数据元素栈`s2`中，并重复该动作比较下一个栈顶运算符
5.  遇到括号时
    
     *  如果是左括号`(`，则直接压入`s1`，包括左括号处理及栈顶为左括号场景
     *  如果是右括号`)`，则依次弹出`s1`栈顶的运算符，并压入到`s2`，直到遇到左括号为止，此时可以将这一对括号丢弃
6.  重复步骤2到步骤5，直到扫描到表达式尾部
7.  将`s1`中剩余的运算符依次弹出并压入`s2`
8.  逆序输出`s2`中的元素并拼接为表达式（因为栈是后进先出），即为中缀表达式的后缀表达式

## 4.2，转换举例说明 ##

*  中缀表达式`1+((2+3)*4)-5`转换为`123+4*+5-`  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTE5NzYzODg_size_16_color_FFFFFF_t_70]

## 4.3，代码实现 ##

package com.self.datastructure.stack;
    
    import java.util.ArrayList;
    import java.util.List;
    import java.util.Stack;
    
    /** * 表达式转换, 中缀表达式转后缀表达式 * @author LiYanBin * @create 2020-01-13 11:27 **/
    public class TransformPermission { 
    
        public static void main(String[] args) { 
            System.out.println(transformPermission("10+((20+30)*40)-50"));;
        }
    
        // 转换
        public static String transformPermission(String permission) { 
            // 字符串表达式转数据
            String[] permissionArray = MiddleCalculateDemo.transformPermission(permission);
            // 中缀表达式转后缀表达式
            return doTransformPermission(permissionArray);
        }
    
        //
        private static String doTransformPermission(String[] permissionArray) { 
            if (0 == permissionArray.length) { 
                return null;
            }
            // 数字栈
            Stack<String> numberStack = new Stack<>();
            // 符号栈
            Stack<String> operateStack = new Stack<>();
            // 遍历表达式数组, 进行处理
            for (int i = 0; i < permissionArray.length; i++) { 
                // 数字直接入栈
                if (permissionArray[i].matches("^[+-]?[0-9]+$")) { 
                    numberStack.push(permissionArray[i]);
                } else if(permissionArray[i].matches("^\$$")) { 
                    // 左括号直接入栈
                    operateStack.push(permissionArray[i]);
                } else if(permissionArray[i].matches("^\$$")) { 
                    // 右括号,将最近的左括号前的数据, 移到数字栈
                    moveElement(numberStack, operateStack);
                } else if(permissionArray[i].matches("^[+\\-*/]$")) { 
                    // 运算符号, 进行优先级判断
                    while (operateStack.size() != 0 && !higgerPriority(permissionArray[i], operateStack.peek())) { 
                        numberStack.push(operateStack.pop());
                    }
                    operateStack.push(permissionArray[i]);
                }
            }
            // 处理完成后, 弹出符号栈元素到数字栈
            for (;0 != operateStack.size(); numberStack.push(operateStack.pop()));
            // 返回表达式
            List<String> lstElement = new ArrayList<>(10);
            for (;0 != numberStack.size(); lstElement.add(numberStack.pop()));
            StringBuffer sb = new StringBuffer();
            for (int i = lstElement.size() - 1; i >= 0; i--) { 
                // 加上一个中断位
                sb.append(lstElement.get(i) + "#");
            }
            return sb.toString();
        }
    
        // 判断优先级
        private static boolean higgerPriority(String operate, String preOperate) { 
            int priorityCount = getPriorityCount(operate);
            int prePriorityCount = getPriorityCount(preOperate);
            return priorityCount > prePriorityCount;
        }
    
        // 获取优先级代表的标志位
        private static int getPriorityCount(String operate) { 
            int priorityCount = 0;
            switch (operate) { 
                case "+": priorityCount = 1;
                    break;
                case "-": priorityCount = 1;
                    break;
                case "*": priorityCount = 2;
                    break;
                case "/": priorityCount = 2;
                    break;
                // 括号不参与, 遇到括号直接入栈
                case "(": priorityCount = 0;
                    break;
            }
            return priorityCount;
        }
    
        // 将符号栈数据迁移到数字栈
        private static void moveElement(Stack<String> numberStack, Stack<String> operateStack) { 
            for (String currOperate = operateStack.pop(); !"(".equals(currOperate); numberStack.push(currOperate), currOperate = operateStack.pop());
        }
    
    }

# 5，栈模拟计算器\_后缀表达式 #

## 5.1，思路分析 ##

*  从左至右扫描后缀表达式（逆波兰表达式）
 *  对扫描的数字位压栈处理，继续向后扫描
 *  扫描到运算符时，从栈中弹出两个数字位，并根据运算符进行对应操作
 *  计算完成后，将计算结果压栈并进行后续处理

package com.self.datastructure.stack;
    
    import java.util.Arrays;
    import java.util.List;
    import java.util.Stack;
    
    /** * 后缀表达式进行计算器计算 * @author LiYanBin * @create 2020-01-13 14:40 **/
    public class SuffixCalculateDemo { 
    
        public static void main(String[] args) { 
            // 转换后的后缀表达式: 34+5*6-
            // 每一位之间添加中断符#
            String permission = TransformPermission.transformPermission("10+((20+30)*40)-50");
            System.out.println(calculate(permission));
        }
    
        // 后缀表达式计算
        public static int calculate(String suffixPermission) { 
            // 对表达式进行list转换
            List<String> lstElement = Arrays.asList(suffixPermission.split("#", -1));
            Stack<Integer> numberStack = new Stack<>();
            for (String element : lstElement) { 
                if (element.matches("^[+-]?[0-9]+$")) { 
                    numberStack.push(Integer.valueOf(element));
                } else if (element.matches("^[+\\-*/]$")) { 
                    doCalculate(numberStack, element);
                }
            }
            // 全部计算完成后, 弹出结果
            return numberStack.pop();
        }
    
        // 计算
        private static void doCalculate(Stack<Integer> numberStack, String operate) { 
            if (numberStack.size() < 2) { 
                throw new RuntimeException("表达式有误...");
            }
            // 栈后入先出, 所以应该用 number2 [operate] number1
            Integer number1 = numberStack.pop();
            Integer number2 = numberStack.pop();
            numberStack.push(getResult(number2, number1, operate));
        }
    
        private static Integer getResult(Integer firstNumber, Integer secondNumber, String operate) { 
            switch (operate) { 
                case "+":
                    return firstNumber + secondNumber;
                case "-":
                    return firstNumber - secondNumber;
                case "*":
                    return firstNumber * secondNumber;
                case "/":
                    return firstNumber / secondNumber;
            }
            throw new RuntimeException("操作符无效...");
        }
    
    }

[20200718135737834.png]: /images/20230209/1e7a17fb2ab64671b42d549ca04c2b2c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTE5NzYzODg_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/2020071814043251.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTE5NzYzODg=,size_16,color_FFFFFF,t_70