Bracket Push

1. Readme

括号配套

给定包含括号[]大括号{}括号()或它们的任何组合的字符串，验证任何和所有对，都被正确地匹配和嵌套。

资源

Ginna Baker

2. 开始你的表演

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

3. 测试代码查看

 

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

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

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

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

#[test]
//#[ignore]
fn wrong_closing_bracket() {
   assert!(!brackets_are_balanced("{]"));
}

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

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

#[test]
//#[ignore]
fn several_paired_brackets() {
   assert!(brackets_are_balanced("{}[]"));
}

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

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

#[test]
//#[ignore]
fn unpaired_and_nested_brackets() {
   assert!(!brackets_are_balanced("([{])"));
}

#[test]
//#[ignore]
fn paired_and_wrong_nested_brackets() {
   assert!(!brackets_are_balanced("[({]})"));
}

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

#[test]
//#[ignore]
fn complex_latex_expression() {
   let input = "\\left(\\begin{array}{cc} \\frac{1}{3} & x\\\\ \\mathrm{e}^{x} &... x^2 \
                \\end{array}\\right)";
   assert!(brackets_are_balanced(input));
}

#}

4. 答案

 


# #![allow(unused_variables)]
#fn main() {
use std::collections::HashMap;

pub fn brackets_are_balanced(string: &str) -> bool {
   Brackets::from(string).are_balanced()
}

struct Brackets {
   raw_brackets: Vec<char>,
   pairs: MatchingBrackets,
}

impl<'a> From<&'a str> for Brackets {
   fn from(i: &str) -> Self {
       Brackets::new(String::from(i), None)
   }
}

impl Brackets {
   fn new(s: String, pairs: Option<Vec<(char, char)>>) -> Self {
       let p = match pairs {
           Some(x) => MatchingBrackets::from(x),
           None => MatchingBrackets::from(vec![('[', ']'), ('{', '}'), ('(', ')')]),
       };

       Brackets {
           raw_brackets: s.chars().filter(|c| p.contains(&c)).collect::<Vec<char>>(),
           pairs: p,
       }
   }

   fn are_balanced(&self) -> bool {
       let mut unclosed: Vec<char> = Vec::new();

       for &bracket in self.raw_brackets.iter() {
           if let Some(last_unclosed) = unclosed.pop() {
               unclosed.extend(self.pairs.unmatched(last_unclosed, bracket));
           } else {
               unclosed.push(bracket);
           }
       }

       unclosed.is_empty()
   }
}

struct MatchingBrackets {
   collection: HashMap<char, char>,
}

impl From<Vec<(char, char)>> for MatchingBrackets {
   fn from(v: Vec<(char, char)>) -> Self {
       MatchingBrackets {
           collection: v.into_iter().collect::<HashMap<char, char>>(),
       }
   }
}

impl MatchingBrackets {
   fn contains(&self, other: &char) -> bool {
       let known = self.collection
           .keys()
           .chain(self.collection.values())
           .collect::<Vec<_>>();
       known.contains(&other)
   }

   fn closer_for(&self, k: &char) -> Option<&char> {
       self.collection.get(k)
   }

   fn closed_by(&self, l: char, r: char) -> bool {
       match self.closer_for(&l) {
           Some(&x) => r == x,
           None => false,
       }
   }

   fn unmatched(&self, open: char, potential_close: char) -> Vec<char> {
       let mut ret: Vec<char> = Vec::new();

       if !self.closed_by(open, potential_close) {
           ret.push(open);
           ret.push(potential_close);
       }

       ret
   }
}

#}

填充/相关