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

Rust 数据结构与算法:5栈:用栈实现前缀、中缀、后缀表达式

3、前缀、中缀和后缀表达式

计算机是从左到右处理数据的,类似(A + (B * C))这样的完全括号表达式,计算机如何跳到内部括号计算乘法,然后跳到外部括号计算加法呢?

一种直观的方法是将运算符移到操作数外,分离运算符和操作数。计算时先取运算符再取操作数,计算结果则作为当前值参与后面的运算,直到完成对整个表达式的计算。

可将中缀表达式A + B中的“+”移出来,既可以放前面,也可以放后面,得到的将是+ A B和A B +。这两种不同的表达式分别被称为前缀表达式和后缀表达式。

前缀表达式要求所有运算符在处理的两个操作数之前,后缀表达式则要求所有运算符在相应的操作数之后。

在这里插入图片描述

前缀、中缀和后缀表达式

在这里插入图片描述

将中缀表达式转换为前缀和后缀表达式

这里规定:运算符只有+ - * /,操作数则被定义为任何大写字母A~Z或数字0~9。

代码如下:

#[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()}
}use std::collections::HashMap;fn main() {let infix = "( A + B ) * ( C + D )";let postfix = infix_to_postfix(infix);match postfix {Some(val) => {println!("{infix} -> {val}");},None => {println!("{infix} is not a correct infix string");}}let infix = "( 1 + 2 ) * 3";let postfix = infix_to_postfix(infix);match postfix {Some(val) => {println!("{infix} -> {val}");},None => {println!("{infix} is not a correct infix string");}}
}// 中缀转后缀
fn infix_to_postfix(infix:&str) -> Option<String> {// 括号匹配检验if !par_checker3(infix) { return None;};// 设置各个运算符的优先级let mut prec = HashMap::new();//  HashMap<K, V> 类型储存了一个键类型 K 对应一个值类型 V 的映射。它通过一个 哈希函数(hashing function)来实现映射,决定如何将键和值放入内存中。prec.insert("(", 1);prec.insert(")", 1);prec.insert("+", 2);prec.insert("-", 2);prec.insert("*", 3);prec.insert("/", 3);// ops 用于保存运算符, postfix 用于保存后缀表达式let mut ops = Stack::new(); // 保存运算符let mut postfix = Vec::new(); // 保存后缀表达式for token in infix.split_whitespace() { // 按空格分割字符串切片// 将数字 0 - 9 和 大写字母 A - Z 入栈if ("A" <= token && token <= "Z") || ("0" <= token && token <= "9") {postfix.push(token); // 如果是字符或数字就存入 postfix}else if "(" == token {// 遇到开始符号,将运算符入栈ops.push(token); // 如果是开始括号运算符 ( 就存储 ops}else if ")" == token {// 比如 infix 为 (1 + 2) * 3,此时 postfix 类似为 [1,2],ops 类似为 [(,+]  // 遇到结束符号,将操作数入栈let mut top = ops.pop().unwrap(); // 如果是结束括号运算符 就去 ops 中匹配 对应的 开始 括号运算符 此时 ops 类似为 [(],因为 + 已经被 pop 出去了while top !="(" { // 如果匹配到的不是 ( 开始括号运算符,则说明是 + - * / 运算符 此时 top 比如为 +postfix.push(top); // 将 + - * / 运算符入栈至 postfix,比如 infix 为 (1 + 2) * 3,此时 postfix 类似为 [1,2,+]top = ops.pop().unwrap(); // 此时 ops 类似为 [],top = "(",到这里 while 就结束了 因为 top = "("}// 到这里时 ops 类似为 [],infix 为 (1 + 2) * 3 中的 () 就被丢弃了,而 postfix 已经为,如:[1,2,+]}else {// + - * / 运算符// 比较运算符的优先级以决定是否将运算符添加到 postfix 列表中while (!ops.is_empty()) && (prec[ops.peek().unwrap()] >= prec[token]) {postfix.push(ops.pop().unwrap()); // 比如 peek 是 *,而 当前 token 是 + ,则直接把 * 放入 postfix }ops.push(token); // 此时将 * push 了进去// 此时 ops 如 [*]}}// 比如:infix 为 (1 + 2) * 3//  此时 ops 如 [*]// 此时 postfix 如 [1,2,+,3]// 将剩下的操作数入栈while !ops.is_empty() {postfix.push(ops.pop().unwrap()); // 此时 postfix 如 [1,2,+,3,*]}// 出栈并组成字符串let mut postfix_str = "".to_string();for c in postfix {postfix_str += &c.to_string();postfix_str += " "; // 加上空格}Some(postfix_str)
}// 同时检测多种开始符号和结束符号是否匹配
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 数据结构与算法:5栈:用栈实现前缀、中缀、后缀表达式

