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

深入解析：Rust 练习册 ：Matching Brackets与栈数据结构

news 2026/3/27 4:24:32

在编程和文本处理中，括号匹配是一个经典问题，广泛应用于编译器、解释器、文本编辑器等场景。在 Exercism 的 “matching-brackets” 练习中，我们需要实现一个函数来检查字符串中的括号是否正确匹配。这不仅能帮助我们掌握栈数据结构的应用，还能深入学习Rust中的字符处理、数据结构实现和算法设计。

什么是括号匹配问题？

括号匹配问题是检查文本中各种类型的括号是否正确配对的问题。需要检查的括号类型包括：

  • 圆括号：( )
  • 方括号：[ ]
  • 花括号：{ }

正确的括号匹配需要满足以下条件：

  1. 每个开括号都有对应的闭括号
  2. 每个闭括号都有对应的开括号
  3. 括号的嵌套顺序正确

例如：

  • "[]" 是正确的
  • "[()]" 是正确的
  • "([)]" 是错误的（交叉嵌套）
  • "([)" 是错误的（缺少匹配）

括号匹配在以下领域有应用：

  1. 编译器：检查程序语法中的括号匹配
  2. 文本编辑器：高亮显示匹配的括号
  3. 数学表达式：验证数学表达式的正确性
  4. HTML/XML解析：检查标签的正确嵌套

让我们先看看练习提供的函数签名：

pub fn brackets_are_balanced(string: &str) -> bool {
unimplemented!(
"Check if the string \"{}\" contains balanced brackets",
string
);
}

我们需要实现一个函数，检查给定字符串中的括号是否正确匹配。

设计分析

1. 核心要求

  1. 字符识别：识别各种类型的括号字符
  2. 匹配检查：检查括号是否正确配对
  3. 嵌套处理：处理嵌套的括号结构
  4. 忽略非括号字符：忽略文本中的其他字符

2. 技术要点

  1. 栈数据结构：使用栈来跟踪未匹配的开括号
  2. 字符处理：高效处理字符串中的字符
  3. 匹配逻辑：实现正确的括号匹配逻辑
  4. 边界情况：处理各种边界情况

完整实现

1. 基础实现

pub fn brackets_are_balanced(string: &str) -> bool {
let mut stack = Vec::new();
for c in string.chars() {
match c {
'(' | '[' | '{' => stack.push(c),
')' => {
if stack.pop() != Some('(') {
return false;
}
}
']' => {
if stack.pop() != Some('[') {
return false;
}
}
'}' => {
if stack.pop() != Some('{') {
return false;
}
}
_ => (), // 忽略其他字符
}
}
stack.is_empty()
}

2. 优化实现

pub fn brackets_are_balanced(string: &str) -> bool {
let mut stack = Vec::new();
for c in string.chars() {
match c {
'(' | '[' | '{' => stack.push(c),
')' | ']' | '}' => {
let expected = match c {
')' => '(',
']' => '[',
'}' => '{',
_ => unreachable!(),
};
if stack.pop() != Some(expected) {
return false;
}
}
_ => (), // 忽略其他字符
}
}
stack.is_empty()
}

3. 使用HashMap的实现

use std::collections::HashMap;
pub fn brackets_are_balanced(string: &str) -> bool {
let mut stack = Vec::new();
let mut pairs = HashMap::new();
pairs.insert(')', '(');
pairs.insert(']', '[');
pairs.insert('}', '{');
for c in string.chars() {
match c {
'(' | '[' | '{' => stack.push(c),
')' | ']' | '}' => {
if stack.pop() != Some(*pairs.get(&c).unwrap()) {
return false;
}
}
_ => (), // 忽略其他字符
}
}
stack.is_empty()
}

测试用例分析

通过查看测试用例，我们可以更好地理解需求：

#[test]
fn paired_square_brackets() {
assert!(brackets_are_balanced("[]"));
}

成对的方括号是平衡的。

#[test]
fn empty_string() {
assert!(brackets_are_balanced(""));
}

空字符串是平衡的。

#[test]
fn unpaired_brackets() {
assert!(!brackets_are_balanced("[["));
}

未成对的括号是不平衡的。

#[test]
fn wrong_ordered_brackets() {
assert!(!brackets_are_balanced("}{"));
}

顺序错误的括号是不平衡的。

#[test]
fn paired_with_whitespace() {
assert!(brackets_are_balanced("{ }"));
}

包含空白字符的成对括号是平衡的。

#[test]
fn simple_nested_brackets() {
assert!(brackets_are_balanced("{[]}"));
}

