【优选算法】栈 {何时使用栈结构？后缀表达式求值；中缀转后缀表达式；中缀表达式求值}

一、经验总结

何时使用栈结构解题？

  1. 做过相似的使用栈结构解得的题目
  2. 嵌套处理：在从前向后处理的过程中，由于之后内容的不确定性而导致当前操作不能贸然进行，需要先进行保存，直到遇到区间结束标志（如’)'）此时才能处理最近区间的内容。从前往后存，从后往前取，正好是栈后进先出的特点。

二、相关编程题

2.1 删除字符串中的所有相邻重复项

题目链接

1047. 删除字符串中的所有相邻重复项 - 力扣（LeetCode）

题目描述

在这里插入图片描述

算法原理

在这里插入图片描述

编写代码

class Solution {
public:
    string removeDuplicates(string s) {
        string ret; //用数组模拟栈结构
        for(auto ch : s)
        {
            if(!ret.empty() && ch == ret.back())
                ret.pop_back();
            else
                ret.push_back(ch);
        }
        return ret;
    }
};

2.2 比较含退格的字符串

题目链接

844. 比较含退格的字符串 - 力扣（LeetCode）

题目描述

在这里插入图片描述

算法原理

同上，略

编写代码

class Solution {
public:
    bool backspaceCompare(string s, string t) {
        return ChangeStr(s) == ChangeStr(t);
    }

    string ChangeStr(const string& str)
    {
        string ret;
        for(auto ch : str)
        {
            if(ch == '#')
            {
                if(!ret.empty()) ret.pop_back();
            } 
            else
                ret+=ch;
        }
        return ret;
    }
};

2.3 基本计算器 II（无括号）

题目链接

227. 基本计算器 II - 力扣（LeetCode）

题目描述

在这里插入图片描述

算法原理

在这里插入图片描述

编写代码

class Solution {
public:
    int calculate(string s) {
        stack<int> st;
        char op = '+';
        int i = 0;
        while(i < s.size())
        {
            if (s[i] == ' ') ++i;
            else if (s[i] >= '0' && s[i] <= '9') 
            {
                int num = 0;
                while (i < s.size() && s[i] >= '0' && s[i] <= '9') 
                {
                    num = num * 10 + (s[i]-'0');
                    ++i;
                }
                switch (op) 
                {
                case '+':
                    st.push(num);
                    break;
                case '-':
                    st.push(-num);
                    break;
                case '*':
                    st.top()*=num;
                    break;
                case '/':
                    st.top()/=num;
                    break;
                }
            }
            else op = s[i++];
        }

        int ret = 0;
        while(!st.empty())
        {
            ret += st.top();
            st.pop();
        }
        return ret;
    }
};

2.4 逆波兰表达式求值

题目链接

150. 逆波兰表达式求值 - 力扣（LeetCode）

题目描述

在这里插入图片描述

算法原理
后缀表达式求值
后缀表达式，也称为逆波兰表达式，是一种没有操作符优先级的表达式（也没有左右括号），因此求值过程相对直接。求值过程通常涉及使用一个栈来辅助存储操作数，并按照以下步骤进行：

  1. 遍历后缀表达式中的每个元素。
  2. 如果遇到操作数（通常是数字），则将其压入栈中。
  3. 如果遇到操作符，则从栈中弹出两个操作数进行计算，并将结果压回栈中。
  4. 这个过程持续直到后缀表达式中的所有元素都被处理，最终栈中剩下的就是表达式的计算结果。

逆波兰 - 下（后缀表达式计算结果）_哔哩哔哩_bilibili

编写代码

class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        stack<int> nums; //使用一个栈来辅助存储操作数
        for(auto &str : tokens)
        {
            if(IsNum(str))
            {
                nums.push(stoi(str));
            }
            else
            {
                int right = nums.top(); //后进先出，右操作数先出栈
                nums.pop();
                int left = nums.top();
                nums.pop();
                switch(str[0])
                {
                    case '+':
                        nums.push(left+right);
                    break;
                    case '-':
                        nums.push(left-right);
                    break;
                    case '*':
                        nums.push(left*right);
                    break;
                    case '/':
                        nums.push(left/right);
                    break;
                }
            }
        }
        return nums.top();
    }

    bool IsNum(const string &str)
    {
        if(str[0] == '-')
        {
            if(str.size() > 1) return true;
        }
        else if(str[0] >= '0' && str[0] <= '9')
        {
            return true;
        }
        return false;
    }
};

2.5 中缀表达式求值（有括号）

题目链接

