haar_lib/parser/
parse_paren.rs

1//! 括弧列の構文解析
2
3use std::iter::Peekable;
4
5/// 括弧列のパースの結果
6#[derive(Clone, Debug)]
7pub struct ParseResult<T> {
8    /// 複数の[`Elem`]からなる列
9    pub elems: Vec<Elem<T>>,
10}
11
12/// ‍対応のある括弧列、または括弧以外の値を一つもつ列挙型
13#[derive(Clone, Debug)]
14pub enum Elem<T> {
15    /// 括弧以外
16    Value(T),
17    /// 対応のある括弧列
18    Paren {
19        /// 開き括弧
20        open: T,
21        /// 括弧の内部のパースの結果
22        inner: ParseResult<T>,
23        /// 閉じ括弧
24        close: T,
25    },
26}
27
28fn _parse<T: Copy + Eq + std::fmt::Debug>(
29    s: &mut Peekable<impl Iterator<Item = T>>,
30    open: T,
31    close: T,
32) -> Option<ParseResult<T>> {
33    let mut elems = vec![];
34
35    loop {
36        let c = s.peek();
37
38        match c {
39            None => break,
40            Some(&c) => {
41                if c == open {
42                    s.next();
43                    let inner = _parse(s, open, close)?;
44
45                    let c = s.peek()?;
46                    assert_eq!(c, &close);
47                    elems.push(Elem::Paren { open, inner, close });
48                    s.next();
49                } else if c == close {
50                    break;
51                } else {
52                    elems.push(Elem::Value(c));
53                    s.next();
54                }
55            }
56        }
57    }
58
59    Some(ParseResult { elems })
60}
61
62/// 括弧列をパースする。
63pub fn parse_paren<T: Copy + Eq + std::fmt::Debug>(
64    s: impl IntoIterator<Item = T>,
65    open: T,
66    close: T,
67) -> Option<ParseResult<T>> {
68    assert_ne!(open, close);
69
70    let mut s = s.into_iter().peekable();
71    let res = _parse(&mut s, open, close);
72
73    if s.peek().is_none() {
74        res
75    } else {
76        None
77    }
78}
79
80#[cfg(test)]
81mod tests {
82    use super::*;
83
84    fn check(s: &str) -> bool {
85        let a = parse_paren(s.chars(), '(', ')');
86        a.is_some()
87    }
88
89    #[test]
90    fn test() {
91        assert!(check("()"));
92        assert!(check("()()()"));
93        assert!(check("(()(()))"));
94
95        assert!(!check(")("));
96        assert!(!check("(()"));
97        assert!(!check("())"));
98        assert!(!check("(()()"));
99
100        assert!(check("a(bc(d)()e((f)g)h)i"));
101
102        assert!(!check("(()()aaa"));
103    }
104}
haar_lib/parser/parse_paren.rs

haar_lib/parser/
parse_paren.rs