简单的嵌套括号是平衡的。

#[test]
fn paired_and_nested_brackets() {
assert!(brackets_are_balanced("([{}({}[])])"));
}

成对且嵌套的括号是平衡的。

#[test]
fn unopened_closing_brackets() {
assert!(!brackets_are_balanced("{[)][]}"));
}

未正确开启的闭括号是不平衡的。

#[test]
fn math_expression() {
assert!(brackets_are_balanced("(((185 + 223.85) * 15) - 543)/2"));
}

数学表达式中的括号是平衡的。

性能优化版本

考虑性能的优化实现：

pub fn brackets_are_balanced(string: &str) -> bool {
let mut stack = Vec::with_capacity(string.len() / 2); // 预分配容量
for c in string.chars() {
match c {
'(' | '[' | '{' => stack.push(c),
')' => {
if stack.pop() != Some('(') {
return false;
}
}
']' => {
if stack.pop() != Some('[') {
return false;
}
}
'}' => {
if stack.pop() != Some('{') {
return false;
}
}
_ => (), // 忽略其他字符
}
}
stack.is_empty()
}
// 使用字节数组的高性能版本
pub fn brackets_are_balanced_bytes(string: &str) -> bool {
let mut stack = Vec::with_capacity(string.len() / 2);
let bytes = string.as_bytes();
for &byte in bytes {
match byte {
b'(' | b'[' | b'{' => stack.push(byte),
b')' => {
if stack.pop() != Some(b'(') {
return false;
}
}
b']' => {
if stack.pop() != Some(b'[') {
return false;
}
}
b'}' => {
if stack.pop() != Some(b'{') {
return false;
}
}
_ => (), // 忽略其他字符
}
}
stack.is_empty()
}
// 提前退出优化版本
pub fn brackets_are_balanced_optimized(string: &str) -> bool {
let mut stack = Vec::with_capacity(string.len() / 2);
// 统计开括号和闭括号数量，提前发现明显不平衡的情况
let mut open_count = 0;
let mut close_count = 0;
for c in string.chars() {
match c {
'(' | '[' | '{' => {
open_count += 1;
stack.push(c);
}
')' | ']' | '}' => {
close_count += 1;
if close_count > open_count {
return false; // 闭括号多于开括号
}
let expected = match c {
')' => '(',
']' => '[',
'}' => '{',
_ => unreachable!(),
};
if stack.pop() != Some(expected) {
return false;
}
}
_ => (), // 忽略其他字符
}
}
open_count == close_count && stack.is_empty()
}

错误处理和边界情况

考虑更多边界情况的实现：

