算法基础08：栈的三种表达式

发表于 2024-07-18 更新于 2024-09-11 分类于算法，基础阅读次数：
本文字数： 6.7k 阅读时长 ≈ 6 分钟

栈的三种表达式为：前缀，中缀，后缀

前缀表达式（波兰表达式）

前缀表达式的计算机求值

中缀表达式

后缀表达式（逆波兰表达式）

后缀表达式的计算机求值

代码完成一个计算器（逆波兰计算器）

package com.algorithm.stack;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * 逆波兰计算器
 *
 * @author：XMD
 * @date: 24.8.22
 */
public class BackPolandCalculatorDemo {

    public static void main(String[] args) {
        //先定义一个逆波兰表达式
        //为了方便，表达式的数组和符号使用空格隔开
        //（30+4）* 5 -6  =>  30 4 + 5 * 6 -
        String expre = "30 4 + 5 * 6 - ";
        /**
         * 思路
         * 1.先将表达式当道ArrayList中
         * 2.将ArrayList传递给一个方法，遍历ArrayList配合栈完成计算
         */
        List<String> listString = getListString(expre);
        System.out.println(listString);
        int calculate = calculate(listString);
        System.out.println(calculate);
    }

    /**
     * 将一个逆波兰表达式，依次将数据和运算符放到ArrayList中
     */
    public static List<String> getListString(String expre) {
        //将表达式分割
        String[] strings = expre.split(" ");
        List<String> stringList = new ArrayList<>();
        for (String string : strings) {
            stringList.add(string);
        }
        return stringList;
    }
    /**
     * 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<String> stringList){
        //创建一个栈，一个即可
        Stack<String> stack = new Stack<>();
        for (String item : stringList) {
            if (item.matches("\\d+")){
                //入栈
                stack.push(item);
            }else {
                //pop出两个数并计算，计算后的数据入栈
                int num2 = Integer.parseInt(stack.pop());
                int num1 = Integer.parseInt(stack.pop());
                int res;
                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(String.valueOf(res));
            }

        }
        return Integer.parseInt(stack.pop());
    }


}

中缀转后缀

大家看到，后缀表达式适合计算式进行运算，但是人却不太容易写出来，尤其是表达式很长的情况下，因此在开发中，我们需要将中缀表达式转成后缀表达式。

具体步骤如下：

初始化两个栈：运算符栈s1和储存中间结果的栈s2；
从左至右扫描中缀表达式；
遇到操作数时，将其压s2；
遇到运算符时，比较其与s1栈顶运算符的优先级：
1. 如果s1为空，或栈顶运算符为左括号“("，则直接将此运算符入栈；
2. 否则，若优先级比栈顶运算符的高，也将运算符压入s1;
3. 否则，将s1栈顶的运算符弹出并压入到s2中，再次转到(4-1)与s1中新的栈顶运算符相比较；
遇到括号时：
1. 如果是左括号“(”，则直接压入s1
2. 如果是右括号“)”，则依次弹出s1栈顶的运算符，并压入s2,直到遇到左括号为止，此时将这一对括号丢弃
重复步骤2至5，直到表达式的最右边
将s1中剩余的运算符依次弹出并压入s2
依次弹出s2中的元素并输出，结果的逆序即为中缀表达式对应的后缀表达式

举例说明：

代码实现

package com.algorithm.stack;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * 逆波兰计算器
 *
 * @author：XMD
 * @date: 24.8.22
 */
public class BackPolandCalculatorDemo {

