数据结构-栈(三)逆波兰计算器(Java)_LySong_的博客-程序员宝宝

技术标签: 算法  stack  java    数据结构  

1.逆波兰表达式

逆波兰表达式又叫做后缀表达式。逆波兰表示法是波兰逻辑学家J・卢卡西维兹(J・ Lukasewicz)于1929年首先提出的一种表达式的表示方法 [1] 。后来,人们就把用这种表示法写出的表达式称作“逆波兰表达式”。逆波兰表达式把运算量写在前面,把算符写在后面。
逆波兰表达式是一种十分有用的表达式,它将复杂表达式转换为可以依靠简单的操作得到计算结果的表达式。例如(a+b)(c+d)转换为ab+cd+

2.逆波兰表达式存在的意义

在我们看来逆波兰表达式阅读起来并不方便,那么它存在的意义是什么呢?

原因就在于这个简单是相对人类的思维结构来说的,对计算机而言中序表达式是非常复杂的结构。相对的,逆波兰式在计算机看来却是比较简单易懂的结构。因为计算机普遍采用的内存结构是栈式结构,它执行先进后出的顺序。

在上篇博客中,我们根据中缀表达式(即我们平时习惯读的多项式顺序)实现了计算器,但是这种实现方式很难实现有括号的多项式,而逆波兰表达式会完美的解决这个问题,中缀表达式转为逆波兰表达式后就不会存在括号了。

3.中缀表达式转后缀表达式

3.1 实现的思路

  1. 初始化两个栈s1,s2

  2. 从左至右扫描表达式

  3. 遇到数字压入s2

  4. 若遇到运算符,比较与栈顶的优先级
    4.1 若s1为空,或栈顶运算符为左括号 “(”,则将运算符压入s1
    4.2 若优先级比栈顶运算符高,也将运算符压入s1
    4.3 否则,将s1栈顶运算符弹出并压入s2,再转到4.1与s1新的栈顶运算符进行比较

  5. 遇到括号时
    5.1 如果为"(",直接压入s1
    5.2 如果为")",则依次弹出s1栈顶运算符,压入s2,直到遇到左括号,此时将这一对括号“丢弃”

  6. 重复2-5步骤直到表达式最右边

  7. 将s1中剩余的运算符依次弹出并压入s2

  8. 依次弹出s2中的元素并输出,将结果逆序,即为后缀表达式
    算法图示:
    在这里插入图片描述

在整个思路中我们发现s2仅仅是进行压栈的操作,并且因为s2栈的特点,最后输出时需要对结果进行逆序输出,所以我们可以使用ArrayList充当s2的数据结构,这样我们就不需要最后进行逆序操作,直接输出即是后缀表达式

4.如何计算后缀表达式

当中缀表达式转为后缀表达式后,我们不用考虑优先级的问题,因为后缀表达式的顺序就是计算顺序,我们只需要按照规则进行计算即可
9. 对后缀表达式从左至右开始扫描
10. 如果遇到数字,进行压栈操作
11. 如果遇到操作符,弹出栈顶两个数(次栈顶在前),用该计算符进行计算,将结果压栈,直到最后。

5.代码实现

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

/**
 * 第一步,首先完成了后缀表达式的计算器
 * 第二步,需要完成中缀表达式转后缀表达式的功能4 * 5 - 8 + 60 + 8 / 2 => 4 5 * 8 - 6 + 8 2 / +
 */
public class PolandNotation {
    
    public static void main(String[] args) {
    
        //先定义一个逆波兰表达式
        //(30+4)*5-6
        // 4 * 5 - 8 + 60 + 8 / 2 => 4 5 * 8 - 6 + 8 2 / +
        String expression = "1+((2+3)*4)-5";
        List<String> infixExpressionList = toInfixExpressionList(expression);
        System.out.println("中缀表达式对应List"+ infixExpressionList);
        List<String> suffixExpresionList = parseSuffixExpresionList(infixExpressionList);
        System.out.println("后缀表达式对应List:"+ suffixExpresionList);
        System.out.printf("Expression=%d", calculate(suffixExpresionList));
//        //1.先将suffixExpression放到ArrayList中
//        //2.将ArrayList传递给一个方法,遍历ArrayList配合栈完成计算器
//        List<String> rpnList = getListString(suffixExpression);
//        System.out.println("rpnList" + rpnList);
//
//        int res = calculate(rpnList);
//        System.out.println("计算的结果是:" + res);
    }


    public static List<String> parseSuffixExpresionList(List<String> list){
    
        //定义两个栈
        Stack<String> s1 = new Stack<>(); //符号栈
        //因为s2在整个转换过程中没有pop操作,而且还需要逆序输出
        //因此我们这里直接使用list进行输出
        List<String> s2 = new ArrayList<String>();
        //遍历list
        for (String item: list) {
    
            //如果是一个数,就入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();//将小括号弹出,消除小括号
            }else {
    
                //考虑到运算符优先级的问题
                //当item的优先级小于或者等于栈顶运算符,弹出s1加入s2,再继续用item与新的栈顶元素作比较
                //缺少比较优先级高低的方法
                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
     * @param s
     * @return
     */
    public static List<String> toInfixExpressionList(String s){
    
        //定义一个list,放中缀表达式
        List<String> list = new ArrayList<String>();
        int i = 0; //这是一个指针,用于遍历中缀表达式字符串
        String str;//对多位数的拼接
        char c;//每遍历一个字符就放到c
        do{
    
            //如果c是一个非数字,就需要加入到ls中
            if((c = s.charAt(i)) < 48 || (c = s.charAt(i)) > 57){
    
                list.add("" + c);
                i++;//i需要后移
            }else{
     //如果是一个数,需要考虑多位数
                str = "";//置空串
                while (i < s.length() && (c=s.charAt(i)) >= 48 && (c=s.charAt(i)) <= 57){
     //对整数的处理
                    str += c;//拼接
                    i++;
                }
                list.add(str);
            }
        }while (i < s.length());
        return list;
    }


    //将一个逆波兰表达式,依次将数据和运算符放入到ArrayList中
    public static List<String> getListString(String suffixExpression){
    
        //分割字符串
        String[] split = suffixExpression.split(" ");
        List<String> list = new ArrayList<String>();
        for (String ele: split) {
    
            list.add(ele); //依次放入字符
        }
        return list;
    }

    //完成逆波兰表达式的运算
    public static int calculate(List<String> ls){
    
        //创建一个栈。只需要一个栈
        Stack<String> stack = new 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 + "");
            }
        }
        //最后留在stack的数据就是结果
        return Integer.parseInt(stack.pop());
    }
}

