当前位置: 首页 > news >正文

Rust 数据结构与算法:3栈:用栈实现符号匹配

1、符号匹配

如: (5+6)×(7+8)/(4+3)、{ { ( [ ] [ ])}}、(a+b)(c*d)func() 等各类语句的符号匹配。

这里我们关注的不是数字而是括号,因为括号更改了操作优先级,限定了语言的语义,这是非常重要的。如果括号不完整,那么整个表达式就是错的。

括号都必须以成对匹配的形式出现。括号匹配意味着每个开始符号都有相应的结束符号,并且括号必须正确嵌套,这样计算机才能正确处理。

真正具有挑战的是如何编写一个算法来从左到右读取一串符号,并决定括号是否匹配。处理的第一个左开始括号必须等待,直到其匹配最后一个右关闭括号为止。结束符号以相反的顺序匹配开始符号,从内到外,这是一个可以用栈来解决的问题。

在这里插入图片描述

括号匹配

具体算法原理:

一旦采用栈来保存括号,算法的具体实现就很简单了,因为栈的操作无非就是出入栈和判断而已。

从空栈开始,从左到右处理括号字符串。如果一个符号是开始符号,将其入栈;

如果是结束符号,则弹出栈顶元素并开始匹配这两个符号。

如果它们恰好是左右匹配的,就继续处理下一个括号,直到字符串处理完为止。

最后,当所有符号都被处理后,栈应该是空的。只要栈不为空,就说明有括号不匹配。

检测包含任意字符的字符串是否匹配的代码:

