20. 有效的括号,1047. 删除字符串中的所有相邻重复项,150. 逆波兰表达式求值

简介: 本内容涵盖三道编程题的题目与题解,包括“有效的括号”(使用栈判断括号是否匹配)、“删除字符串中的所有相邻重复项”(利用栈删除相邻重复字符)以及“逆波兰表达式求值”(通过栈计算后缀表达式的结果)。每道题均采用C++实现,详细展示了栈在解决匹配问题、字符串处理和表达式求值中的应用。代码逻辑清晰,适合学习栈数据结构的应用场景与实现方法。

题目:20. 有效的括号

给定一个只包括 '(',')','{','}','[',']' 的字符串 s ,判断字符串是否有效。

有效字符串需满足:

左括号必须用相同类型的右括号闭合。

左括号必须以正确的顺序闭合。

每个右括号都有一个对应的相同类型的左括号。

示例 1:

输入:s = "()"

输出:true

示例 2:

输入:s = "()[]{}"

输出:true

示例 3:

输入:s = "(]"

输出:false

提示:

1 <= s.length <= 104

s 仅由括号 '()[]{}' 组成

题解:

class Solution {
public:
    bool isValid(string s) {
        if (s.size() % 2 != 0) return false; // 如果s的长度为奇数,一定不符合要求
        stack<char> st;
        for (int i = 0; i < s.size(); i++) {
            if (s[i] == '(') st.push(')');
            else if (s[i] == '{') st.push('}');
            else if (s[i] == '[') st.push(']');
            // 第三种情况:遍历字符串匹配的过程中,栈已经为空了,没有匹配的字符了,说明右括号没有找到对应的左括号 return false
            // 第二种情况:遍历字符串匹配的过程中,发现栈里没有我们要匹配的字符。所以return false
            else if (st.empty() || st.top() != s[i]) return false;
            else st.pop(); // st.top() 与 s[i]相等,栈弹出元素
        }
        // 第一种情况:此时我们已经遍历完了字符串,但是栈不为空,说明有相应的左括号没有右括号来匹配,所以return false,否则就return true
        return st.empty();
    }
};

题目:1047. 删除字符串中的所有相邻重复项

给出由小写字母组成的字符串 S,重复项删除操作会选择两个相邻且相同的字母,并删除它们。

在 S 上反复执行重复项删除操作,直到无法继续删除。

在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。

示例:

输入:"abbaca"

输出:"ca"

解释:

例如,在 "abbaca" 中,我们可以删除 "bb" 由于两字母相邻且相同,这是此时唯一可以执行删除操作的重复项。之后我们得到字符串 "aaca",其中又只有 "aa" 可以执行重复项删除操作,所以最后的字符串为 "ca"。

提示:

1 <= S.length <= 20000

S 仅由小写英文字母组成。

题解:

class Solution {
public:
    string removeDuplicates(string S) {
        stack<char> st;
        for (char s : S) {
            if (st.empty() || s != st.top()) {
                st.push(s);
            } else {
                st.pop(); // s 与 st.top()相等的情况
            }
        }
        string result = "";
        while (!st.empty()) { // 将栈中元素放到result字符串汇总
            result += st.top();
            st.pop();
        }
        reverse (result.begin(), result.end()); // 此时字符串需要反转一下
        return result;
 
    }
};

题目:150. 逆波兰表达式求值

给你一个字符串数组 tokens ,表示一个根据 逆波兰表示法 表示的算术表达式。

请你计算该表达式。返回一个表示表达式值的整数。

注意:

有效的算符为 '+'、'-'、'*' 和 '/' 。

每个操作数(运算对象)都可以是一个整数或者另一个表达式。

两个整数之间的除法总是 向零截断 。

表达式中不含除零运算。

输入是一个根据逆波兰表示法表示的算术表达式。

答案及所有中间计算结果可以用 32 位 整数表示。

示例 1:

输入:tokens = ["2","1","+","3","*"]

输出:9

解释:该算式转化为常见的中缀算术表达式为:((2 + 1) * 3) = 9

示例 2:

输入:tokens = ["4","13","5","/","+"]

输出:6

解释:该算式转化为常见的中缀算术表达式为:(4 + (13 / 5)) = 6

示例 3:

输入:tokens = ["10","6","9","3","+","-11","*","/","*","17","+","5","+"]

输出:22

解释:该算式转化为常见的中缀算术表达式为:

 ((10 * (6 / ((9 + 3) * -11))) + 17) + 5

= ((10 * (6 / (12 * -11))) + 17) + 5

= ((10 * (6 / -132)) + 17) + 5

= ((10 * 0) + 17) + 5

= (0 + 17) + 5

= 17 + 5

= 22

提示:

1 <= tokens.length <= 104