//增加一个类Operation 返回运算符对应的优先级
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:
                    break;
        }
        return result;
    }

结果:

在这里插入图片描述

欢迎访问我的个人博客

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/weixin_43265151/article/details/104735385

智能推荐

c++ ea 代码 生成_看EA如何生成代码框架_weixin_39916355的博客-程序员宝宝

EA的使用给我们带来了极大的方便,同时,在对EA不断的深入使用过程中,我们也一步步的对其功能有了深层次的了解,这次我学到的新功能,就是通过EA,将类图转换成代码框架,这是如何做到的呢?代码工程设置首先,代码生成是分很多种类别的,为了每次生成代码是都简单方便,我们可以先对一些常规内容进行配置。如,我想将生成的代码设置为C#版的,设置方法:选择“工具”中的“选项”,弹出窗体,继续“代码工程”,设置代码...

有没有亚马逊跨境电商适合用的浏览器排名_候鸟浏览器的博客-程序员宝宝

跨境电商用户最看重的就是浏览器的防关联效果。我以一个用户的角度,大概给大家一个相关防关联浏览器的排名。候鸟浏览器特点:安全、国内最火、亚马逊测评专用、界面简洁易上手这款候鸟浏览器是2021年最新的针对亚马逊测评开发的基于chrome内核的反指纹浏览器,经过我们测试相对起来浏览器来说防关联的安全级别更高。浏览器指纹的修改更彻底,操作起来也比较简单至于怎么使用大家可以去候鸟的官网的帮助页面看一下,个人无限版是499一个月,可以创建无限浏览器环境。可以是适配luminati、911S5等市面上常见的代理,经

Diffie-Hellman算法详细讲解 及用java实现一个基于密钥协商的socket通信_太菜了怎么办?的博客-程序员宝宝_diffiehellman算法实例

