栈的应用-综合计数器的实现

左手的ㄟ右手 2024-03-04 01:23 39阅读 0赞

##  ##

**目录**

前言

一、思路分析

二、代码实现

总结

## 前言 ##

在实现综合计数器之前,大家应该先了解一下什么是前中后缀表达式

前缀、中缀和后缀表达式是表示数学表达式的三种不同方式。

1.  前缀表达式（也称为波兰式或前缀记法）：操作符位于操作数之前。例如，"+ 2 3"表示加法操作，其中2和3是操作数。
2.  中缀表达式：操作符位于操作数之间。这是我们通常使用的数学表达式表示方式。例如，"2 + 3"表示加法操作，其中2和3是操作数。
3.  后缀表达式（也称为逆波兰式或后缀记法）：操作符位于操作数之后。例如，"2 3 +"表示加法操作，其中2和3是操作数。

这三种表达式都可以表示相同的数学运算，只是操作符和操作数的排列顺序不同。在计算机中，后缀表达式常用于数学表达式的求值，因为它可以通过使用栈来进行简单而高效的计算。

本次实现综合计算器就是借助后缀表达式来实现,为了简单起见,我们并不加入()等的符号

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

## 一、思路分析 ##

定义两个栈,一个栈为数栈(NumStack)用来存放数字,另一个栈为符号栈,用来存放符号

1. 通过一个 index 值（索引），来遍历我们的表达式

2. 如果我们**发现是一个数字****,** 就直接入数栈

3. 如果发现**扫描到是一个符号**,  就分如下情况

3.1 如果发现当前的符号栈为 空，就直接入栈

3.2 如果符号栈有操作符，就进行比较,如**果当前的操作符的优先级小于或者等于栈中的操作符**， 就需要从数栈中pop出两个数,在从符号栈中pop出一个符号，进行运算，将得到结果，入数栈，然后将当前的操作符入符号栈， 如**果当前的操作符的优先级****大于****栈中的操作符****， 就直接入符号栈****.**

**4.** **当表达式扫描完毕，就顺序的从 数栈和符号栈中****pop****出相应的数和符号，并运行****.**

**5.** **最后在数栈只有一个数字，就是表达式的结果**

我们来举个例子 图解 计算 7\*2\*2-5+1 = 24

![72e44d3a55794062b0de79909803bb87.png][]

![2a8a9b10791546c8a76aefcf7596e7e5.png][]

![17d5aa44bd2c456d920bb58e1801e82b.png][]

![b991d95bea79444fbb4e1ea4b0ee595f.png][]

![27879343c1ee4e498836e8f630d4f2cf.png][]

![ebe4097596e84fb8b08ed2ce02f5400d.png][]

![58ca6be89ee54b23af65bf3aba96dd14.png][]![dc00a92374ae489eadac2ae3a03132fa.png][]![68ea83ddac7040afa4b6340080174e2c.png][]![84a1b8b529b64a11b86c1aa5f4aa430f.png][]

![4a36a30667c14fa68da533e4d344b372.png][]

![40590324321740e88dd960203343da05.png][]

![cee3e2af23c34d6ab21b5b9a35ee53f8.png][]

## 二、代码实现 ##

代码量太大,不可能一步一步解析了,上面的过程如果能看懂,并且编程有一定基础,下面代码应该不成问题,代码出处[033\_尚硅谷\_栈实现综合计算器-思路分析(1)\_哔哩哔哩\_bilibili][033_-_1_bilibili]

大家可以去看看