tokens[i] 是一个算符("+"、"-"、"*" 或 "/"),或是在范围 [-200, 200] 内的一个整数

逆波兰表达式:

逆波兰表达式是一种后缀表达式,所谓后缀就是指算符写在后面。

平常使用的算式则是一种中缀表达式,如 ( 1 + 2 ) * ( 3 + 4 ) 。

该算式的逆波兰表达式写法为 ( ( 1 2 + ) ( 3 4 + ) * ) 。

逆波兰表达式主要有以下两个优点:

去掉括号后表达式无歧义,上式即便写成 1 2 + 3 4 + * 也可以依据次序计算出正确结果。

适合用栈操作运算:遇到数字则入栈;遇到算符则取出栈顶两个数字进行计算,并将结果压入栈中

题解:

class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        // 力扣修改了后台测试数据,需要用longlong
        stack<long long> st;  
        for (int i = 0; i < tokens.size(); i++) {
            if (tokens[i] == "+" || tokens[i] == "-" || tokens[i] == "*" || tokens[i] == "/") {
                long long num1 = st.top();
                st.pop();
                long long num2 = st.top();
                st.pop();
                if (tokens[i] == "+") st.push(num2 + num1);
                if (tokens[i] == "-") st.push(num2 - num1);
                if (tokens[i] == "*") st.push(num2 * num1);
                if (tokens[i] == "/") st.push(num2 / num1);
            } else {
                st.push(stoll(tokens[i]));
            }
        }
 
        int result = st.top();
        st.pop(); // 把栈里最后一个元素弹出(其实不弹出也没事)
        return result;
    }
};
相关文章
|
人工智能 安全 Apache
QwenPaw:你的私人 AI 助理 —— 数据归你、记忆进化、多端触达的开源个人智能体
QwenPaw 是一款开源、本地优先的AI个人智能体(Apache 2.0),数据归属用户、记忆自主进化、支持钉钉/飞书/微信等多端触达。3行命令即可部署,内置Coding IDE、Persona人格、定时任务、MCP工具生态与多Agent协作,真正属于你的私有AI助理。
QwenPaw:你的私人 AI 助理 —— 数据归你、记忆进化、多端触达的开源个人智能体
|
7月前
|
监控 Linux iOS开发
免费开源天花板!Veyon 机房多媒体教学管控全套部署 + 零基础实操教程
Veyon是一款完全免费、开源的跨平台教室控制软件,支持Windows/macOS/Linux,提供屏幕监控、广播、远程控制、文件分发等全功能,无需授权、无广告、无人数限制,轻松替代极域、红蜘蛛,是学校与培训机构的高性价比教学管控方案。
|
8月前
|
人工智能 安全 应用服务中间件
3 分钟用 Docker 部署 CoPaw!你的专属AI个人助理
Copaw是AI个人助理领域新锐,支持多平台接入、本地/云端灵活部署及大模型无缝对接。本文提供Docker一站式部署指南,集成国内镜像加速,严格区分测试与生产环境配置,兼顾3分钟快速验证与企业级安全、高可用、可运维要求。
4583 5
|
Linux 虚拟化 iOS开发
macOS Ventura 13.7.7 (22H722) Boot ISO 原版可引导镜像下载
macOS Ventura 13.7.7 (22H722) Boot ISO 原版可引导镜像下载
6482 0
macOS Ventura 13.7.7 (22H722) Boot ISO 原版可引导镜像下载
|
算法 搜索推荐 数据挖掘
智能API驱动:精准推荐,提升客户复购率
智能API驱动的精准推荐技术,通过实时数据分析与个性化算法,整合用户行为、偏好及商品特征,为电商、内容、旅游等多行业提供动态场景化推荐。低延迟、高并发的微服务架构确保流畅体验,A/B测试优化转化率,提升复购与客单价。支持企业自定义权重参数,适配多样化业务需求,助力交叉销售与增长策略。
|
8天前
|
Linux Go 开发工具
手机上跑 DeepSeek 智能体:开源安卓客户端 DSH Go 安装与使用指南
DSH Go 是一款开源安卓客户端,将 DeepSeek Harness 智能体引擎装进手机:免 Root、免 Termux,一键安装即用;支持本机运行(内置 Ubuntu+Node.js)或远程接管电脑会话;具备插话打断、过程折叠、屏幕操控、端到端加密分享等特色功能,真正实现智能体“口袋化”。
9775 25
|
8天前
|
弹性计算 人工智能 API
Codex超详细入门指南(下载·安装·登录·上手,全版本覆盖,2026最新版)
建议收藏本教程,2026 全年各版本更新随时回来查阅。如果你在搭建过程中遇到任何问题,欢迎结合 阿里云工单系统 提交技术支持请求,或在 阿里云开发者社区 搜索 Codex 相关话题交流。 祝你编码愉快,效率翻倍!
2756 14