首页 > 编程语言 >【算法】栈——逆波兰表达式求值

【算法】栈——逆波兰表达式求值

时间:2024-05-25 12:27:48浏览次数:28  
标签:操作数 right st push 算法 求值 表达式 left

题解:逆波兰表达式求值(栈算法)

目录

1.题目

题目链接:LINK
在这里插入图片描述

2.题意

这个题目种涉及一些概念,应当适当说一下。

2.1逆波兰表达式

后缀表达式,是一种数学表达式的表达方式,我们平时数学所用的称为中缀表达式,即:操作数-操作符-操作数 的格式,而后缀表达式,即是:操作数-操作数-操作符 的格式。

中缀表达式–>后缀表达式:
举例如下:
eg1:
a + b --> a b +

eg2:
在这里插入图片描述
eg3:
在这里插入图片描述

2.2向零截断

这个概念呢…就是一种取近似值的方式,具体什么意思呢,下面我来进行简要介绍。

所谓的 向零截断 ,即结果是5.5那就会取到5,如果是结果是-3.3那就会取到-3。
大概就是下面的取值图:
在这里插入图片描述

3.题解

思路:利用栈先入后出的特点来求解。

  • 遍历:遍历题目给的vector值,
  • 数入栈:如果是操作数,就入栈,
  • 符出栈:如果是操作符,就出两个操作数与操作符进行运算,
  • 得结果:然后将结果返回到栈中。直到vector入完栈并在栈中计算完结果。
class Solution {
public:
    int evalRPN(vector<string>& tokens) 
    {
        stack<int> st;
        set<string> s = {"+","-","*","/"};
        for(string& str : tokens)
        {
            //如果是运算符,操作数出栈,运算,返回栈
            if(s.find(str) != s.end())
            {
               int right = st.top();
               st.pop();
               int left = st.top();
               st.pop();
               
               switch(str[0])
               {
                case '+':
                st.push(left + right);
                break;
                case '-':
                st.push(left - right);
                break;
                case '*':
                st.push(left * right);
                break;
                case '/':
                st.push(left / right);
                break;
               }
            }
            //如果是操作数,入栈
            else
            {
                st.push(stoi(str));
            }
        }

        return st.top();
    }
};

4.总结

要理解后缀表达式的含义才可以做这道题,然后还需要熟悉栈,因为这个运算逻辑跟栈刚好吻合。


EOF

标签:操作数,right,st,push,算法,求值,表达式,left
From: https://blog.csdn.net/2302_79031646/article/details/139171781

相关文章

  • 【无标题】基于[具体技术]的烟雾识别算法研究
    本文主要探讨了一种高效的烟雾识别算法,通过对[相关技术或特征]的分析和利用,实现了对烟雾的准确检测和识别。详细介绍了算法的原理、流程以及实验结果,并结合实际应用案例展示了其应用价值。一、引言(阐述烟雾识别的重要性及应用场景)二、相关工作(回顾以往烟雾识别算法的研究......
  • 算法学习笔记——动态规划.最长上升/下降子序列 2024.5.24
    LanqiaoOJ 773这道题是一道动态规划的题目,主要考察最长上升/下降子序列,难度中等,但是对思维的考察比较重要,特别是如何解决其第二问题目描述某国为了防御敌国的导弹袭击,发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷:虽然它的第一发炮弹能够到达任意的高度,但是以......
  • 算法学习笔记——深度优先搜索DFS 2024.5.25
    LanqiaoOJ141此题是一道比较经典的搜索题目,这里采用深度优先搜索的方法题目描述X星的坦克战车很奇怪,它必须交替地穿越正能量辐射区和负能量辐射区才能保持正常运转,否则将报废。某坦克需要从A区到B区去(A,B区本身是安全区,没有正能量或负能量特征),怎样走才能路径最短?......
  • 1358:中缀表达式值(expr)
    题目网址:信息学奥赛一本通(C++版)在线评测系统题目介绍:1358:中缀表达式值(expr)时间限制:1000ms      内存限制:65536KB提交数:13372   通过数: 4646【题目描述】输入一个中缀表达式(由0-9组成的运算数、加+减-乘*除/四种运算符、左右小括号组成。注意“......
  • 基于天牛须(BAS)与NSGA-Ⅱ混合算法的交直流混合微电网多场景多目标优化调度(Matlab代
    ......
  • 常见的排序算法——归并排序(六)
    本文记述了多向归并排序的基本思想并给出了一份参考实现代码。在说明了算法的性能后用随机数据进行了验证。◆思想在归并排序、归并排序(二)、归并排序(三)、归并排序(四)中记述的归并排序,都是把待排序范围分成两个部分分别排序的。而多向归并排序是把待排序范围分为K个部分,把它们......
  • Mysql自增id、uuid、雪花算法id的比较
    MySQL自增id:优点:1.简单易用​MySQL自增id由数据库自动生成。2.效率高自增id是按顺序递增的,可以提高插入和查询的效率。3.索引效率高自增id可以作为主键或索引列,提高查询效率。缺点:1.不适用于分布式系统在分布式环境下,多个节点生成的自增id可能会冲突,需要额外的处理机......
  • m基于GA-GRU遗传优化门控循环单元网络的电力负荷数据预测算法matlab仿真
    1.算法仿真效果matlab2022a仿真结果如下: 优化前:    优化后:    对比:   2.算法涉及理论知识概要      基于遗传算法(GeneticAlgorithm,GA)优化的长门控循环单元(GatedRecurrentUnit,GRU)网络,是一种结合了进化计算与深度学习的混合预测模......
  • 代码随想录算法训练营第一天 | 977.有序数组的平方;
    代码随想录算法训练营第一天|977.有序数组的平方;977题链接:https://leetcode.cn/problems/squares-of-a-sorted-array/代码随想录链接:https://programmercarl.com/0977.有序数组的平方.html#思路209题链接:https://leetcode.cn/problems/minimum-size-subarray-sum/submission......
  • 基于BP神经网络的16QAM解调算法matlab性能仿真
    1.算法运行效果图预览  2.算法运行软件版本MATLAB2022a 3.算法理论概述     16QAM(QuadratureAmplitudeModulation,正交幅度调制)是一种高效的数字调制技术,能够在相同的带宽内传输比传统调制方式更多的信息。解调是通信系统中从接收到的信号中恢复原始信息的关......