数据结构与算法学习八：前缀（波兰）表达式、中缀表达式、后缀（逆波兰）表达式的学习，中缀转后缀的两个方法，逆波兰计算器的实现-阿里云开发者社区

前言

一、前缀(波兰)表达式学习

1.1 前缀表达式介绍

前缀表达式又称波兰式，前缀表达式的运算符位于操作数之前
举例说明： (3+4)×5-6 对应的前缀表达式就是 - × + 3 4 5 6

1.2 前缀表达式的计算机求值

求值规则：
从右至左扫描表达式，遇到数字时，将数字压入堆栈，遇到运算符时，弹出栈顶的两个数，用运算符对它们做相应的计算（栈顶元素和次顶元素，栈顶操作次栈顶），并将结果入栈； 重复上述过程直到表达式最左端，最后运算得出的值即为表达式的结果
例如 : (3+4)×5-6 对应的前缀表达式就是 - × + 3 4 5 6 , 针对前缀表达式求值步骤如下:

从 右至左扫描 ，将6、5、4、3压入堆栈
遇到+运算符，因此弹出3和4（3为栈顶元素，4为次顶元素），计算出3+4的值，得7，再将7入栈
接下来是×运算符，因此弹出7和5，计算出7×5=35，将35入栈
最后是-运算符，计算出35-6的值，即29，由此得出最终结果；

1.3 后话

前缀表达式的计算方式是从右往左扫描，不符合我们的计算习惯，所以这里我们了解即可。
重点是后面的中缀表达式和后缀表达式。

二、中缀表达式学习

中缀表达式就是 常见的运算表达式 ，如(3+4)×5-6
中缀表达式的求值是我们人最熟悉的，但是对计算机来说却不好操作(前面我们讲的案例就能看的这个问题)，因此，在计算结果时，往往会将中缀表达式转成其它表达式来操作(一般转成后缀表达式.)

三、后缀(逆波兰)表达式学习

3.1 后缀表达式介绍

后缀表达式又称 逆波兰表达式 ,与前缀表达式相似，只是运算符位于操作数之后
举例说明： (3+4)×5-6 对应的后缀表达式就是 3 4 + 5 × 6 –
再比如：

3.2 后缀表达式的计算机求值

求值规则：
从左至右 扫描表达式，遇到数字时，将数字压入堆栈，遇到运算符时，弹出栈顶的两个数，用运算符对它们做相应的计算（次顶元素和栈顶元素，次栈顶操作栈顶），并将结果入栈；重复上述过程直到表达式最右端，最后运算得出的值即为表达式的结果
例如: (3+4)×5-6 对应的后缀表达式就是 3 4 + 5 × 6 - , 针对后缀表达式求值步骤如下:

从左至右扫描，将3和4压入堆栈；
遇到+运算符，因此弹出4和3（4为栈顶元素，3为次顶元素），计算出3+4的值，得7，再将7入栈；
将5入栈；
接下来是×运算符，因此弹出5和7，计算出7×5=35，将35入栈；
将6入栈；
最后是-运算符，计算出35-6的值，即29，由此得出最终结果;

3.3 构成方法

给定一个后缀表达式字符串，对其进行计算。
思路：

先将后缀表达式字符串存储到 list 集合中。也就是将字符串的数字和运算符放到ArrayList中，写成方法一。
按照3.2 的思路，遍历1中的ArrayList 中的字符串，对其进行计算。写成方法二

3.3.1 PolandNotation类

package com.feng.ch07_polandnotation;