    public static void main(String[] args) {

        /**
         * 中缀表达式转后缀表达式
         * 1,1+((2+3)*4)-5=>转成1 2 3 + 4 * + 5 -
         * 2,因为直接对str进行操作，不方便，因此先将"1+((2+3)*4)-5”=》中缀的表达式对应的List
         *  即"1+(2+3)*4)-5"=>ArrayList[1,+,(,(,2,+,3,),*,4,)-,5]
         * 3. 将中缀表达式list转为后缀表达式对应的list
         */

        //中缀表达式
        String exp = "1+((2+3)*4)-5";

        List<String> list = toInfixExpList(exp);
        System.out.println(list);
        List<String> list1 = parseSufExpList(list);
        System.out.println(list1);


//        //先定义一个逆波兰表达式
//        //为了方便，表达式的数组和符号使用空格隔开
//        //（30+4）* 5 -6  =>  30 4 + 5 * 6 -
//        String expre = "30 4 + 5 * 6 - ";
//        /**
//         * 思路
//         * 1.先将表达式当道ArrayList中
//         * 2.将ArrayList传递给一个方法，遍历ArrayList配合栈完成计算
//         */
//        List<String> listString = getListString(expre);
//        System.out.println(listString);
        int calculate = calculate(list1);
        System.out.println(calculate);
    }


    public static List<String> parseSufExpList(List<String> list){
        //定义两个栈
        Stack<String> s1 = new Stack<>();//符号栈
        //说明：因为s2这个栈，在整个转换过程中，没有pop操作，而且后面我们还需要逆序输出
        //因此比较麻烦，这里我们就不用Stack<String>直接使用List<String> s2
        List<String> s2 = new ArrayList<>();

        for (String item : list) {
            //如果是数字
            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(s1.peek()) >= Operation.getValue(item)){
                    s2.add(s1.pop());
                }
                //将item压入栈中
                s1.push(item);
            }

        }
        //将s1中剩余的运算符依次弹出并加入s2
        while (s1.size() != 0){
            s2.add(s1.pop());
        }
        return s2;
    }

    public static List<String> toInfixExpList(String str) {
        //存放中缀表达式对应的内容
        List<String> list = new ArrayList<>();
        //指针，用于遍历中缀表达式字符串
        int i = 0;
        String st;
        char c;
        do {
            //如果不是一个数字，加入list
            if ((c = str.charAt(i)) < 48 || (c = str.charAt(i)) > 57) {
                list.add(String.valueOf(c));
                i++;
            } else {
                //如果是数字，需要考虑多位数
                st = "";
                while (i < str.length() && (c = str.charAt(i)) >= 48 && (c = str.charAt(i)) <= 57) {
                    st += c;
                    list.add(st);
                    i++;
                }
            }
        } while (i < str.length());
        return list;
    }


    /**
     * 将一个逆波兰表达式，依次将数据和运算符放到ArrayList中
     */
    public static List<String> getListString(String expre) {
        //将表达式分割
        String[] strings = expre.split(" ");
        List<String> stringList = new ArrayList<>();
        for (String string : strings) {
            stringList.add(string);
        }
        return stringList;
    }

    /**
     * 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<String> stringList) {
        //创建一个栈，一个即可
        Stack<String> stack = new Stack<>();
        for (String item : stringList) {
            if (item.matches("\\d+")) {
                //入栈
                stack.push(item);
            } else {
                //pop出两个数并计算，计算后的数据入栈
                int num2 = Integer.parseInt(stack.pop());
                int num1 = Integer.parseInt(stack.pop());
                int res;
                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(String.valueOf(res));
            }

        }
        return Integer.parseInt(stack.pop());
    }


}

class Operation{
    private static int ADD = 1;
    private static int SUB = 1;
    private static int MUL = 2;
    private static int DIV = 2;

    public static int getValue(String oper){
        int res = 0;
        switch (oper){
            case "+":
                res = ADD;
                break;
            case "-":
                res = SUB;
                break;
            case "*":
                res = MUL;
                break;
            case "/":
                res = DIV;
                break;
            default:
                System.out.println("运算符有误");
                break;
        }
        return res;
    }
}

-------------本文结束感谢您的阅读-------------

本文作者： meadee
本文链接： https://blog.xuemingde.com/posts/2XHCMQG.html
版权声明： 本博客所有文章除特别声明外，均采用 BY-NC-SA 许可协议。转载请注明出处！