JAVA数据结构与算法之栈（四）~ 中缀表达式转换为后缀表达式

标签：equals   注意   static   逆序输出   入栈   步骤   数字   说明   有限公司   

中缀表达式转换为后缀表达式

中缀表达式转后缀表达式思路：

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

举例：

将中缀表达式“1+((2+3)×4)-5”转换为后缀表达式的过程如下：
因此结果为 :"1 2 3 + 4 × + 5 –"

代码演示：

/**
 * Copyright (C), 2015-2020, XXX有限公司
 * FileName: dddd
 * Author:   Administrator
 * Date:     2020/4/25 15:41
 * Description:
 * History:
 *           
 * 作者姓名           修改时间           版本号              描述
 */
package com.pierce.algorithm;

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

public class PolandNotation2 {
    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
        // 即 ArrayList [1,+,(,(,2,+,3,),*,4,),-,5] =》 ArrayList [1,2,3,+,4,*,+,5,–]
        String expression = "1+((2+3)*4)-5";
        List infixExpressionList = toInfixExpressionList(expression);
        //ArrayList [1,+,(,(,2,+,3,),*,4,),-,5]
        System.out.println("中缀表达式对应的 List=" + infixExpressionList);
        List suffixExpreesionList = parseSuffixExpreesionList(infixExpressionList);
        //ArrayList [1,2,3,+,4,*,+,5,–]
        System.out.println("后缀表达式对应的 List" + suffixExpreesionList);
        System.out.printf("expression=%d", calculate(suffixExpreesionList));
        /*
        //先定义给逆波兰表达式
        //(30+4)×5-6 => 30 4 + 5 × 6 - => 164
        // 4 * 5 - 8 + 60 + 8 / 2 => 4 5 * 8 - 60 + 8 2 / +
        //测试
        //说明为了方便，逆波兰表达式 的数字和符号使用空格隔开
        //String suffixExpression = "30 4 + 5 * 6 -";
        String suffixExpression = "4 5 * 8 - 60 + 8 2 / +"; // 76
        //思路
        //1. 先将 "3 4 + 5 × 6 - " => 放到 ArrayList 中
        尚硅谷 Java 数据结构和算法
        更多 Java –大数据 –前端 –python 人工智能 -区块链资料下载，可访问百度：尚硅谷官网
        第 85页
        //2. 将 ArrayList 传递给一个方法，遍历 ArrayList 配合栈 完成计算
        List list = getListString(suffixExpression);
        System.out.println("rpnList=" + list);
        int res = calculate(list);
        System.out.println("计算的结果是=" + res);
        */
    }
    //即 ArrayList [1,+,(,(,2,+,3,),*,4,),-,5] =》 ArrayList [1,2,3,+,4,*,+,5,–]
    //方法：将得到的中缀表达式对应的 List => 后缀表达式对应的 List
    public static List parseSuffixExpreesionList(List ls) {
        //定义两个栈
        Stack s1 = new Stack(); // 符号栈
        //说明：因为 s2 这个栈，在整个转换过程中，没有 pop 操作，而且后面我们还需要逆序输出
        //因此比较麻烦，这里我们就不用 Stack 直接使用 List s2
        //Stack s2 = new Stack(); // 储存中间结果的栈 s2
        List s2 = new ArrayList(); // 储存中间结果的 Lists2
        //遍历 ls
        for(String item: ls) {
            //如果是一个数，加入 s2
            if(item.matches("\\d+")) {
                s2.add(item);
            } else if (item.equals("(")) {
                s1.push(item);
            } else if (item.equals(")")) {
                //如果是右括号“)”，则依次弹出 s1 栈顶的运算符，并压入 s2，直到遇到左括号为止，此时将这一对括号丢弃
                while(!s1.peek().equals("(")) {
                    s2.add(s1.pop());
                }
                s1.pop();//!!! 将 ( 弹出 s1 栈， 消除小括号
            } 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; //注意因为是存放到 List, 因此按顺序输出就是对应的后缀表达式对应的 List
    }
    //方法：将 中缀表达式转成对应的 List
    // s="1+((2+3)×4)-5";
    public static List toInfixExpressionList(String s) {
        //定义一个 List,存放中缀表达式 对应的内容
        List ls = new ArrayList();
        int i = 0; //这时是一个指针，用于遍历 中缀表达式字符串
        String str; // 对多位数的拼接
        char c; // 每遍历到一个字符，就放入到 c
        do {
            //如果 c 是一个非数字，我需要加入到 ls
            if((c=s.charAt(i))  57) {
                ls.add("" + c);
                //i 需要后移
                i++;
                //如果是一个数，需要考虑多位数
            } else {
                //先将 str 置成"" ‘0‘[48]->‘9‘[57]
                str = "";
                while(i = 48 && (c=s.charAt(i))  getListString(String suffixExpression) {
        //将 suffixExpression 分割
        String[] split = suffixExpression.split(" ");
        List list = new ArrayList();
        for(String ele: split) {
            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 ls) {
        // 创建给栈, 只需要一个栈即可
        Stack stack = new Stack();
        // 遍历 ls
        calculateNumber(ls, stack);
        //最后留在 stack 中的数据是运算结果
        return Integer.parseInt(stack.pop());
    }

    static void calculateNumber(List ls, Stack stack) {
        for (String item : ls) {
            // 这里使用正则表达式来取出数
            if (item.matches("\\d+")) {
                // 入栈
                stack.push(item);
            } else {
                // pop 出两个数，并运算， 再入栈
                int num2 = Integer.parseInt(stack.pop());
                int num1 = Integer.parseInt(stack.pop());
                int res = 0;
                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("" + res);
            }
        }
    }
}

JAVA数据结构与算法之栈（四）~ 中缀表达式转换为后缀表达式

标签：equals   注意   static   逆序输出   入栈   步骤   数字   说明   有限公司   

原文地址：https://www.cnblogs.com/pierceming/p/12773378.html