栈-综合应用-中缀表达式转后缀表达式

标签: 计算机基础  # 数据结构与算法

综合应用

使用栈完成一个计算表达式的结果

输入:2 * 3 - 4 / 5 * 0.2 => 0.08

思路

  1. 使用index -> 2 (第一个为止),数字放入数栈,符号放入符号栈,符号栈为空,直接放入。

  1. 遇到第二个运算符,与符号栈中的符号进行运算符优先级比较。

    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-gvhtZGbo-1601271684334)(C:\Users\how浩\AppData\Roaming\Typora\typora-user-images\image-20200925111655503.png)]

    • 第二个优先级小于等于第一个运算符,则计算绿色框中表达式的结果;

      1. 运算结果存入栈;
      2. 将第二个运算符存入栈;
    • 第二个优先级大于第一个运算符,直接进行数值运算,结果保存到数栈中;

为什么使用栈这个数据结构?

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-IXSde0V7-1601271684338)(C:\Users\how浩\AppData\Roaming\Typora\typora-user-images\image-20200925111845440.png)]

整个运算下来,“-”最先入“容器”,因为优先级不够的问题最后才出“容器”参与运算,刚好符号栈这个数据结构。

代码实现

function calculator(expression) {
    expression = expression.replace(/ +/g, "");

    let expressionArr = expression.match(/(\d+|[*\-+/%]+)/g);
    console.log(expressionArr);
    let numStack = new StackArray();
    let signStack = new StackArray();

    let signsValue = {"-": 1, "+": 1, "*": 2, "/": 2, "%": 1};
    let sign = "";

    for (let i = 0; i < expressionArr.length; i++) {

        // 遍历到新的符号 且 符号栈中已经有符号
        if (!signStack.isEmpty() && signsValue[expressionArr[i]]) {
            // 窥探一下栈顶的符号
            sign = signStack.peek();

            // 如果当前符号优先级小于等于栈顶符号优先级,取出两个数字和栈顶符号进行运算
            if (signsValue[expressionArr[i]] <= signsValue[sign]) {

                let right = numStack.pop();
                let left = numStack.pop();

                let result = eval(left + signStack.pop() + right);


                // 计算结果和当前符号放入栈,准备下一轮计算
                numStack.push(result);
                signStack.push(expressionArr[i]);

            } else {
                // 当前符号优先级大于栈顶符号优先级,只取出数栈顶的一个元素和运算符下一个数字进行运算
                let curSign = expressionArr[i];
                let right = expressionArr[++i];
                let left = numStack.pop();

                let result = eval(left + curSign + right);
                numStack.push(result);
            }

            // 检测是否到最后一位字符
            if (i === expressionArr.length - 1) {
                let right = numStack.pop();
                let left = numStack.pop();
                let sign = signStack.pop();

                result = eval(left + sign + right);

                return result;
            }

            // 计算完没必要再放入栈中了
            continue;
        }


        // 第一次两个栈都为空
        if (!isNaN(expressionArr[i])) { // number

            numStack.push(expressionArr[i]);

        } else if (signsValue[expressionArr[i]]) { // sign

            signStack.push(expressionArr[i]);
        }
    }

    // 运算出最后的结果
    let right = numStack.pop();
    let left = numStack.pop();
    let lastSign = signStack.pop();

    return eval(left + lastSign + right);
}

逆波兰计算器

后缀表达式的计算器求值

如: (3+4) * 5 - 6 对应的后缀表达式就是 3 4 + 5 * 6 - ,针对后缀表达式的求值步骤:

  1. 从左至右扫描,将3和4压入栈;
  2. 遇到"+"运算符,弹出3和4,进行运算,结果压入栈;
  3. 遇到5,压入栈;
  4. 遇到"*"弹出7和5,将结果压入栈;
  5. 遇到6,压入栈;
  6. 遇到“-”,弹出35和6,进行运算,结果压入栈;
  7. 结束

实现后缀表达式计算器

输入一个后缀表达式 3 4 + 5 * 6 - => 29