表达式求值_牛客题霸_牛客网 (nowcoder.com)

题目描述

在这里插入图片描述

算法原理

解法一：中缀表达式转后缀表达式，再运算

在中缀变后缀时，操作数的顺序不会发生变化，只有运算符的顺序可能发生变化。同时又没有括号。所以在转换的过程中，只要碰到操作数，可以直接输出，而遇到运算符和括号进行相应的处理即可。

转换原则如下：

1.从左到右读取一个中序表达式。

2.若读取的是操作数，则直接输出。

3.若读取的是运算符，分三种情况。

  1. 该运算符为左括号（ ，则直接存入堆栈。 （等待右括号出现；提高优先级：隔断左括号之前的运算符优先级比较）

  2. 该运算符为右括号），则输出堆栈中的运算符，直到取出左括号为止。 （提高优先级：优先处理括号内的运算）

  3. 该运算符为非括号运算符，则与堆栈顶端的运算符做优先权比较：

    • 如果栈为空或当前运算符优先级高于栈顶运算符，则直接入栈。（不能确定后面的运算符优先级是否更高，入栈等待）
    • 如果当前运算符优先级低于等于栈顶运算符，则弹出栈顶运算符并输出，直到当前运算符优先级大于栈顶运算符或者栈空为止，然后将当前运算符入栈。（能够确定栈顶运算符的优先级比后面的运算符（当前）优先级更高，出栈运算）

4.当表达式已经读取完成，而堆栈中尚有运算符时，则依次序取出运算符，直到堆栈为空，由此得到的结果就是中缀表达式转换成的后缀表达式。

5.后缀表达式求值参考上一题。

逆波兰 - 上（中缀表达式 转 后缀表达式）_哔哩哔哩_bilibili

解法二：数字栈和算符栈