#[derive(Debug)]
struct Stack<T> {size: usize,  // 栈大小data: Vec<T>, // 栈数据
}impl<T> Stack<T> {// 初始化空栈fn new() -> Self {Self {size: 0,data: Vec::new(), // 以 Vec 为低层}}fn is_empty(&self) -> bool {0 == self.size}fn len(&self) -> usize {self.size}// 清空栈fn clear(&mut self) {self.size = 0;self.data.clear();}// 将数据保存在 Vec 的末尾fn push(&mut self, val: T) {self.data.push(val);self.size += 1;}// 将栈顶减 1 后,弹出数据fn pop(&mut self) -> Option<T> {if 0 == self.size {return None;};self.size -= 1;self.data.pop()}// 返回栈顶数据引用和可变引用fn peek(&self) -> Option<&T> {if 0 == self.size {return None;}self.data.get(self.size - 1)}fn peek_mut(&mut self) -> Option<&mut T> {if 0 == self.size {return None;}self.data.get_mut(self.size - 1)}// 以下是为栈实现的迭代功能// into_iter: 栈改变,成为迭代器// iter: 栈不变,得到不可变迭代器// iter_mut:栈不变,得到可变迭代器fn into_iter(self) -> IntoIter<T> {// into_iter()方法获取了一个迭代器,然后进行迭代IntoIter(self)}fn iter(&self) -> Iter<T> {let mut iterator = Iter { stack: Vec::new() };for item in self.data.iter() {iterator.stack.push(item);}iterator}fn iter_mut(&mut self) -> IterMut<T> {let mut iterator = IterMut { stack: Vec::new() };for item in self.data.iter_mut() {iterator.stack.push(item);}iterator}
}
// 实现三种迭代功能
struct IntoIter<T>(Stack<T>);
// Iterator 是 Rust 的迭代器 迭代器(iterator)负责遍历序列中的每一项和决定序列何时结束的逻辑。当使用迭代器时,我们无需重新实现这些逻辑。
impl<T: Clone> Iterator for IntoIter<T> {// into_iter()方法获取了一个迭代器,然后进行迭代。type Item = T;fn next(&mut self) -> Option<Self::Item> {// 迭代器之所以成为迭代器,是因为实现了Iterator trait。要实现该特征,最主要的就是实现其中的 next 方法,该方法控制如何从集合中取值,最终返回值的类型是关联类型 Item。if !self.0.is_empty() {self.0.size -= 1;self.0.data.pop()} else {None}}
}
// 'a 生命周期标识 用于帮助编译器检查引用的有效性,避免悬垂引用和使用已被释放的内存。
// 从所有权的角度来理解,就是它可以避免因为Copy或者clone的造成的不必要开销
struct Iter<'a, T: 'a> {stack: Vec<&'a T>, // 'a 被用在了传参类型 T 上
}
impl<'a, T> Iterator for Iter<'a, T> {type Item = &'a T; // 生命周期标识只作用于引用上,且放在&符号之后 如这里的 &'a Tfn next(&mut self) -> Option<Self::Item> {self.stack.pop()}
}struct IterMut<'a, T: 'a> {stack: Vec<&'a mut T>,
}
impl<'a, T> Iterator for IterMut<'a, T> {type Item = &'a mut T;fn next(&mut self) -> Option<Self::Item> {self.stack.pop()}
}fn main() {let sa = "(2+3){func}[abc]";let sb = "(2+3)*(3-1";let sc = "{{([])}}";let sd = "((())";let se = "[[[]]]]]]]]]";let res1 = par_checker3(sa);let res2 = par_checker3(sb);let res3 = par_checker3(sc);let res4 = par_checker3(sd);let res5 = par_checker3(se);println!("sa balanced: {res1}");println!("sb balanced: {res2}");println!("sc balanced: {res3}");println!("sd balanced: {res4}");println!("se balanced: {res5}");
}// 同时检测多种开始符号和结束符号是否匹配
fn par_match(open: char, close: char) -> bool {let opens = "([{";let closers = ")]}";opens.find(open) == closers.find(close)
}
// 基于栈的符号匹配
fn par_checker3(par: &str) -> bool {let mut char_list = Vec::new();for c in par.chars() {char_list.push(c);}let mut index = 0;let mut balance = true;let mut stack = Stack::new();while index < char_list.len() && balance {let c = char_list[index];// 将开始符号入栈if '(' == c || '[' == c || '{' == c {stack.push(c);}// 如果是结束符号,则判断是否平衡if ')' == c || ']' == c || '}' == c {if stack.is_empty() {balance = false;} else {let top = stack.pop().unwrap();if !par_match(top, c) {balance = false;}}}// 非括号字符直接跳过index += 1;}balance && stack.is_empty()
}

运行结果:

在这里插入图片描述

相关文章:

Rust 数据结构与算法:3栈:用栈实现符号匹配

1、符号匹配 如&#xff1a; (56)(78)/(43)、{ { ( [ ] [ ])}}、(ab)(c*d)func() 等各类语句的符号匹配。 这里我们关注的不是数字而是括号&#xff0c;因为括号更改了操作优先级&#xff0c;限定了语言的语义&#xff0c;这是非常重要的。如果括号不完整&#xff0c;那么整个…...

用ESP8266快速实现WIFI红外遥控器(SoC模式)

1&#xff0c;硬件结构图 主要使用了esp8266 wifi模块和红外串口通讯模块。有了红外串口通讯模块&#xff0c;省去了单片机的串口通讯和红外编码程序&#xff0c;大大缩短开发时间。因为红外通讯模块不支持3.3VTTL电平&#xff0c;所以两个模块之间加了一个2路电平转换模块&…...

微服务OAuth 2.1认证授权可行性方案(Spring Security 6)

文章目录 一、背景二、微服务架构介绍三、认证服务器1. 数据库创建2. 新建模块3. 导入依赖和配置4. 安全认证配置类 四、认证服务器测试1. AUTHORIZATION_CODE&#xff08;授权码模式&#xff09;1. 获取授权码2. 获取JWT 2. CLIENT_CREDENTIALS(客户端凭证模式) 五、Gateway1.…...

Maui blazor ios 按设备类型设置是否启用safeArea

需求&#xff0c;新做了个app&#xff0c; 使用的是maui blazor技术&#xff0c;里面用了渐变背景&#xff0c;在默认启用SafeArea情况下&#xff0c;底部背景很突兀 由于现版本maui在SafeArea有点bug&#xff0c;官方教程的<ContentPage SafeAreafalse不生效&#xff0c;于…...

C#系列-使用 Minio 做图片服务器实现图片上传 和下载(13)

1、Minio 服务器下载和安装 要在本地安装和运行 MinIO 服务器&#xff0c;你可以按照以下 步骤进行操作&#xff1a; 1. 访问 MinIO 的官方网站&#xff1a;https://min.io/&#xff0c;然后 点击页面上的”Download”按钮。 2. 在下载页面上&#xff0c;选择适合你操作系统的 …...

生活篇——华为手机去除负一屏

华为手机去除如下图的恶心负一屏 打开华为的应用市场app 进入&#xff1a;我的-设置-国家/地区&#xff08;改为俄罗斯&#xff09;-进入智慧助手检查更新并更新智慧助手。 然后重复开始的操作&#xff0c;将地区改回中国&#xff0c;这样就没有负一屏了。...

2024牛客寒假算法基础集训营2-c Tokitsukaze and Min-Max XOR

来源 题目 Tokitsukaze 有一个长度为 n 的序列 a1,a2,…,an和一个整数 k。 她想知道有多少种序列 b1,b2,…,bm满足&#xff1a; 其中 ⊕\oplus⊕ 为按位异或&#xff0c;具体参见 百度百科&#xff1a;异或 答案可能很大&#xff0c;请输出  mod1e97 后的结果。 输入描述…...

C语言:指针的基础详解

目录 1. 内存 2. 取地址& 3. 指针变量 4. 解引用 4.1 *解引用 4.2 []解引用 4.3 ->解引用 5. 指针变量的大小 5.1 结论 6. 指针运算 7. void* 指针 8. const修饰指针 8.1 const修饰变量 8.2 const修饰指针变量 8.3 结论 9. 野指针 9.1 为什么会出现野指…...

PHP+vue+mysql校园学生社团管理系统574cc

运行环境:phpstudy/wamp/xammp等 开发语言&#xff1a;php 后端框架&#xff1a;Thinkphp 前端框架&#xff1a;vue.js 服务器&#xff1a;apache 数据库&#xff1a;mysql 数据库工具&#xff1a;Navicat/phpmyadmin 前台功能&#xff1a; 首页&#xff1a;展示社团信息和活动…...

VS Code中主程序C文件引用了另一个.h头文件,编译时报错找不到函数

目录 一、问题描述二、问题原因三、解决方法四、扩展五、通过CMake进行配置 一、问题描述 VS Code中主程序C文件引用了另一个.h头文件&#xff0c;编译时报错找不到函数 主程序 main.c #include <stdio.h> #include "sumaa.h"int main(int, char**){printf(&q…...

边缘计算:重塑数字世界的未来

引言 随着物联网&#xff08;IoT&#xff09;设备的激增和5G网络的普及&#xff0c;我们正站在一个计算模式的新纪元门槛上——边缘计算。这一技术范式将数据处理和分析推向网络的边缘&#xff0c;即设备或终端&#xff0c;为实时性要求较高的应用提供了前所未有的可能性。 目…...

2024 前端面试题 附录3

这里记录的是昨天和今天原篇的知识点补充 原篇地址&#xff1a; 2024 前端面试题&#xff08;GPT回答 示例代码 解释&#xff09;No.41 - No.60 2024 前端面试题&#xff08;GPT回答 示例代码 解释&#xff09;No.61 - No.100 2024 前端面试题&#xff08;GPT回答 示例代…...

[Vue warn]: Duplicate keys detected: ‘1‘. This may cause an update error.

[Vue warn]: Duplicate keys detected: ‘1‘. This may cause an update error.——> Vue报错&#xff0c;key关键字不唯一&#xff1a; 解决办法&#xff1a;修改一下重复的id值&#xff01;&#xff01;&#xff01;...

Docker-Learn(二)保存、导入、使用Docker镜像

1.保存镜像 根据上一节内容&#xff0c;将创建好镜像进行保存&#xff0c;需要退出当前的已经在运行的docer命令行中断里面&#xff0c;可以通过在终端里面输入指令exit或者按下键盘上的 ctrlD建退出&#xff1a; 回到自己的终端里面&#xff0c;输入指令&#xff1a; docker…...

第三百一十五回

文章目录 1. 概念介绍2. 基本用法3. 补充用法4. 内容总结 我们在上一章回中介绍了"再谈ListView中的分隔线"&#xff0c;本章回中将介绍showMenu的用法.闲话休提&#xff0c;让我们一起Talk Flutter吧。 1. 概念介绍 我们在第一百六十三回中介绍了showMenu相关的内容…...

区块链(一): 以太坊基础知识

目录 什么是区块链&#xff1f;什么是以太坊&#xff1f;什么是加密货币&#xff1f;以太坊与比特币有什么不同&#xff1f;以太坊能做什么&#xff1f;什么是智能合约&#xff1f;以太坊社区以太坊白皮书 什么是区块链&#xff1f; 区块链是一个交易数据库&#xff0c;在网络…...

高级FPGA开发之基础协议PCIe

基础协议之PCIe部分 一、TLP包的包头 在PCIe的系统中&#xff0c;tlp包的包头的结构有许多部分是相似的&#xff0c;通过掌握这些常规的包头&#xff0c;能帮助理解在PCIe总线上各个设备之间如何进行数据的收发。 通用的字段 通用字段作用Fmt决定了包头是3DW还是3DW&#xff…...

Vue核心基础1:数据代理

1 回顾Object.defineProperty方法 let str hello const person {name: 张三,age: 18 } Object.defineProperty(person, sex, {// value: 男,// enumerable: true, // 控制属性是否可以枚举&#xff0c;默认值是false// writable: true, // 控制属性是否可以被修改&#xff0…...

12 ABC串口接收原理与思路

1. 串口接收原理 基本原理&#xff1a;通过数据起始位判断要是否要开始接收的数据&#xff0c;通过采样的方式确定每一位数据是0还是1。 如何判断数据起始位到来&#xff1a;通过边沿检测电路检测起始信号的下降沿 如何采样&#xff1a;一位数据采多次&#xff0c;统计得到高…...

leetcode(二分查找)34.在排序数组中查找元素的第一个和最后一个位置(C++详细解释)DAY11

文章目录 1.题目示例提示 2.解答思路3.实现代码结果 4.总结 1.题目 给你一个按照非递减顺序排列的整数数组 nums&#xff0c;和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。 如果数组中不存在目标值 target&#xff0c;返回 [-1, -1]。 你必须设计…...

变量 varablie 声明- Rust 变量 let mut 声明与 C/C++ 变量声明对比分析

一、变量声明设计&#xff1a;let 与 mut 的哲学解析 Rust 采用 let 声明变量并通过 mut 显式标记可变性&#xff0c;这种设计体现了语言的核心哲学。以下是深度解析&#xff1a; 1.1 设计理念剖析 安全优先原则&#xff1a;默认不可变强制开发者明确声明意图 let x 5; …...

Leetcode 3577. Count the Number of Computer Unlocking Permutations

Leetcode 3577. Count the Number of Computer Unlocking Permutations 1. 解题思路2. 代码实现 题目链接&#xff1a;3577. Count the Number of Computer Unlocking Permutations 1. 解题思路 这一题其实就是一个脑筋急转弯&#xff0c;要想要能够将所有的电脑解锁&#x…...

EtherNet/IP转DeviceNet协议网关详解

一&#xff0c;设备主要功能 疆鸿智能JH-DVN-EIP本产品是自主研发的一款EtherNet/IP从站功能的通讯网关。该产品主要功能是连接DeviceNet总线和EtherNet/IP网络&#xff0c;本网关连接到EtherNet/IP总线中做为从站使用&#xff0c;连接到DeviceNet总线中做为从站使用。 在自动…...

Reasoning over Uncertain Text by Generative Large Language Models

https://ojs.aaai.org/index.php/AAAI/article/view/34674/36829https://ojs.aaai.org/index.php/AAAI/article/view/34674/36829 1. 概述 文本中的不确定性在许多语境中传达,从日常对话到特定领域的文档(例如医学文档)(Heritage 2013;Landmark、Gulbrandsen 和 Svenevei…...

Netty从入门到进阶(二)

二、Netty入门 1. 概述 1.1 Netty是什么 Netty is an asynchronous event-driven network application framework for rapid development of maintainable high performance protocol servers & clients. Netty是一个异步的、基于事件驱动的网络应用框架&#xff0c;用于…...

GitHub 趋势日报 (2025年06月06日)

&#x1f4ca; 由 TrendForge 系统生成 | &#x1f310; https://trendforge.devlive.org/ &#x1f310; 本日报中的项目描述已自动翻译为中文 &#x1f4c8; 今日获星趋势图 今日获星趋势图 590 cognee 551 onlook 399 project-based-learning 348 build-your-own-x 320 ne…...

基于PHP的连锁酒店管理系统

有需要请加文章底部Q哦 可远程调试 基于PHP的连锁酒店管理系统 一 介绍 连锁酒店管理系统基于原生PHP开发&#xff0c;数据库mysql&#xff0c;前端bootstrap。系统角色分为用户和管理员。 技术栈 phpmysqlbootstrapphpstudyvscode 二 功能 用户 1 注册/登录/注销 2 个人中…...

嵌入式常见 CPU 架构

架构类型架构厂商芯片厂商典型芯片特点与应用场景PICRISC (8/16 位)MicrochipMicrochipPIC16F877A、PIC18F4550简化指令集&#xff0c;单周期执行&#xff1b;低功耗、CIP 独立外设&#xff1b;用于家电、小电机控制、安防面板等嵌入式场景8051CISC (8 位)Intel&#xff08;原始…...

HybridVLA——让单一LLM同时具备扩散和自回归动作预测能力:训练时既扩散也回归,但推理时则扩散

前言 如上一篇文章《dexcap升级版之DexWild》中的前言部分所说&#xff0c;在叠衣服的过程中&#xff0c;我会带着团队对比各种模型、方法、策略&#xff0c;毕竟针对各个场景始终寻找更优的解决方案&#xff0c;是我个人和我司「七月在线」的职责之一 且个人认为&#xff0c…...

若依登录用户名和密码加密

/*** 获取公钥&#xff1a;前端用来密码加密* return*/GetMapping("/getPublicKey")public RSAUtil.RSAKeyPair getPublicKey() {return RSAUtil.rsaKeyPair();}新建RSAUti.Java package com.ruoyi.common.utils;import org.apache.commons.codec.binary.Base64; im…...