function calculatePostfix(expression) {
    let expressionArr = expression.match(/([\d]+|[\/*+\-])/g);

    console.log(expressionArr);
    let numStack = new StackArray();

    for (let i = 0; i < expressionArr.length; i++) {
        // number
        if (!isNaN(expressionArr[i])) {
            numStack.push(expressionArr[i]);
        } else {
            // sign
            // 遇到符号就取出两个数字进行运算
            let right = numStack.pop();
            let left = numStack.pop();
            let sign = expressionArr[i];

            numStack.push(eval(left + sign + right));
        }
    }

    return numStack.peek();
}

从代码实现中可以发现,后缀表达式相对中缀表达式计算非常方便,很符合计算机的运算方式,遇到符号就将数字取出栈运算,将结果放入栈。

中缀表达式转后缀表达式⭐️

🌰

1 + ( ( 2 + 3 ) * 4 ) - 5  =>  1 2 3 + 4 * + 5 -

考虑以下几种情况:

     top   cur
① 1  -  2  +  3 - 4
② 1  *  2  +  3
③ 1  -  2  *  3
------------------------
④ 1 - (2 * (3 + 4)) * 5

用一个栈s1保存符号,用第二个栈s2保存后缀表达式。

扫描到数字直接进入s2。

top cur 代表符号优先级

① top 与 cur 的优先级相同, 转换:1 - 2 + 3 - 4=> 1 2 - 3 + 4 -

  1. "-"先入栈s1
  2. 扫描到"+",优先级相同,"-“先出栈,进入s2,”+"进入栈s1
  3. 扫描到"-",优先级相同,"+“先出栈,进入s2,”-"进入栈s1
  4. 扫描到最后一个数字,s1中的"-"出栈,进入s2

②top > cur,转换:1 * 2 + 3 => 1 2 * 3 +

  1. "*"先入栈s1
  2. 扫描到"+","*“弹出s1,入s2,”+"入s1
  3. 扫描到最后一个数字,s1中的"+"出栈,进入s2

③ top < cur,转换:1 - 2 * 3 => 1 2 3 * -

  1. "-"先入栈s1
  2. 扫描到"*","*“的下一个数字入栈s2,”*"入栈s2
  3. "-"入栈s2

()关键思路分析:

  1. ( 2 + 3 )括号中一定会有一个运算符的优先级被提到最高
    1. 如( 2 + 3 ) 先让(入栈,依次是+,然后是)就从栈中取出符号,并且取出(
    2. 如( ( 2 + 3 ) * 4 ) ((+入栈,遇到),取出+(此时+就是被提高优先级的符号。*入栈,遇到),取出*(此时*就是被提高优先级的符号。

如图:

在这里插入图片描述

在这里插入图片描述

()中的运算符优先级提升,同时也运用了栈先进后出的概念。

④ 1 - (2 * (3 + 4)) * 5 转换:1 2 3 4 + * 5 * -

  1. "-"入栈s1
  2. "("入栈s1
  3. "*"入栈s1
  4. "("入栈s1
  5. "+"入栈s1
  6. 扫描到")",取出"+(","+"入栈s2,此时"+"运算优先级提高
  7. 扫描到")",取出"*(","*",入栈s2,"*"运算优先级提高,此时栈s1中仅剩下"-"
  8. 扫描到"*",根据③,"*“的下一个数字入栈s2,”*“入栈s2,”-"入栈s2

小结

  1. 数字:直接入栈

  2. 符号:

    1. 栈为空 or 栈顶为"(" or cur为"(",符号直接入栈
    2. cur为")",取出栈s1中的常规运算符,进入栈s2,弹出"(",不做任何操作
    3. cur为常规运算符,top为常规运算符,进行比较
      1. top >= cur,top出栈s1,进入s2,cur进入s1
      2. top < cur,cur下一个数字入栈s2,cur入栈s2,top出栈s1,入栈s2
    4. 根据②③,扫描到最后一个数字栈s1,可能为空也可能有符号,有符号就直接入栈s2
  3. 细节:最后s2符号出栈是逆序排列,因此需要颠倒过来。

代码实现

function calculatePostfix(expression) {
    expression = expression.replace(/ +/g, "");
    expressionArr = expression.match(/([\d+]|[()\-\/+*%])/g);

    let signStack = new StackArray();
    let numStack = new StackArray();
    let signsValue = {"-": 1, "+": 1, "*": 2, "/": 2, "%": 1};
    let result = [];

    for (let i = 0; i < expressionArr.length; i++) {
        // number
        if (!isNaN(expressionArr[i])) {
            numStack.push(expressionArr[i]);

        } else {//sign
            let cur = expressionArr[i];
            let top = signStack.peek();

            if (signStack.isEmpty() || top === '(' || cur === '(') {
                signStack.push(cur);

            } else if (cur === ')') {

                numStack.push(signStack.pop());
                // 弹出'('
                signStack.pop();

            } else { // 常规运算符号
                let curValue = signsValue[cur];
                let topValue = signsValue[top];
                // 将top弹出s1
                top = signStack.pop();

                if (topValue >= curValue) {
                    numStack.push(top);
                    signStack.push(cur)

                } else {
                    numStack.push(expressionArr[++i]);
                    numStack.push(cur);
                    numStack.push(top);
                }
            }
        }
    }

    if (!signStack.isEmpty()) {
        numStack.push(signStack.pop());
    }

    let j = 0;
    while(!numStack.isEmpty()) {
        result[j++] = numStack.pop();
    }
    return result.reverse().join('');
}
版权声明:本文为ZHgogogoha原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/ZHgogogoha/article/details/108848136

智能推荐

spring cloud netflix (07) 服务的消费者(feign)

前言 完整知识点:spring cloud netflix 系列技术栈 Feign (同步通信 HTTP通信) feign是基于接口完成服务与服务之间的通信的 搭建Feign服务 项目结构 项目搭建 pom.xml application类 application.yml 使用feign完成服务与服务之间的通信 feign是基于接口完成服务与服务之间的通信的...

AtCoder Beginner Contest 174 E.Logs

AtCoder Beginner Contest 174 E.Logs 题目链接 到最后才发现是二分,菜菜的我/(ㄒoㄒ)/~~ 我们直接二分 [1,max{a[i]}][1,max\lbrace a[i]\rbrace][1,max{a[i]}] 即可,对每一个 midmidmid,每个数 a[i]a[i]a[i] 只需要切 a[i]−1mid\frac{a[i]-1}{mid}mi...

小程序基础与实战案例

小程序开发工具与基础 小程序开发准备: 申请小程序账号( appid ) 下载并安装微信开发者工具 具体步骤如下: 先进入 微信公众平台 ,下拉页面,把鼠标悬浮在小程序图标上 然后点击 小程序开发文档 照着里面给的步骤,就可以申请到小程序账号了。 然后就可以下载 开发者工具 了 下载完打开后的界面就是这个样子 下面让我们来新建一个小程序开发项目: 在AppID输入自己刚刚注册的AppID就可以,或...

VMware centOS7 下通过minikube部署Kubernetes

1、环境准备: VMware CentOS-7-x86_64 CPU:2*2core 内存:8G 宿主机和虚拟机需网络互通,虚拟机外网访问正常 Centos发行版版本查看:cat /etc/centos-release root用户操作 2、禁用swap分区 Kubernetes 1.8开始要求关闭系统的Swap,可暂时关闭或永久禁用, 使用 $ free -m 确认swap是否为开启状态 $ s...

逻辑回归与scikit-learn

欢迎关注本人的微信公众号AI_Engine LogisticRegression 算法原理 一句话概括:逻辑回归假设数据服从伯努利分布,通过极大化似然函数(损失函数)的方法,运用梯度下降或其他优化算法来求解参数,来达到将数据二分类的目的。 定义:逻辑回归(Logistic Regression)是一种用于解决二分类(0 or 1)问题的机器学习方法,用于估计某种事物的可能性(不是概率)。比如某用户...

猜你喜欢

指针OR数组?用他们来表达字符串又有何不同?

cocowy的编程之旅 在学习C语言的过程中我们经常可以看到或者听到这样一句话:数组其实等价于指针,例如: 在这里可以轻松的看出输出后他们的值相等,其实在计算机内存里面,p为本地变量,有着他自己的作用域。而指针变量q保存着这个数组的首地址,通过*号指向这个地址保存的变量值。 然而我们再看一个例子: 这个时候计算机报错,这是为什么呢? 其实原因很简单,指针说指向的这个字符串的地址是位于计算机代码段地...

广度搜索

广度搜索的基本使用方法 广度搜索不同于深度搜索,是一种一步一步进行的过程,每一个点只记录一遍。需要用到队列记录每一步可以走到的位置,找到目标位置输出步数即可。 用到的知识:结构体、队列 如图 首先我们需要定义一个结构体来存储每个遍历到的点和步数 广搜不会用到递归,所以可以直接在主函数里写,这里需要定义一个结构体队列 初始化队列并将起始点入列 遍历 完整代码...

NIO Socket 编程实现tcp通信入门(二)

1、NIO简介 NIO面向通道和缓冲区进行工作,数据总是从通道读取到缓冲区中,或者从缓冲区写入到通道中。可以双向传输数据,是同步非阻塞式IO。NIO还引入了选择器机制,从而实现了一个选择器监听多个底层通道,减少了线程并发数。用NIO实现socket的Tcp通信需要掌握下面三个知识点: Buffer 缓冲区 Channel 通道 Selector 选择器   2、java.nio.Buff...

[字节码系列]ObjectWeb ASM构建Method Monitor

      在前面的篇章中,我们看到Java Instrutment的强大能力,本篇,我们将介绍如何使用ObjectWeb ASM的字节码增强能力构建Method Monitor       1.什么是ObjectWeb ASM      ObjectWeb ...

Core Location 电子围栏:入门

原文:Geofencing with Core Location: Getting Started 作者:Andy Pereira 译者:kmyhy 更新说明:Andy Pereira 将本教程升级至 Xcode 9.3 和 Swift 4.1。 Geofencing 会在设备进入/离开指定的电子围栏时通知应用程序。它可以让你写出一些很酷的应用程序,当你从家里出来时触发通知,或者在附近出现最爱的商...