3、前缀、中缀和后缀表达式 计算机是从左到右处理数据的&#xff0c;类似(A (B * C))这样的完全括号表达式&#xff0c;计算机如何跳到内部括号计算乘法&#xff0c;然后跳到外部括号计算加法呢&#xff1f; 一种直观的方法是将运算符移到操作数外&#xff0c;分离运算符和操…...

作业day6

数据库 sqlite3 sq.db 如果sq.db存在则直接打开sq.db数据库&#xff0c;如果不存在则先创建再打开; ​ 系统命令 需要以 . 开头&#xff0c;不需要以 ; 结尾 .quit 退出数据库 .exit 退出数据库 .help 显示帮助信息&#xff0c;获取所有系统命令; ​ .table 查看当前数据…...

前方预警!2024年七大网络安全威胁

新颖创新技术的兴起和迅速采用已极大地改变了各行各业的全球网络安全和合规格局&#xff0c;比如生成式人工智能、无代码应用程序、自动化和物联网等新技术。 网络犯罪分子正转而采用新的技术、工具和软件来发动攻击&#xff0c;并造成更大的破坏。因此&#xff0c;《2023年网…...

绿色化 数据库 MongoDB 和 mysql 安装

绿色化 数据库 MongoDB 和 mysql 安装 【1.1】 前言 为什么要绿色化 安装呢&#xff1f;因为系统老升级&#xff0c;老重装&#xff01;&#xff01;也方便了解下数据库配置和库在那 绿色软件喜欢一般放在 D盘tools目录里 D:\tools\ 数据库 MongoDB D:\tools\MongoDB 数…...

npm install 一直卡着不动如何解决

目录 方式一&#xff1a;方式二&#xff1a; 方式一&#xff1a; npm cache clean --force npm config set registry https://registry.npmmirror.com npm install下面是简单的解释&#xff1a; &#x1f340;1、强制清理 npm 缓存 npm cache clean --force&#x1f340;2、设…...

电路设计(15)——篮球赛24秒违例倒计时报警器的proteus仿真

1.设计要求 设计、制作一个篮球赛24秒违例倒计时报警器。要求&#xff1a; &#xff08;1&#xff09;具有倒计时功能。可完整实现从“24”秒开始依序倒计时并显示倒计时过程&#xff0c;显示时间间隔为1秒。 &#xff08;2&#xff09;具有消隐功能。当“24”秒倒计时…...

golang 集成sentry:http.Client

http.Client 是 Go 标准库 HTTP 客户端实现&#xff0c; sentry-go也没有这个组件&#xff0c;所以需要自己实现。 我们只需要对 http.Transport 进行包装即可&#xff0c; 完整代码如下 package mainimport ("bytes""fmt""io""log"&…...

设计链表(不难,代码稍微多一点)

设计链表 在链表类中实现这些功能&#xff1a; get(index)&#xff1a;获取链表中第 index 个节点的值。如果索引无效&#xff0c;则返回-1。addAtHead(val)&#xff1a;在链表的第一个元素之前添加一个值为 val 的节点。插入后&#xff0c;新节点将成为链表的第一个节点。ad…...

[GXYCTF2019]禁止套娃

进来发现只有这句话&#xff0c;习惯性访问一下flag.php&#xff0c;发现不是404&#xff0c;那就证明flag就在这了&#xff0c;接下来要想办法拿到flag.php的源码。 这道题是.git文件泄露网页源码&#xff0c;githack拿到index.php源码 这里观察到多次判断&#xff0c;首先要…...

ubuntu下如何查看显卡及显卡驱动