import javax.management.relation.RoleUnresolved;
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class PolandNotation {
    public static void main(String[] args) {
        /*
        * 先定义逆波兰表达式
        * （3+4）x5-6 => 3 4 + 5 x 6 - == 29
        * 4 * 5 - 8 + 60 + 8 / 2 => 4 5 * 8 - 60 + 8 2 / + ==76
        * 说明为了方便，逆波兰表达式的数字和符号使用空格隔开
        *
        * */
//        String suffixExpression = "3 4 + 5 * 6 -";  //29
        String suffixExpression = "4 5 * 8 - 60 + 8 2 / +"; //76
        /*
         * 思路：
         * 1、现将 "3 4 5 + 5 x 6 -" =》 放到 ArrayList 中
         * 2、将 ArrayList 传递给一个方法，遍历 ArrayList 配合栈完成计算
         * */
        List<String> listString = getListString(suffixExpression);
        System.out.println("spnList:" + listString);

        int res = calculate(listString);
        //System.out.println("（3+4）x5-6="+res); //29
        System.out.println("4 * 5 - 8 + 60 + 8 / 2 ="+res); //76
    }

    /*
     * 将一个逆波兰表达式，依次将数据和运算符 放到 ArrayList 中
     * */
    public static List<String> getListString(String suffixExpression) {
        String[] splits = suffixExpression.split(" ");
        List<String> list = new ArrayList<>();

        for (String ele : splits) {
            list.add(ele);
        }
        return list;
    }

    /*
     * 计算后缀表达式的值
     * 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> list) {
        Stack<String> stack = new Stack<>();

        for (String item : list) {
            // 使用正则表达式 匹配是否为多位数
            if (item.matches("\\d+")) { //匹配多位数
                // 入栈
                stack.push(item);
            } else { // 为符号
                int num1 = Integer.parseInt(stack.pop());
                int num2 = Integer.parseInt(stack.pop());
                int res = 0;
                if ("+".equals(item)) {
                    res = num2 + num1;
                } else if ("-".equals(item)) {
                    res = num2 - num1;
                } else if ("*".equals(item)) {
                    res = num2 * num1;
                } else if ("/".equals(item)) {
                    res = num2 / num1;
                } else {
                    throw new RuntimeException("运算符有误");
                }
                // 计算后，得到数据，放到栈中
                stack.push("" + res);  // 整型转变为 字符串 最快的方式
            }
        }
        return Integer.parseInt(stack.pop());
    }
}

3.3.2 测试结果

在这里插入图片描述

3.4 后话

这里仅仅是介绍了对逆波兰表达式的计算方法，这个方法相对来说思路和编码是比较简单的。
对于中缀表达式转逆波兰表达式就在下面介绍，没有先讲，是因为着实有点困难。

四、中缀表达式转后缀表达式

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

4.1 方法一【超级简单，用于做题】

举个例子，一个式子：（拿下面的例题，便于对比）

1+((2+3)×4)-5

如何把该式子转换成后缀表达式呢？其实就是分三步：

1、按运算符优先级对所有运算符和它的运算数加括号，（原本的括号不用加）
2、把运算符移到 对应的括号 后
3、去掉括号

具体实现为：

1、（（1+（（2+3）x4））-5）
2、（（1（（2 3）+ 4）x）+5）-
3、1 2 3 + 4 x + 5 -

4.2 方法二代码实现中缀转后缀

4.2.1 思路分析

具体思路分析如下：

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

总结：

最后所有的数据都存放在 s2 栈中。
s2栈没有使用pop() 方法进行出栈，所以可用 ArrayList 链表代替，后面代码使用。

4.2.2 举例说明

将中缀表达式 “1+((2+3)×4)-5” 转换为后缀表达式的过程如下

因此结果为 “1 2 3 + 4 × + 5 –”

在这里插入图片描述

4.2.3 代码实现

前面思路的截图：
在这里插入图片描述
此类中包括了上面的计算后缀表达式的方法和测试方法，
中缀转后缀分为两步：

第一步就是将中缀表达式字符串中的数字和运算符单独存放到 ArrayList 中。其方法为：toInfixExpressionList(String s)
遍历ArrayList 中的元素，进行分析，分析的条件如 4.2.1 所示，其方法为：parseSuffixExpressionList(List<String> list)

package com.feng.ch07_polandnotation;

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

/*
 * 中缀表达式 转 后缀表达式 再到 计算结果的流程
 * 1、中缀表达式字符串 放到 list 集合中
 * 2、中缀表达式集合 =》 后缀表达式集合
 * 3、后缀表达式集合 => 进行计算，得出结果
 * */
public class PolandNotation{
    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]
         * */
        String expression = "1+((2+3)*4)-5";
        List<String> strlist = toInfixExpressionList(expression);
        System.out.println("中缀表达式 转 ArrayList集合：" + strlist); //[1, +, (, (, 2, +, 3, ), ×, 4, ), -, 5]
        System.out.println();

        List<String> suffixExpressionList = parseSuffixExpressionList(strlist);
        System.out.println("中缀表达式 转 后缀表达式：" + suffixExpressionList);
        System.out.println();

        int calculate = calculate(suffixExpressionList);
        System.out.println("后缀表达式 的计算结果：" + calculate);
        System.out.println();

        /*
         * 先定义逆波兰表达式
         * （3+4）x5-6 => 3 4 + 5 x 6 - == 29
         * 4 * 5 - 8 + 60 + 8 / 2 => 4 5 * 8 - 60 + 8 2 / + ==76
         * 说明为了方便，逆波兰表达式的数字和符号使用空格隔开
         *
         * */
//        String suffixExpression = "3 4 + 5 * 6 -";  //29
//        String suffixExpression = "4 5 * 8 - 60 + 8 2 / +";
        /*
         * 思路：
         * 1、现将 "3 4 5 + 5 x 6 -" =》 放到 ArrayList 中
         * 2、将 ArrayList 传递给一个方法，遍历 ArrayList 配合栈完成计算
         * */
//        List<String> listString = getListString(suffixExpression);
//        System.out.println("spnList:" + listString);

//        int res = calculate(listString);
        //System.out.println("（3+4）x5-6="+res); //29
//        System.out.println("4 * 5 - 8 + 60 + 8 / 2 =" + res);
    }

    /*
     * 方法：将中缀表达式  转成 对应的 list
     * s =  "1+((2+3)×4)-5"
     * */
    public static List<String> toInfixExpressionList(String s) {
        //定义一个List ，存放中缀表达式 对应的内容
        List<String> list = new ArrayList<>();
        int i = 0; // 这是一个指针，用于遍历 中缀表达式字符串
        String str; // 对多位数的拼接
        char c; //每遍历到一个字符，就放入c

        do {
            c = s.charAt(i);
            if ((c = s.charAt(i)) < 48 || (c = s.charAt(i)) > 57) {  // 为非数字： + - * / （  ）
                list.add("" + c);
                i++; // i需要后移
            } else { // 如果是一个数，需要考虑多位数
                str = ""; // 现将str 置成 ""，'0'[48]->'9'[57]
                while (i < s.length() && (c = s.charAt(i)) >= 48 && c <= 57) {
                    str += c;
                    i++;
                }
                list.add(str);
            }
        } while (i < s.length());
        return list;
    }

    /*
     * 方法： 将中缀表达式对应的 list =》 后缀表达式
     * 即 ArrayList [1, +, (, (, 2, +, 3, ), ×, 4, ), -, 5] =》 ArrayList [1,2,3,+,4,*,+,5,–]
     * */
    public static List<String> parseSuffixExpressionList(List<String> list) {
        /*
         * 定义两个栈说明：因为 S2 这个栈，在整个转换过程中，没有pop操作，而且后面我们还需要逆序输出 因此比较麻烦，这里我们就不用 Stack<String>
         * 直接使用 List<String> s2 Stack<String> s2 = new Stack<String>(); // 储存中间结果的栈s2
         * */
        Stack<String> s1 = new Stack<String>(); // 符号栈
        List<String> s2 = new ArrayList<String>(); // 储存中间结果的Lists2

        for (String item : list) {
            // 如果是数字，直接入s2
            if (item.matches("\\d+")) {
                s2.add(item);
            } else if ("(".equals(item)) {
                // 如果是左括号， 直接入s2
                s1.add(item);
            } else if (")".equals(item)) {
                // 如果是 右括号， 则依次弹出 s1 栈顶的运算符，并压入s2，直到遇到左括号为止， 此时将这一对括号丢弃
                while (!s1.peek().equals("(")) {
                    s2.add(s1.pop());
                }
                //遇到左括号时，将 ( 弹出 s1栈， 消除小左括号
                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);
            }
        }
        /*
         * 当 list 集合中 遍历完后
         * 如果 s1 中有值，将s1中剩余的运算符依次弹出并加入s2
         * */
        while (s1.size() != 0) {
            s2.add(s1.pop());
        }
        //注意因为是存放到List, 因此按顺序输出就是对应的后缀表达式对应的List
        return s2;
    }

    /*
     * 将一个后缀表达式（逆波兰表达式），依次将数据和运算符 放到 ArrayList 中
     * */
    public static List<String> getListString(String suffixExpression) {
        String[] splits = suffixExpression.split(" ");
        List<String> list = new ArrayList<>();

        for (String ele : splits) {
            list.add(ele);
        }
        return list;
    }

    /*
     * 计算后缀表达式的值
     * 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> list) {
        Stack<String> stack = new Stack<>();

        for (String item : list) {
            // 使用正则表达式 匹配是否为多位数
            if (item.matches("\\d+")) { //匹配多位数
                // 入栈
                stack.push(item);
            } else { // 为符号
                int num1 = Integer.parseInt(stack.pop());
                int num2 = Integer.parseInt(stack.pop());
                int res = 0;
                if ("+".equals(item)) {
                    res = num2 + num1;
                } else if ("-".equals(item)) {
                    res = num2 - num1;
                } else if ("*".equals(item)) {
                    res = num2 * num1;
                } else if ("/".equals(item)) {
                    res = num2 / num1;
                } else {
                    throw new RuntimeException("运算符有误");
                }
                // 计算后，得到数据，放到栈中
                stack.push("" + res);  // 整型转变为 字符串 最快的方式
            }
        }
        return Integer.parseInt(stack.pop());
    }
}

Operation.java 类：判断优先级的类

package com.feng.ch07_polandnotation;

/**
 * 编写一个类 Operation 可以返回一个运算符 对应的优先级
 *
 * @author 89796
 */