diffie-Hellman(DH)算法原理Diffie-Hellman算法是Whitefield Diffie和Martin Hellman在1976年公布的一种秘钥交换算法,它是一种建立秘钥的方法,而不是加密方法,所以秘钥必须和其他一种加密算法结合使用。这种秘钥交换技术的目的在于使两个用户安全的交换一个秘钥一遍后面的报文加密。Diffie-Hellman密钥交换算法的有效性依赖于计算离散对数的难度。模型分析1)由消息发送的一方构建密钥,这里由甲方构建密钥。2)由构建密钥的一方向对方公布其公钥

SQlite源码分析-体系结构_diaoju3333的博客-程序员宝宝

体系结构在内部,SQLite由以下几个组件组成:内核、SQL编译器、后端以及附件。SQLite通过利用虚拟机和虚拟数据库引擎(VDBE),使调试、修改和扩展SQLite的内核变得更加方便。所有SQL语句都被编译成易读的、可以在SQLite虚拟机中执行的程序集。SQLite支持大小高达2 TB的数据库,每个数据库完全存储在单个磁盘文件中。这些磁盘文件可以在不同字节顺序的计算机...

C# 获取程序当前文件夹_liehuo123的博客-程序员宝宝_c# 获取当前文件夹

Application.StartupPath     //如何获取当前进程所属程序的文件夹位置   (窗体中使用)( label16.Text=Application.StartupPath;)  Environment.SystemDirectory;         //获取系统目录      Environment.CurrentDirectory;       //获取当

sequence系列之sequence和sequencer_Iam柒年的博客-程序员宝宝_sequence和sequencer

sequence和item发送实例未封装实例如下:class bus_trans extends uvm_sequence_item; //bus item定义 rand int data; `uvm_object_utils_begin(bus_trans) `uvm_field_int(data, UVM_ALL_ON) `uvm_object_utils_end ...endclassclass child_seq extends uvm_sequence; //child_

随便推点

PAT——A1085 Perfect Sequence(two pointer)_ZMST的博客-程序员宝宝

题目链接:#include&amp;lt;bits/stdc++.h&amp;gt;using namespace std;int a[100010];int main(){ int n,p; scanf(&quot;%d%d&quot;,&amp;amp;n,&amp;amp;p); for(int i=0;i&amp;lt;n;i++) { scanf(&quot;%d&quot;,&amp;amp;a[i]); ...

数据库MySQL的各种锁以及数据库索引[email protected]@的博客-程序员宝宝

以下这几个链接总结的不错,我先存着留个记录,以后有时间再总结深入理解数据库行锁与表锁细谈数据库表锁和行锁数据库索引部分,我看了看一个B站视频链接,也还没总结~B站数据库索引...

柳神跟我说话了_GuoMengKai的博客-程序员宝宝

开心啊啊啊啊啊啊啊啊啊啊。

最简单的Jsp环境配置及数据库连接调试(Jdk7+Tomcat7+Mysql5.5)_infocarrier的博客-程序员宝宝

这是我看到的最简单的Jsp环境配置,用上述软件版本,傻瓜式安装就是了,根本不用手动设置环境变量什么的。注意:利用下文中的first.jsp例子时,有两点要注意,一是把中文的双引号替换为英文的,在macromedia中很容易看出来,有很多个;二是,数据库的用户名和密码要替换为你自己的。文章出处:http://aircraftinteriorschina.com/archiver/?tid

第二弹!谷歌大脑2017总结下篇:Jeff Dean梳理6大领域研究_RubyBoss的博客-程序员宝宝

https://blog.csdn.net/yH0VLDe8VG8ep9VGe/article/details/79055122量子位 出品 | 公众号 QbitAI传奇一般的Jeff Dean今天发布了谷歌大脑2017总结的第二弹。在这篇总结中,Jeff Dean详细论述了谷歌大脑过去一年的AI应用研究,例如如何将机器学习等技术应用于医疗、机器人、创意、公平等等多个领域。这在...

随机森林算法学习(RandomForest)_木鱼&金鱼的博客-程序员宝宝

随机森林算法学习最近在做kaggle的时候,发现随机森林这个算法在分类问题上效果十分的好,大多数情况下效果远要比svm,log回归,knn等算法效果好。因此想琢磨琢磨这个算法的原理。要学随机森林,首先先简单介绍一下集成学习方法和决策树算法。下文仅对该两种方法做简单介绍(具体学习推荐看统计学习方法的第5章和第8章)。Bagging和Boosting的概念与区别该部分主要学习自:http://www....

推荐文章

热门文章

相关标签