1
\$\begingroup\$

I have written a recursive parsing algorithm for strings with nested brackets (I needed it to solve a molecules to atoms task). I would love to see how I could make it more idiomatic (I am a noob at Rust an exploring a lot of APIs and other people's code) and/or efficient.

Here are some examples of tests:

assert_parse!("H", [("H",1)], hydrogen);
assert_parse!("O2", [("O",2)], oxygen);
assert_parse!("H2O", [("H",2),("O",1)], water);
assert_parse!("Mg(OH)2", [("Mg",1),("O",2),("H",2)], 
magnesium_hydroxide);
assert_parse!("K4[ON(SO3)2]2", [("K",4),("O",14),("N",2),("S",4)], 
fremys_salt);

I tried a few different implementations, and for the moment went with the following:

use char_stream::CharStream;
use std::collections::HashMap;
use std::collections::VecDeque;
use std::rc::Rc;

struct Brackets {
    brackets: String,
}

fn get_closed(s: char) -> char {
    match s {
        '{' => '}',
        '[' => ']',
        '(' => ')',
        _ => s,
    }
}

fn is_open(c: char) -> bool {
    match c {
        '{' | '[' | '(' => true,
        _ => false,
    }
}

fn is_closed(c: char) -> bool {
    match c {
        '}' | ']' | ')' => true,
        _ => false,
    }
}

impl Brackets {
    pub fn from(s: &str) -> Self {
        Brackets {
            brackets: String::from(s),
        }
    }

    pub fn are_balanced(&self) -> bool {
        let mut open = VecDeque::new();
        for ch in self.brackets.chars() {
            if is_open(ch) {
                open.push_front(ch);
            }
            if !open.is_empty() && is_closed(ch) {
                if get_closed(open[0]) == ch {
                    open.pop_front();
                } else {
                    return false;
                }
            }
        }
        open.is_empty()
    }
}

type Atom = (String, usize);
type Molecule = Vec<Atom>;

#[derive(Debug)]
struct ParseError {
    message: &'static str,
}

impl ParseError {
    fn invalid() -> ParseError {
        ParseError {
            message: "Not a valid molecule",
        }
    }
    fn mismatched() -> ParseError {
        ParseError {
            message: "Mismatched parenthesis",
        }
    }
}

n str_to_vec(s: String, idx: usize) -> Vec<String> {
    let mut str = vec![s.clone()];
    str.resize(idx, s.clone());
    str
}

fn parse(mut stream: Rc<CharStream>, idx: usize) -> Vec<String> {
    let mut atom_vec: Vec<String> = Vec::new();
    while let Some(c) = Rc::get_mut(&mut stream).unwrap().next() {
        match c {
            c if c.is_uppercase() => {
                let mut a = String::new();
                a.push(c);
                let mut str_vec: Vec<String>;
                let l = Rc::get_mut(&mut stream).unwrap().peek();
                match l {
                    Some(l) if l.is_lowercase() => {
                        a.push(l);
                        Rc::get_mut(&mut stream).unwrap().next();
                        let next = Rc::get_mut(&mut stream).unwrap().peek().unwrap_or('1');
                        if next.is_digit(10) {
                            str_vec = str_to_vec(a, next.to_digit(10).unwrap() as usize * idx);
                        } else {
                            str_vec = str_to_vec(a, idx);
                        }
                    }
                    Some(l) if l.is_digit(10) => {
                        str_vec = str_to_vec(a, l.to_digit(10).unwrap() as usize * idx);
                    }
                    Some(_) => {
                        str_vec = str_to_vec(a, idx);
                    }
                    None => {
                        str_vec = str_to_vec(a, idx);
                    }
                }
                atom_vec.append(&mut str_vec);
            }
            c if is_open(c) => {
                let inside_brackets = Rc::get_mut(&mut stream)
                    .unwrap()
                    .take_while(|p| *p != get_closed(c))
                    .collect::<String>();
                let inner_stream = Rc::new(CharStream::from(&inside_brackets));
                let multiplier = idx
                    * Rc::get_mut(&mut stream)
                        .unwrap()
                        .next()
                        .unwrap_or('1')
                        .to_digit(10)
                        .unwrap() as usize;
                atom_vec.append(&mut parse(inner_stream, multiplier));
            }
            _ => (),
        }
    }
    atom_vec
}

fn parse_molecule(s: &str) -> Result<Molecule, ParseError> {
    if !s.chars().nth(0).unwrap().is_uppercase() {
        Err(ParseError::invalid())
    } else if !Brackets::from(s).are_balanced() {
        Err(ParseError::mismatched())
    } else {
        let stream = Rc::new(CharStream::from(s));
        let atoms: Vec<String> = parse(stream, 1 as usize);
        let mut atoms_map: HashMap<String, usize> = HashMap::new();
        for atom in atoms {
            let counter = atoms_map.entry(atom).or_insert(0);
            *counter += 1;
        }
        let mut molecules: Vec<Atom> = vec![];
        atoms_map.into_iter().for_each(|atom| molecules.push(atom));
        Ok(molecules)
    }
}

fn main() {
    println!("{:#?}", parse_molecule("K4[ON(SO3{Se}3)2]2").unwrap());
}

Thanks a lot for reading my code.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.