public 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 operation) {
        int result = 0;
        switch (operation) {
            case "+":
                result = ADD;
                break;
            case "-":
                result = SUB;
                break;
            case "*":
                result = MUL;
                break;
            case "/":
                result = DIV;
                break;
            default:
                System.out.println("不存在该运算符" + operation);
                break;
        }
        return result;
    }
}

4.2.4 测试结果

在这里插入图片描述

数据结构与算法学习八：前缀（波兰）表达式、中缀表达式、后缀（逆波兰）表达式的学习，中缀转后缀的两个方法，逆波兰计算器的实现

前言

一、前缀(波兰)表达式学习

1.1 前缀表达式介绍

1.2 前缀表达式的计算机求值

1.3 后话

二、中缀表达式学习

三、后缀(逆波兰)表达式学习

3.1 后缀表达式介绍

3.2 后缀表达式的计算机求值

3.3 构成方法

3.3.1 PolandNotation类

3.3.2 测试结果

3.4 后话

四、中缀表达式转后缀表达式

4.1 方法一【超级简单，用于做题】

4.2 方法二代码实现中缀转后缀

4.2.1 思路分析

4.2.2 举例说明

4.2.3 代码实现

4.2.4 测试结果

热门文章

最新文章

相关电子书

数据结构与算法学习八：前缀（波兰）表达式、中缀表达式、后缀（逆波兰）表达式的学习，中缀转后缀的两个方法，逆波兰计算器的实现

前言

一、前缀(波兰)表达式学习

1.1 前缀表达式介绍

1.2 前缀表达式的计算机求值

1.3 后话

二、中缀表达式学习

三、后缀(逆波兰)表达式学习

3.1 后缀表达式介绍

3.2 后缀表达式的计算机求值

3.3 构成方法

3.3.1 PolandNotation类

3.3.2 测试结果

3.4 后话

四、中缀表达式 转 后缀表达式

4.1 方法一【超级简单，用于做题】

4.2 方法二 代码实现中缀转后缀

4.2.1 思路分析

4.2.2 举例说明

4.2.3 代码实现

4.2.4 测试结果

热门文章

最新文章

相关电子书

四、中缀表达式转后缀表达式

4.2 方法二代码实现中缀转后缀