ubuntu下如何查看显卡及显卡驱动 使用nvidia-smi 工具查看 查看显卡型号nvida-smi -L $ nvidia-smi -L GPU 0: NVIDIA GeForce RTX 3050 4GB Laptop GPU (UUID: GPU-4cf7b7cb-f103-bf56-2d59-304f8996e28c)当然直接使用nvida-smi 命令可以查看更多信息 $ nvidia-smi Mon Fe…...

【图论经典题目讲解】CF786B - Legacy 一道线段树优化建图的经典题目

C F 786 B − L e g a c y \mathrm{CF786B - Legacy} CF786B−Legacy D e s c r i p t i o n \mathrm{Description} Description 给定 1 1 1 张 n n n 个点的有向图&#xff0c;初始没有边&#xff0c;接下来有 q q q 次操作&#xff0c;形式如下&#xff1a; 1 u v w 表示…...

【AIGC】Stable Diffusion的采样器入门

在 Stable Diffusion 中&#xff0c;采样器&#xff08;Sampler&#xff09;是指用于生成图像的一种技术或方法&#xff0c;它决定了模型如何从潜在空间中抽样并生成图像。采样器在生成图像的过程中起着重要作用&#xff0c;影响着生成图像的多样性、质量和创造性。以下是对 St…...

【Python】通过conda安装Python的IDE

背景 系统&#xff1a;win11 软件&#xff1a;anaconda Navigator 问题现象&#xff1a;①使用Navigator安装jupyter notebook以及Spyder IDE 一直转圈。②然后进入anaconda prompt执行conda install jupyter notebook一直卡在Solving environment/-\。 类似问题&#xff1a; …...

基于HTML5实现动态烟花秀效果(含音效和文字)实战

目录 前言 一、烟花秀效果功能分解 1、功能分解 2、界面分解 二、HTML功能实现 1、html界面设计 2、背景音乐和燃放触发 3、燃放控制 4、对联展示 5、脚本引用即文本展示 三、脚本调用及实现 1、烟花燃放 2、燃放响应 3、烟花canvas创建 4、燃放声音控制 5、实际…...

「数据结构」栈和队列

栈 栈的基本概念 定义 栈是只允许在一端进行插入或删除操作的线性表栈顶&#xff1a;线性表允许进行插入删除的那一端栈底&#xff1a;固定的&#xff0c;不允许进行插入和删除的另一端空栈&#xff1a;不含任何元素特点&#xff1a;后进先出&#xff08;LIFO&#xff09; 基…...

【机器学习笔记】5 机器学习实践

数据集划分 子集划分 训练集&#xff08;Training Set&#xff09;&#xff1a;帮助我们训练模型&#xff0c;简单的说就是通过训练集的数据让我们确定拟合曲线的参数。 验证集&#xff08;Validation Set&#xff09;&#xff1a;也叫做开发集&#xff08; Dev Set &#xf…...

C++ //练习 7.5 在你的Person类中提供一些操作使其能够返回姓名和住址。这些函数是否应该是const的呢?解释原因。

C Primer&#xff08;第5版&#xff09; 练习 7.5 练习 7.5 在你的Person类中提供一些操作使其能够返回姓名和住址。这些函数是否应该是const的呢&#xff1f;解释原因。 环境&#xff1a;Linux Ubuntu&#xff08;云服务器&#xff09; 工具&#xff1a;vim 解释 姓名大概…...

python系统学习Day2

section3 python Foudamentals part one&#xff1a;data types and variables 数据类型&#xff1a;整数、浮点数、字符串、布尔值、空值 #整型&#xff0c;没有大小限制 >>>9 / 3 #3.0 >>>10 // 3 #3 地板除 >>>10 % 3 #1 取余#浮点型&#xff…...

学习笔记——ENM模拟

学习笔记——ENM模拟 文章目录 前言一、文献一1. 材料与方法1.1. 大致概念1.2. 生态模型的构建1.2.1. 数据来源&#xff1a;1.2.2. 数据处理&#xff1a;1.2.3. 模型参数优化&#xff1a; 1.3. 适生情况预测1.3.1. 预测模型构建1.3.2. 适生区划分 1.4. 模型的评估与验证 2. 结果…...

数值类型的运算方式总结

提纲1&#xff1a;常见的位运算使用场景 提纲2&#xff1a;整数类型运算时的类型溢出问题&#xff0c;产生原因以及解决办法 提纲3&#xff1a;浮点类型运算时的精度丢失问题&#xff0c;产生原因以及解决办法 数值类型&#xff08;6种&#xff09;分为&#xff1a; 整型&…...

