栈的简单应用（利用Stack进行四则混合运算）（JAVA）

喜欢ヅ旅行 2023-10-16 12:57 51阅读 0赞

**目录**

中缀表达式转后缀表达式

图解

代码实现过程：

完整代码：

利用后缀表达式求值：

完整代码：

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

首先我们得先了解**逆波兰表达式**。

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

所谓的**中缀表达式**其实就是我们平时写的例如：![3+4\\times (2+ 2)+2\\div 2][3_4_times _2_ 2_2_div 2]；而它的**后缀表达式（也成为逆波兰表达式）**为 ![3\\; 4\\; 2\\; 2+ \\times + 2\\; 2 \\;\\div +][3_ 4_ 2_ 2_ _times _ 2_ 2 _div]；

**后缀表达式：**指的是**不包含括号**，**运算符放在**两个**运算对象的后面**，所有的计算按运算符出现的顺序，严格**从左向右进行**（**不再考虑运算符的优先规则**）。

我们如果要利用程序来**进行四则混合运算最重要的**就是将输入的**中缀表达式转后缀表达式**。

首先我们假设**运算符中只有 加 减 乘 除 和 括号**不然的话程序太复杂了（其实是我不会写【哭】）。

### 图解 ###

![4bc7c0f54e18405ea5be1b957b049498.png][]

### 代码实现过程： ###

首先我们先写一个**方法 返回值是动态字符串数组**（为了后面好计算），**形参为字符串类型**（因为输入值不只有数字还有运算符）。这里会用到栈所以也定义一个栈。

public ArrayList<String> midChangeEng(String str) {
            //这里用动态数组就不用担心不够用
            ArrayList<String> ret = new ArrayList<String>();
            Stack<Character> stack = new Stack<>();
        }

此时再创建一个新方法用来**判断传入字符是不是运算符**

public boolean isOperator(char s) {
            if (s == '+' || s == '-' || s == '*' || s == '/' || s == '(' || s == ')') {
                return true;
            }
            return false;
        }

我们再利用**运算符再ASCII码中的位置，**创建一个数组用来**表示它们的优先级**

![e3e9a37ed1084cde972afa336d690c23.png][]![2883ae7102e7433c9f20e6336012a115.png][]

int[] able = {1,0,0,0,0,1};//分别代表 * + (null) - (null) / 的优先级

利用循环遍历字符串

//遍历字符串
            for (int i = 0; i < str.length(); i++) {
                char a = str.charAt(i);
                String tmp = "";//用来暂时存储出栈的数字
                if (isOperator(a)) {
                    //是操作数
                }else{
                    //如果是数字就放到ret中
                }
            }
    
            return ret;

对操作数的操作 ，可是此段代码中重复代码过多，所以可以将其封装成一个方法。

if (isOperator(a)) {
                    //是操作数
                    switch (a) {
                        case '+'://判断如果优先级不大于栈顶的元素那么就先出栈在入栈
                            if(!stack.isEmpty()) {//出栈
                                while(!stack.isEmpty() && stack.peek() != '(' && able[(int)stack.peek() - 42] >= able[(int)a-42]) {
                                    String b = "";
                                    b += stack.pop();
                                    ret.add(b);
                                }
                            }
                            stack.push(a);
                            break;
                        case '-':
                            if(!stack.isEmpty()) {//出栈
                                while(!stack.isEmpty() && stack.peek() != '(' && able[(int)stack.peek() - 42] >= able[(int)a-42]) {
                                    String b = "";
                                    b += stack.pop();
                                    ret.add(b);
                                }
                            }
                            stack.push(a);
                            break;
                        case '*':
                            if(!stack.isEmpty()) {//出栈
                                while(!stack.isEmpty() && stack.peek() != '(' && able[(int)stack.peek() - 42] >= able[(int)a-42]) {
                                    String b = "";
                                    b += stack.pop();
                                    ret.add(b);
                                }
                            }
                            stack.push(a);
                            break;
                        case '/':
                            if(!stack.isEmpty()) {//出栈
                                while(!stack.isEmpty() && stack.peek() != '(' && able[(int)stack.peek() - 42] >= able[(int)a-42]) {
                                    String b = "";
                                    b += stack.pop();
                                    ret.add(b);
                                }
                            }
                            stack.push(a);
                            break;
                        case '(':
                            stack.push(a);
                            break;
                        case ')':
                            while(!stack.isEmpty() && stack.peek() != '(') {
                                String b = "";
                                b += stack.pop();
                                ret.add(b);
                            }
                            stack.pop();//删除‘(’
                            break;
                    }
    
                }

如果是数字就进行以下操作

else{
                    //如果是数字就放到ret中
                    String tmp = "";
                    while(i < str.length() && !isOperator(str.charAt(i))) {//数字有可能是多位的
                        tmp += str.charAt(i);
                        i++;
                    }
                    i--;
                    ret.add(tmp);
                }

