Minreg the Cat/minreg.rs

← Back to Minreg the Cat

use std::io::{self, Write};

fn main() {
    let mut lines = io::stdin().lines().map(Result::unwrap);
    let mut prompt = |s| {
        print!("{s}");
        io::stdout().flush().unwrap();
        lines.next()
    };
    let regex = prompt("Enter Minreg expression: ").expect("could not read regex from input");
    let tree = Tree::new(&regex);
    while let Some(line) = prompt("Enter string: ") {
        if tree.matches(&line) {
            println!("matched")
        } else {
            println!("did not match")
        }
    }
}

#[derive(Debug)]
enum Tree {
    Any,               // .
    Or(Vec<Tree>),     // |
    Kleene(Box<Tree>), // *
    Group(Vec<Tree>),  // ,
    Literal(char),
}

impl Tree {
    fn new(regex: &str) -> Self {
        let mut stack = Vec::new();
        let mut iter = regex.chars();
        while let Some(x) = iter.next() {
            if !",.|\\*".contains(x) {
                stack.push(Tree::Literal(x));
            } else if x == '\\' {
                stack.push(Tree::Literal(
                    iter.next().expect("why tf wud u put \\ @ da end??"),
                ));
            } else {
                if x == '.' {
                    stack.push(Tree::Any);
                } else {
                    let b = stack.pop().expect("empty stack");
                    if x == '*' {
                        stack.push(Tree::Kleene(Box::new(b)));
                        continue;
                    }
                    let mut a = stack.pop().expect("empty stack");
                    match x {
                        '|' => match &mut a {
                            Tree::Or(v) => v.push(b),
                            _ => a = Tree::Or(vec![a, b]),
                        },
                        ',' => match &mut a {
                            Tree::Group(v) => v.push(b),
                            _ => a = Tree::Group(vec![a, b]),
                        },
                        _ => unreachable!(),
                    }
                    stack.push(a);
                }
            }
        }
        Tree::Group(stack)
    }
    fn matches(&self, s: &str) -> bool {
        let (b, idx) = self.matches_priv(s);
        b && s.len() == idx
    }
    fn matches_priv(&self, s: &str) -> (bool, usize) {
        let mut idx = 0;
        let fail = (false, 0);
        match self {
            Tree::Any => {
                if let Some(c) = s.chars().next() {
                    (true, c.len_utf8())
                } else {
                    fail
                }
            }
            Tree::Literal(c) => {
                if Some(*c) == s.chars().next() {
                    (true, c.len_utf8())
                } else {
                    fail
                }
            }
            Tree::Group(v) => {
                for m in v {
                    if let (true, i) = m.matches_priv(&s[idx..]) {
                        idx += i;
                    } else {
                        return fail;
                    }
                }
                (true, idx)
            }
            Tree::Or(v) => {
                for m in v {
                    if let (true, i) = m.matches_priv(s) {
                        return (true, i);
                    }
                }
                fail
            }
            Tree::Kleene(b) => {
                while let (true, i) = b.matches_priv(&s[idx..]) {
                    idx += i;
                }
                (true, idx)
            }
        }
    }
}