#[derive(Debug, PartialEq)]
pub enum BracketError {
UnmatchedClosingBracket,
UnmatchedOpeningBracket,
MismatchedBracket,
}
pub fn check_brackets_detailed(string: &str) -> Result<bool, BracketError> {let mut stack = Vec::new();let mut open_count = 0;let mut close_count = 0;for c in string.chars() {match c {'(' | '[' | '{' => {open_count += 1;stack.push(c);}')' | ']' | '}' => {close_count += 1;if close_count > open_count {return Err(BracketError::UnmatchedClosingBracket);}let expected = match c {')' => '(',']' => '[','}' => '{',_ => unreachable!(),};if stack.pop() != Some(expected) {return Err(BracketError::MismatchedBracket);}}_ => (), // 忽略其他字符}}if !stack.is_empty() {Err(BracketError::UnmatchedOpeningBracket)} else {Ok(true)}}pub fn brackets_are_balanced(string: &str) -> bool {check_brackets_detailed(string).unwrap_or(false)}// 支持自定义括号类型的版本pub fn brackets_are_balanced_custom(string: &str, pairs: &[(&char, &char)]) -> bool {let mut stack = Vec::new();let opening_brackets: Vec<char> = pairs.iter().map(|(open, _)| **open).collect();let closing_to_opening: std::collections::HashMap<char, char> =pairs.iter().map(|(open, close)| (**close, **open)).collect();for c in string.chars() {if opening_brackets.contains(&c) {stack.push(c);} else if closing_to_opening.contains_key(&c) {let expected = *closing_to_opening.get(&c).unwrap();if stack.pop() != Some(expected) {return false;}}}stack.is_empty()}

扩展功能

基于基础实现，我们可以添加更多功能：

pub struct BracketChecker {
stack: Vec<char>,}impl BracketChecker {pub fn new() -> Self {BracketChecker {stack: Vec::new(),}}pub fn is_balanced(&self, string: &str) -> bool {let mut checker = BracketChecker::new();checker.check(string).is_ok()}pub fn check(&mut self, string: &str) -> Result<bool, BracketError> {self.stack.clear();for c in string.chars() {match c {'(' | '[' | '{' => self.stack.push(c),')' => {if self.stack.pop() != Some('(') {return Err(BracketError::UnmatchedClosingBracket);}}']' => {if self.stack.pop() != Some('[') {return Err(BracketError::UnmatchedClosingBracket);}}'}' => {if self.stack.pop() != Some('{') {return Err(BracketError::UnmatchedClosingBracket);}}_ => (), // 忽略其他字符}}if self.stack.is_empty() {Ok(true)} else {Err(BracketError::UnmatchedOpeningBracket)}}// 获取不匹配括号的位置信息pub fn find_mismatch_positions(&self, string: &str) -> Vec<usize> {let mut stack = Vec::new();let mut mismatch_positions = Vec::new();for (i, c) in string.chars().enumerate() {match c {'(' | '[' | '{' => stack.push((c, i)),')' | ']' | '}' => {let expected = match c {')' => '(',']' => '[','}' => '{',_ => unreachable!(),};if let Some((last_char, _)) = stack.pop() {if last_char != expected {mismatch_positions.push(i);}} else {mismatch_positions.push(i); // 多余的闭括号}}_ => (),}}// 剩余未匹配的开括号位置for (_, pos) in stack {mismatch_positions.push(pos);}mismatch_positions.sort();mismatch_positions}// 获取嵌套深度信息pub fn get_nesting_depth(&self, string: &str) -> usize {let mut max_depth = 0;let mut current_depth = 0;for c in string.chars() {match c {'(' | '[' | '{' => {current_depth += 1;max_depth = max_depth.max(current_depth);}')' | ']' | '}' => {if current_depth > 0 {current_depth -= 1;}}_ => (),}}max_depth}}#[derive(Debug, PartialEq)]pub enum BracketError {UnmatchedClosingBracket,UnmatchedOpeningBracket,MismatchedBracket,}// 便利函数pub fn brackets_are_balanced(string: &str) -> bool {BracketChecker::new().is_balanced(string)}

实际应用场景

括号匹配在实际开发中有以下应用：

  1. 编译器和解释器：检查代码中的语法正确性
  2. 文本编辑器：实现括号高亮和自动补全功能
  3. IDE开发：提供语法检查和错误提示
  4. 表达式解析：验证数学和逻辑表达式的正确性
  5. 配置文件解析：检查配置文件中的结构正确性
  6. 模板引擎：验证模板语法的正确性
  7. HTML/XML解析：检查标签的正确嵌套
  8. JSON解析：验证JSON格式的正确性

算法复杂度分析

  1. 时间复杂度：O(n)

  2. 空间复杂度：O(n)

与其他实现方式的比较

// 使用递归的实现
pub fn brackets_are_balanced_recursive(string: &str) -> bool {
fn check_recursive(chars: &[char], index: usize, stack: &mut Vec<char>) -> bool {if index >= chars.len() {return stack.is_empty();}let c = chars[index];match c {'(' | '[' | '{' => {stack.push(c);check_recursive(chars, index + 1, stack)}')' | ']' | '}' => {let expected = match c {')' => '(',']' => '[','}' => '{',_ => unreachable!(),};if stack.pop() == Some(expected) {check_recursive(chars, index + 1, stack)} else {false}}_ => check_recursive(chars, index + 1, stack),}}let chars: Vec<char> = string.chars().collect();let mut stack = Vec::new();check_recursive(&chars, 0, &mut stack)}// 使用状态机的实现#[derive(Debug, Clone, Copy)]enum State {Balanced,Unbalanced,}pub fn brackets_are_balanced_state_machine(string: &str) -> bool {let mut state = State::Balanced;let mut stack = Vec::new();for c in string.chars() {match (state, c) {(State::Balanced, '(' | '[' | '{') => {stack.push(c);}(State::Balanced, ')' | ']' | '}') => {let expected = match c {')' => '(',']' => '[','}' => '{',_ => unreachable!(),};if stack.pop() == Some(expected) {state = State::Balanced;} else {state = State::Unbalanced;}}(State::Unbalanced, _) => {// 一旦不平衡，保持不平衡状态break;}_ => (), // 忽略其他字符}}matches!(state, State::Balanced) && stack.is_empty()}// 使用迭代器链的函数式实现pub fn brackets_are_balanced_functional(string: &str) -> bool {string.chars().fold((Vec::new(), true), |(mut stack, is_balanced), c| {if !is_balanced {return (stack, false);}match c {'(' | '[' | '{' => {stack.push(c);(stack, true)}')' => {if stack.pop() == Some('(') {(stack, true)} else {(stack, false)}}']' => {if stack.pop() == Some('[') {(stack, true)} else {(stack, false)}}'}' => {if stack.pop() == Some('{') {(stack, true)} else {(stack, false)}}_ => (stack, true),}}).1 && string.chars().fold(Vec::new(), |mut stack, c| {match c {'(' | '[' | '{' => stack.push(c),')' | ']' | '}' => { stack.pop(); }_ => (),}stack}).is_empty()}

总结

通过 matching-brackets 练习，我们学到了：

  1. 栈数据结构：掌握了栈的基本操作和应用
  2. 字符处理：学会了处理字符串中的字符
  3. 算法设计：理解了括号匹配算法的设计思路
  4. 性能优化：了解了不同实现方式的性能特点
  5. 边界情况处理：学会了处理各种输入边界情况
  6. 错误处理：深入理解了Result类型处理错误情况

这些技能在实际开发中非常有用，特别是在编译器开发、文本处理、表达式解析等场景中。括号匹配虽然是一个经典的数据结构问题，但它涉及到了栈操作、字符处理、算法设计等许多核心概念，是学习Rust实用编程的良好起点。

通过这个练习，我们也看到了Rust在数据结构实现和算法设计方面的强大能力，以及如何用安全且高效的方式实现经典算法。这种结合了安全性和性能的语言特性正是Rust的魅力所在。

http://www.jsqmd.com/news/285863/

相关文章：

  • 2026 年 AI PPT 工具深度评测：拒绝 “科技与狠活”，寻找真正能解决职场痛点的生产力工具
  • 2026年专业深度测评：淘宝代运营公司排名前五权威榜单
  • 【计算机毕业设计案例】基于Java的在线食品安全信息平台基于springboot的食品安全管理系统(程序+文档+讲解+定制)
  • Java毕设项目：基于springboot的食品安全管理系统(源码+文档，讲解、调试运行，定制等)
  • AI代码质检员：如何用大模型提前揪出软件缺陷？
  • 湖州职业技术学院：Wi-Fi 7全覆盖，打造智慧校园“湖职样本”
  • Linux命令创意
  • ：计算机Java毕设实战-基于springboot的食品安全管理系统食品安全档案管理系统【完整源码+LW+部署说明+演示视频，全bao一条龙等】
  • Vue3底层原理——keep-alive
  • ：vtkBooleanOperationPolyDataFilter 布尔运算全解析
  • 2026年拼多多代运营服务商专业深度测评：排名前五权威榜单
  • APS1604M-SQR-SN核心性能特点及应用
  • GD5F2GM7UEYIGR核心性能及应用
  • 维基百科志愿者创建AI写作特征库，现推出插件帮助规避检测
  • Java毕设选题推荐：基于springboot+vue的食品安全管理系统基于springboot的食品安全管理系统【附源码、mysql、文档、调试+代码讲解+全bao等】
  • 计算机Java毕设实战-基于SpringBoot+Vue线上素菜超市平台蔬菜商城springboot的蔬菜超市系统【完整源码+LW+部署说明+演示视频，全bao一条龙等】
  • AI助力托管安全服务商降本增效实战分享
  • 2026 年办公效率新标杆：AI PPT 工具的全流程生成能力评测，重新定义演示文稿制作
  • ThinkPHP框架学习全攻略
  • 前端性能优化系列（一）：问题分析与诊断
  • Java毕设选题推荐：基于SpringBoot生鲜商城系统基于springboot的蔬菜超市系统【附源码、mysql、文档、调试+代码讲解+全bao等】
  • 高管无视AI泡沫担忧，坚定推进技术采用计划
  • 2026年天猫代运营公司排名前五权威发布：专业深度测评
  • MX Linux 25.1恢复可切换初始化系统功能
  • offline_install_processor.cpp中的IPC通信
  • 微软CEO重新定义AI主权：关键在控制权而非数据中心位置
  • (新卷,200分)- 数字加减游戏（Java JS Python）
  • Nginx多服务静态资源路径冲突解决方案
  • CIO如何解锁人工智能战略价值并实施落地
  • Java毕设项目：基于springboot的蔬菜超市系统(源码+文档，讲解、调试运行，定制等)