再出函数之前要先将栈里面的全部导出来

//将栈里面剩余的全部出栈
            while(!stack.isEmpty()) {
                String b = "";
                b += stack.pop();
                ret.add(b);
            }
            return ret;

## 完整代码： ##

public static ArrayList<String> midChangeEng(String str) {
            //这里用动态数组就不用担心不够用
            ArrayList<String> ret = new ArrayList<String>();
            Stack<Character> stack = new Stack<>();
    
            int[] able = {1,0,0,0,0,1};//分别代表 * + (null) - (null) / 的优先级
            //遍历字符串
            for (int i = 0; i < str.length(); i++) {
                char a = str.charAt(i);
    
                if (isOperator(a)) {
                    //是操作数
                    switch (a) {
                        case '+'://判断如果优先级不大于栈顶的元素那么就先出栈在入栈
                            abcd(ret, stack, able, a);
                            break;
                        case '-':
                            abcd(ret, stack, able, a);
                            break;
                        case '*':
                            abcd(ret, stack, able, a);
                            break;
                        case '/':
                            abcd(ret, stack, able, a);
                            break;
                        case '(':
                            stack.push(a);
                            break;
                        case ')':
                            while(!stack.isEmpty() && stack.peek() != '(') {
                                String b = "";
                                b += stack.pop();
                                ret.add(b);
                            }
                            stack.pop();//删除‘(’
                            break;
                    }
                }else{
                    //如果是数字就放到ret中
                    String tmp = "";
                    while(i < str.length() && !isOperator(str.charAt(i))) {//数字有可能是多位的
                        tmp += str.charAt(i);
                        i++;
                    }
                    i--;
                    ret.add(tmp);
                }
            }
            //将栈里面剩余的全部出栈
            while(!stack.isEmpty()) {
                String b = "";
                b += stack.pop();
                ret.add(b);
            }
            return ret;
        }

![f25e330769294c75b7e61f5183bea3ab.png][]![f8dddd435cb54d08afb0d74ccf97c1e3.png][]

## 利用后缀表达式求值： ##

这部分**比较简单**所以就直接展示了

![7360e16b7aba472690dae509a1c47b07.png][]

## 完整代码： ##

public int evalRPN(String[] tokens) {
                Stack<Integer> stack = new Stack<>();
                for (int i = 0; i < tokens.length; i++) {
                    if (isOperator(tokens[i])) {
                        int num2 = stack.pop();
                        int num1 = stack.pop();
                        switch(tokens[i].charAt(0)) {
                            case '+':
                                stack.push(num1 + num2);
                                break;
                            case '-':
                                stack.push(num1 - num2);
                                break;
                            case '*':
                                stack.push(num1 * num2);
                                break;
                            case '/':
                                stack.push(num1 / num2);
                                break;
                        }
                    }else {
                        stack.push(Integer.parseInt(tokens[i]));
                    }
                }
                return stack.pop();
            }
    
    
            public boolean isOperator(String str) {
                if (str.length() != 1) {
                    return false;
                }
                if (str.charAt(0) == '+' || str.charAt(0) == '-' || str.charAt(0) == '*' || str.charAt(0) == '/') {
                    return true;
                }
                return false;
            }

[3_4_times _2_ 2_2_div 2]: https://latex.csdn.net/eq?3&plus;4%5Ctimes%20%282&plus;%202%29&plus;2%5Cdiv%202
[3_ 4_ 2_ 2_ _times _ 2_ 2 _div]: https://latex.csdn.net/eq?3%5C%3B%204%5C%3B%202%5C%3B%202&plus;%20%5Ctimes%20&plus;%202%5C%3B%202%20%5C%3B%5Cdiv%20&plus;
[4bc7c0f54e18405ea5be1b957b049498.png]: https://img-blog.csdnimg.cn/4bc7c0f54e18405ea5be1b957b049498.png
[e3e9a37ed1084cde972afa336d690c23.png]: https://img-blog.csdnimg.cn/e3e9a37ed1084cde972afa336d690c23.png
[2883ae7102e7433c9f20e6336012a115.png]: https://img-blog.csdnimg.cn/2883ae7102e7433c9f20e6336012a115.png
[f25e330769294c75b7e61f5183bea3ab.png]: https://img-blog.csdnimg.cn/f25e330769294c75b7e61f5183bea3ab.png
[f8dddd435cb54d08afb0d74ccf97c1e3.png]: https://img-blog.csdnimg.cn/f8dddd435cb54d08afb0d74ccf97c1e3.png
[7360e16b7aba472690dae509a1c47b07.png]: https://img-blog.csdnimg.cn/7360e16b7aba472690dae509a1c47b07.png