中缀表达式求值通常涉及使用栈来处理运算符和操作数。以下是中缀表达式求值的基本步骤：

  1. 定义两个栈，一个用于存储操作数，另一个用于存储运算符。

  2. 遍历中缀表达式的每个字符，如果遇到操作数（数字），则将其压入操作数栈。

  3. 如果遇到运算符，则将其与运算符栈的栈顶元素比较优先级：

    1. 如果运算符的优先级高于栈顶元素的优先级或运算符栈为空，将其压入运算符栈。（不能确定后面的运算符优先级是否更高，入栈等待）
    2. 如果运算符的优先级低于或者等于栈顶元素的优先级，则从操作数栈弹出两个操作数进行计算，并将结果压入操作数栈，同时将运算符栈中优先级低于或等于当前运算符的元素依次弹出并处理，直到遇到一个优先级高于当前运算符的元素或栈为空，再将运算符压入运算符栈。（能够确定栈顶运算符的优先级更高，出栈运算）

  5. 如果遇到左括号“(”，则直接将其压入运算符栈。（提高优先级：隔断左括号之前的运算符优先级比较；等待右括号出现）

  6. 如果遇到右括号“)”，则从运算符栈弹出并处理运算符，直到遇到左括号“(”为止。（提高优先级：优先处理括号内的运算）

  7. 遍历完成后，如果运算符栈中还有元素，则从操作数栈弹出两个操作数进行计算，并将结果压回操作数栈。

  8. 最后，操作数栈中剩下的元素（如果有）就是表达式的求值结果。

这种方法的关键在于正确处理运算符的优先级和括号，其实底层原理与解法一相同。

中缀表达式的计算_哔哩哔哩_bilibili

编写代码

//解法一：中缀表达式转后缀表达式，再运算
#include <cmath>
class Solution {
public:
    int solve(string s) {
        stack<char> ops;
        unordered_map<char, int> op_level = {{'+', 1}, {'-', 1}, {'*', 2}, {'/', 2}}; //运算符的优先级
        vector<string> tokens; //存储后缀表达式
        //中缀转后缀
        int i = 0;
        while(i < s.size())
        {
            if(IsNum(s[i]))
            {
                string num;
                while(i < s.size() && IsNum(s[i]))
                {
                    num += s[i++];
                }
                tokens.push_back(num);
            }
            else if (s[i] == '(') 
            {
                ops.push(s[i++]);
            } 
            else if (s[i] == ')') 
            {
                while(ops.top() != '(')
                {
                    tokens.push_back(string(1, ops.top()));
                    ops.pop();
                }
                ops.pop();
                ++i;
            }
            else 
            {
                while (!ops.empty() && ops.top() != '(' && op_level[s[i]] <= op_level[ops.top()]) 
                {
                    tokens.push_back(string(1, ops.top()));
                    ops.pop();
                }
                ops.push(s[i++]);
            } 
        }

        while(!ops.empty())
        {
            tokens.push_back(string(1, ops.top()));
            ops.pop();
        }

        //后缀表达式求值
        return evalRPN(tokens); //这里复用上一题的代码，直接复制过来使用就行
    }

    bool IsNum(char ch)
    {
        return ch >= '0' && ch <= '9';
    }
};

//解法二：数字栈和算符栈
class Solution {
    stack<char> op_st; //算符栈
    stack<int> num_st; //数字栈
    unordered_map<char, int> op_level = {{'+', 1}, {'-', 1}, {'*', 2}, {'/', 2}}; //运算符的优先级
  public:
    int solve(string s) {
        int i = 0;
        while (i < s.size()) {
            if (IsNum(s[i])) 
            {
                int num = 0;
                while (i < s.size() && IsNum(s[i]))
                    num = num * 10 + (s[i++] - '0');
                num_st.push(num);
            } 
            else if (s[i] == '(') 
            {
                op_st.push(s[i++]);
            } 
            else if (s[i] == ')') 
            {
                while (op_st.top() != '(') calc();
                op_st.pop();
                ++i;
            } 
            else 
            {
                while (!op_st.empty() && op_st.top() != '(' && op_level[s[i]] <= op_level[op_st.top()]) calc();
                op_st.push(s[i++]);
            }
        }

        while(!op_st.empty()) calc();
        return num_st.top();
    }

    bool IsNum(char ch) {
        return ch >= '0' && ch <= '9';
    }
	
    //calc的工作是从栈中取出2个操作数和1个操作符进行运算，并将结果压入数字栈
    void calc() {
        char op = op_st.top();
        op_st.pop();
        int right = num_st.top();
        num_st.pop();
        int left = num_st.top();
        num_st.pop();
        int ret = 0;
        switch (op) {
            case '+':
                ret = left + right;
                break;
            case '-':
                ret = left - right;
                break;
            case '*':
                ret = left * right;
                break;
            case '/':
                ret = left / right;
                break;
        }
        num_st.push(ret);
    }
};

2.6 字符串解码

题目链接

394. 字符串解码 - 力扣（LeetCode）

题目描述

在这里插入图片描述

算法原理

在这里插入图片描述

编写代码

class Solution {
public:
    string decodeString(string s) {
        stack<string> str_st;
        stack<int> num_st;
        str_st.push("");
        int i = 0;
        while(i < s.size())
        {
            if(IsNum(s[i]))
            {
                int num = 0;
                while(i < s.size() && IsNum(s[i]))
                {
                    num = num*10+(s[i]-'0');
                    ++i;
                }
                num_st.push(num);
            }
            if(s[i] == '[')
            {
                ++i;
                string tmp;
                while(i < s.size() && IsLetter(s[i]))
                {
                    tmp += s[i];
                    ++i;
                }
                str_st.push(tmp);
            }
            if(s[i] == ']')
            {
                string top = str_st.top();
                str_st.pop();
                int k = num_st.top();
                num_st.pop();
                while(k--)  str_st.top()+=top;
                ++i;
            }
            if(IsLetter(s[i]))
            {
                str_st.top()+=s[i];
                ++i;
            }
        }
        return str_st.top();
    }

    bool IsNum(char ch)
    {
        return ch >= '0' && ch <='9';
    }
    
    bool IsLetter(char ch)
    {
        return ch >= 'a' && ch <= 'z';
    }
};

2.7 验证栈序列

题目链接

946. 验证栈序列 - 力扣（LeetCode）

题目描述

在这里插入图片描述

算法原理

在这里插入图片描述

编写代码

class Solution {
public:
    bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
        stack<int> st;
        int j = 0;
        for(int i = 0; i < pushed.size(); ++i)
        {
            st.push(pushed[i]);
            while(!st.empty() && st.top() == popped[j])
            {
                st.pop();
                ++j;
            }
        }
        return j == popped.size();
    }
};

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/680429.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

2024年船舶、机械制造与海洋科学国际会议（ICSEMMS2024）

2024年船舶、机械制造与海洋科学国际会议（ICSEMMS2024）

2024年船舶、机械制造与海洋科学国际会议&#xff08;ICSEMMS2024&#xff09; 会议简介 我们诚挚邀请您参加将在重庆隆重举行的2024年国际造船、机械制造和海洋科学大会&#xff08;ICSEMMS024&#xff09;。作为一项跨学科和跨学科的活动&#xff0c;本次会议旨在促进造船…
阅读更多...
PostgreSQL专家（pcp51)--王丁丁