package 逆波兰计数器;
    
    import StackDemo.StackEmptyException;
    
    import java.util.Arrays;
    import java.util.Scanner;
    
    class Test{
        public static void main(String[] args) {
            String str = "7*2*2-5+1";
            ArrayStack numStack = new ArrayStack(10);
            ArrayStack operaStack = new ArrayStack(10);
            String s = "";
            int nums1 = 0;
            int nums2 = 0;
            int index = 0;
            int opera = 0;
            char ch = ' ';
            while (true) {
                ch = str.charAt(index);
                // 判断该字符是否是符号
                if(operaStack.isOpera(ch)){
                    // 判断符号栈是否为空
                    if(!operaStack.isEmpty()){
                        // 判断优先级
                        if(operaStack.priority(ch) <= operaStack.priority(operaStack.peek())){
                            nums1 = numStack.pop();
                            nums2 = numStack.pop();
                            opera = operaStack.pop();
                            int cal = numStack.cal(nums1, nums2, opera);
                            numStack.push(cal);
                            operaStack.push(ch);
                        }else{
                            operaStack.push(ch);
                        }
                    }else{
                        // 符号栈为空,直接入栈
                        operaStack.push(ch);
                    }
                }else{
                    boolean flag = true;// 定义标志位 检查字符串是否达到末尾
    
                    // 处理非个位数的情况 如 88 66 这样的数
                    while (!operaStack.isOpera(ch)) {
                        s+=ch;
                        if(index == str.length() -1 ){
                            numStack.push(Integer.parseInt(s));
                            flag = false;
                            break;
                        }else {
                            index++;
                            ch = str.charAt(index);
                        }
                    }
                    if(!flag){
                        break;
                    }
                    numStack.push(Integer.parseInt(s));
                    s = "";
                    index--;
                }
                index++;
                if(index>=str.length()){
                    break;
                }
            }
    
            while (true) {
                if(operaStack.isEmpty()){
                    System.out.println(str+"="+numStack.pop());
                    break;
                }
                nums1 = numStack.pop();
                nums2 = numStack.pop();
                opera = operaStack.pop();
                int cal = numStack.cal(nums1, nums2, opera);
                numStack.push(cal);
            }
        }
    
    }
    
    
    
    public class ArrayStack {
        private final int capacity;
        private int top = -1;
        private int[] stack ;
    
        public ArrayStack(int capacity){
            this.capacity = capacity;
            stack = new int[capacity];
        }
    
        // 入栈
        public void push(int data){
            if(isFull()){
                stack = Arrays.copyOf(stack,capacity*2);
            }
            top++;
            stack[top] = data;
        }
    
        // 出栈
        public int pop(){
            if(isEmpty()){
                throw new StackEmptyException("队列为空,无法删除元素");
            }
    
            int value = stack[top];
            top--;
            return value;
        }
    
        // 查看栈顶的值
        public int peek(){
            return stack[top];
        }
    
        // 制定优先级规则
        public int priority(int opera){
            if(opera == '*' || opera == '/'){
                return 1;
            }else if(opera == '+' || opera == '-'){
                return 0;
            }else{
                return -1;
            }
        }
    
    
        // 判断是否为运算符
        public boolean isOpera(int val){
            return val == '+' || val == '-' || val == '*' || val == '/';
        }
    
        // 运算方法
        public int cal(int num1,int num2,int opera){
            return  switch (opera) {
                case '+' -> num1 + num2;
                case '-' -> num2 - num1;
                case '*' -> num1 * num2;
                case '/' -> num2 / num1;
                default -> -1;
            };
        }
    
        public boolean isFull(){
            return top == capacity - 1;
        }
        public boolean isEmpty(){
            return top == - 1;
        }
    }

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

## 总结 ##

关于栈的应用远不止于此,大家也不必全部了解,只要能运用到这种程度,在刷点面试题,应付面试足矣!

[72e44d3a55794062b0de79909803bb87.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/04/edfa4f2bc2a14188af5f177745075c65.png
[2a8a9b10791546c8a76aefcf7596e7e5.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/04/92a9ac40cfe74df7af249070a02c6691.png
[17d5aa44bd2c456d920bb58e1801e82b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/04/0a7a52ff0ed146c084d56c95350f38d2.png
[b991d95bea79444fbb4e1ea4b0ee595f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/04/76fe94bc0bac4ac49f1498f58f62a192.png
[27879343c1ee4e498836e8f630d4f2cf.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/04/7b15663b71c04fcaa588230d844efef7.png
[ebe4097596e84fb8b08ed2ce02f5400d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/04/68e72f344d0f40db95fe6967278af8e1.png
[58ca6be89ee54b23af65bf3aba96dd14.png]: https://img-blog.csdnimg.cn/58ca6be89ee54b23af65bf3aba96dd14.png
[dc00a92374ae489eadac2ae3a03132fa.png]: https://img-blog.csdnimg.cn/dc00a92374ae489eadac2ae3a03132fa.png
[68ea83ddac7040afa4b6340080174e2c.png]: https://img-blog.csdnimg.cn/68ea83ddac7040afa4b6340080174e2c.png
[84a1b8b529b64a11b86c1aa5f4aa430f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/04/6c12c7bb96654289af08cb13039bc1f6.png
[4a36a30667c14fa68da533e4d344b372.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/04/804534ea00fd4fd2ba7e002146ee9284.png
[40590324321740e88dd960203343da05.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/04/e24df8aa7e75411e8aa8db4e9a0a4741.png
[cee3e2af23c34d6ab21b5b9a35ee53f8.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/04/8a90263cf5c741c98003912fde8b9a79.png
[033_-_1_bilibili]: https://www.bilibili.com/video/BV1E4411H73v?p=33&vd_source=8115f3201b7f98a6c031c0a8d8f38eb0