RestClient

什么是RestClient RestClient 是 Elasticsearch 官方提供的 Java 低级 REST 客户端&#xff0c;它允许HTTP与Elasticsearch 集群通信&#xff0c;而无需处理 JSON 序列化/反序列化等底层细节。它是 Elasticsearch Java API 客户端的基础。 RestClient 主要特点 轻量级&#xff…...

Docker 离线安装指南

参考文章 1、确认操作系统类型及内核版本 Docker依赖于Linux内核的一些特性&#xff0c;不同版本的Docker对内核版本有不同要求。例如&#xff0c;Docker 17.06及之后的版本通常需要Linux内核3.10及以上版本&#xff0c;Docker17.09及更高版本对应Linux内核4.9.x及更高版本。…...

树莓派超全系列教程文档--(62)使用rpicam-app通过网络流式传输视频

使用rpicam-app通过网络流式传输视频 使用 rpicam-app 通过网络流式传输视频UDPTCPRTSPlibavGStreamerRTPlibcamerasrc GStreamer 元素 文章来源&#xff1a; http://raspberry.dns8844.cn/documentation 原文网址 使用 rpicam-app 通过网络流式传输视频 本节介绍来自 rpica…...

UE5 学习系列(三)创建和移动物体

这篇博客是该系列的第三篇&#xff0c;是在之前两篇博客的基础上展开&#xff0c;主要介绍如何在操作界面中创建和拖动物体&#xff0c;这篇博客跟随的视频链接如下&#xff1a; B 站视频&#xff1a;s03-创建和移动物体 如果你不打算开之前的博客并且对UE5 比较熟的话按照以…...

【项目实战】通过多模态+LangGraph实现PPT生成助手

PPT自动生成系统 基于LangGraph的PPT自动生成系统&#xff0c;可以将Markdown文档自动转换为PPT演示文稿。 功能特点 Markdown解析&#xff1a;自动解析Markdown文档结构PPT模板分析&#xff1a;分析PPT模板的布局和风格智能布局决策&#xff1a;匹配内容与合适的PPT布局自动…...

postgresql|数据库|只读用户的创建和删除(备忘)

CREATE USER read_only WITH PASSWORD 密码 -- 连接到xxx数据库 \c xxx -- 授予对xxx数据库的只读权限 GRANT CONNECT ON DATABASE xxx TO read_only; GRANT USAGE ON SCHEMA public TO read_only; GRANT SELECT ON ALL TABLES IN SCHEMA public TO read_only; GRANT EXECUTE O…...

江苏艾立泰跨国资源接力:废料变黄金的绿色供应链革命

在华东塑料包装行业面临限塑令深度调整的背景下&#xff0c;江苏艾立泰以一场跨国资源接力的创新实践&#xff0c;重新定义了绿色供应链的边界。 跨国回收网络&#xff1a;废料变黄金的全球棋局 艾立泰在欧洲、东南亚建立再生塑料回收点&#xff0c;将海外废弃包装箱通过标准…...

elementUI点击浏览table所选行数据查看文档

项目场景&#xff1a; table按照要求特定的数据变成按钮可以点击 解决方案&#xff1a; <el-table-columnprop"mlname"label"名称"align"center"width"180"><template slot-scope"scope"><el-buttonv-if&qu…...

Docker拉取MySQL后数据库连接失败的解决方案

在使用Docker部署MySQL时&#xff0c;拉取并启动容器后&#xff0c;有时可能会遇到数据库连接失败的问题。这种问题可能由多种原因导致&#xff0c;包括配置错误、网络设置问题、权限问题等。本文将分析可能的原因&#xff0c;并提供解决方案。 一、确认MySQL容器的运行状态 …...

DeepSeek源码深度解析 × 华为仓颉语言编程精粹——从MoE架构到全场景开发生态

前言 在人工智能技术飞速发展的今天&#xff0c;深度学习与大模型技术已成为推动行业变革的核心驱动力&#xff0c;而高效、灵活的开发工具与编程语言则为技术创新提供了重要支撑。本书以两大前沿技术领域为核心&#xff0c;系统性地呈现了两部深度技术著作的精华&#xff1a;…...