PostgreSQL专家（pcp51)--王丁丁

#PostgreSQL培训 #postgresql认证 #postgreSQL考试 #PG考试 #PG培训
阅读更多...
【Python系列】Python装饰器

【Python系列】Python装饰器

&#x1f49d;&#x1f49d;&#x1f49d;欢迎来到我的博客&#xff0c;很高兴能够在这里和您见面&#xff01;希望您在这里可以感受到一份轻松愉快的氛围&#xff0c;不仅可以获得有趣的内容和知识&#xff0c;也可以畅所欲言、分享您的想法和见解。 推荐:kwan 的首页,持续学…
阅读更多...
【实战JVM】-实战篇-06-GC调优

【实战JVM】-实战篇-06-GC调优

文章目录 1 GC调优概述1.1 调优指标1.1.1 吞吐量1.1.2 延迟1.1.3 内存使用量 2 GC调优方法2.1 发现问题2.1.1 jstat工具2.1.2 visualvm插件2.1.3 PrometheusGrafana2.1.4 GC Viewer2.1.5 GCeasy 2.2 常见GC模式2.2.1 正常情况2.2.2 缓存对象过多2.2.3 内存泄漏2.2.4 持续FullGC…
阅读更多...
【全开源】小区入户安检系统（FastAdmin + Uni-APP）

【全开源】小区入户安检系统（FastAdmin + Uni-APP）

守护家的每一道防线 一款基于FastAdmin Uni-APP开发的小区入户安检系统(前端可发布为小程序、H5、App)。可针对不同行业自定义安检项目&#xff0c;线下安检&#xff0c;线上留存&#xff08;安检拍照/录像&#xff09;&#xff0c;提高安检人员安检效率。 一、引言&#xff…
阅读更多...
NLP(1)-TF-IDF算法介绍

NLP(1)-TF-IDF算法介绍

一、TF-IDF算法介绍 TF-IDF&#xff08;term frequency–inverse document frequency&#xff0c;词频-逆向文件频率&#xff09;是一种用于信息检索&#xff08;information retrieval&#xff09;与文本挖掘&#xff08;text mining&#xff09;的常用加权技术。 TF-IDF是一…
阅读更多...
升级HarmonyOS 4.2，开启健康生活篇章

升级HarmonyOS 4.2，开启健康生活篇章

夏日来临&#xff0c;华为智能手表携 HarmonyOS 4.2 版本邀您体验&#xff0c;它不仅可以作为时尚单品搭配夏日绚丽服饰&#xff0c;还能充当你的健康管家&#xff0c;从而更了解自己的身体&#xff0c;开启智能健康生活篇章。 高血糖风险评估优化&#xff0c;健康监测更精准 …
阅读更多...
Java面向对象笔记

Java面向对象笔记

多态 一种类型的变量可以引用多种实际类型的对象 如 package ooplearn;public class Test {public static void main(String[] args) {Animal[] animals new Animal[2];animals[0] new Dog();animals[1] new Cat();for (Animal animal : animals){animal.eat();}} }class …
阅读更多...
html 使用svg矢量图时无法 调整宽高问题解决，不能像图片一样设置宽高比例问题

html 使用svg矢量图时无法 调整宽高问题解决，不能像图片一样设置宽高比例问题

引入的路径后加 #svgView(preserveAspectRatio(none)) 具体代码如下 修改前 <img src"/assets/svgs/full_screen_full.svg" class"im"> 修改后 <img src"/assets/svgs/full_screen_full.svg#svgView(preserveAspectRatio(none))" cla…
阅读更多...
前端处理流式数据(SSE服务)

前端处理流式数据(SSE服务)

前言 将数据用流的方式返回给客户端,这种技术需求在传统的管理项目中不多见,但是在媒体或者有实时消息等功能上就会用到,这个知识点对于前端还是很重要的。 即时你不写服务端,但是服务端如果给你这样的接口,你也得知道怎么去使用联调。 nodejs实现简单的SSE服务 SSE服务(Se…
阅读更多...
Java：流程控制语句

Java：流程控制语句

文章目录 一、顺序结构二、分支结构2.1 if2.2 switch 三、循环结构3.1 for3.2 while3.3 do...while 四、流程控制4.1 break4.2 continue 五、结语 一、顺序结构 顺序结构语句是Java程序默认的执行流程&#xff0c;按照代码的先后顺序&#xff0c;从上到下依次执行。 二、分支结…
阅读更多...
宏集Panorama SCADA：个性化定制，满足多元角色需求

宏集Panorama SCADA：个性化定制，满足多元角色需求

前言 在考虑不同人员在企业中的职能和职责时&#xff0c;他们对于SCADA系统的需求可能因其角色和工作职责的不同而有所差异。在SCADA系统的设计和实施过程中&#xff0c;必须充分考虑和解决这种差异性。 为了满足不同人员的需求, 宏集Panorama SCADA平台具备灵活的功能和定制…
阅读更多...
新书速览|Python Django 4构建动态网站的16堂课

新书速览|Python Django 4构建动态网站的16堂课

Python Django 4构建动态网站的16堂课 本书内容 《Python Django 4构建动态网站的16堂课》是一本关于Django框架的网站开发入门教材&#xff0c;适合想要学习并掌握Django框架的开发人员阅读。《Python Django 4构建动态网站的16堂课》共分16课&#xff0c;内容包括网站开发环境…
阅读更多...
影响指挥中心操作台的材质选择的因素有哪些

影响指挥中心操作台的材质选择的因素有哪些

指挥中心操作台作为现代指挥系统的重要组成部分&#xff0c;其材质的选择不仅关系到操作台的使用寿命和稳定性&#xff0c;更直接影响到整个指挥中心的运行效率和安全性。因此&#xff0c;对指挥中心操作台的材质设定一系列标准显得尤为重要。 耐用性考量&#xff1a;鉴于指挥中…
阅读更多...
Android Dialog使用汇总

Android Dialog使用汇总

Dialog分类 AlertDialog Dialog 类是对话框的基类&#xff0c;官方建议我们不要直接实例化它&#xff0c;而是使用其子类来获取实例。AlertDialog是系统提供的一个直接子类&#xff0c;它能帮助我们快速构建出不同类型的弹窗。接下来就看下各种类型弹窗的使用。 1、普通对话框…
阅读更多...
【遗传算法】【机器学习】【Python】常见交叉方法（一）、单点交叉和两点交叉

【遗传算法】【机器学习】【Python】常见交叉方法（一）、单点交叉和两点交叉

一、遗传算法流程图 交叉过程即存在于上图的”交叉“&#xff08;crossover&#xff09;步骤中。 二、单点交叉 随机地选择1个交叉位点进行交叉&#xff0c;如下图所示&#xff1a; 用random库实现随机性&#xff1a; import random# 简单的单点交叉方式 def sing_muta(lis…
阅读更多...
AI写作革命：毕业论文的新助手

AI写作革命：毕业论文的新助手

写作这件事一直让我们从小学时期就开始头痛&#xff0c;初高中时期800字的作文让我们焦头烂额&#xff0c;一篇作文里用尽了口水话&#xff0c;拼拼凑凑才勉强完成。 大学时期以为可以轻松顺利毕业&#xff0c;结果毕业前的最后一道坎拦住我们的是毕业论文&#xff0c;这玩意不…
阅读更多...
操作简单中医电子处方中药划价系统软件视频教程，佳易王诊所电子处方管理系统软件

操作简单中医电子处方中药划价系统软件视频教程，佳易王诊所电子处方管理系统软件

操作简单中医电子处方中药划价系统软件视频教程&#xff0c;佳易王诊所电子处方管理系统软件 一、前言 以下软件操作教程以&#xff0c;佳易王中西医诊所电子处方软件为例说明 软件文件下载可以点击最下方官网卡片——软件下载——试用版软件下载 1、软件支持中医和西医处方…
阅读更多...
多功能光时域反射仪的工作原理

多功能光时域反射仪的工作原理

6426A-2101多功能光时域反射仪是新一代掌上型智能化光纤通信测量仪器&#xff0c;具有强大的功能和广泛的应用领域。它能够显示光纤及光缆的损耗分布曲线图&#xff0c;测量光纤及光缆的多种关键参数&#xff0c;包括长度、损耗、接续质量等&#xff0c;为光纤通信系统的工程施…
阅读更多...
leetcode第867题：转置矩阵

leetcode第867题：转置矩阵

matrix[i][j]需要放在转置矩阵的(j,i)位置 public class Solution {public int[][] Transpose(int[][] matrix) {int rows matrix.Length; int columns matrix[0].Length; int[][] array2 new int[columns][];// 初始化内部数组&#xff08;列数&#xff09;for (int i 0…
阅读更多...
最新文章

Copyright @ 2022~2023