diff --git a/regexp.py b/regexp.py --- a/regexp.py +++ b/regexp.py @@ -35,9 +35,7 @@ class Symbol(Token): return self.value -class Asterisk(Token): - is_skippable = True - +class Plus(Token): def __init__(self, content: Token): self.content = content @@ -54,6 +52,13 @@ class Asterisk(Token): yield (x, y) def __str__(self): + return str(self.content) + "+" + + +class Asterisk(Plus): + is_skippable = True + + def __str__(self): return str(self.content) + "*" @@ -120,6 +125,10 @@ def parse(pattern, offset=0): token = res.pop() res.append(Asterisk(token)) i += 1 + elif c == "+": + token = res.pop() + res.append(Plus(token)) + i += 1 else: res.append(Symbol(i+offset, c)) i += 1 @@ -169,8 +178,9 @@ class Regexp: if __name__ == "__main__": tests = ["a", "ab", "aabb", "abab", "abcd", "abcbcdbcd"] - for pattern in ["a*b*", "(ab)*", "a((bc)*d)*"]: + for pattern in ["a*b*", "a+b+", "(ab)*", "(ab)+", "a((bc)*d)*"]: print("#", pattern) + r = Regexp(pattern) for t in tests: - print(t, Regexp(pattern).match(t)) + print(t, r.match(t)) print() diff --git a/src/main.rs b/src/main.rs --- a/src/main.rs +++ b/src/main.rs @@ -18,6 +18,10 @@ struct Asterisk { content: Box } +struct Plus { + content: Box +} + struct Chain { content: Vec> } @@ -60,6 +64,28 @@ impl Token for Asterisk { } } +impl Token for Plus { + fn list_first(&self) -> Vec { + return self.content.list_first(); + } + + fn list_last(&self) -> Vec { + return self.content.list_last(); + } + + fn list_neighbours(&self) -> Vec<(usize, usize)> { + let mut res = self.content.list_neighbours(); + + for x in self.list_last() { + for y in self.list_first() { + res.push((x, y)); + } + } + + return res; + } +} + impl Token for Chain { fn list_first(&self) -> Vec { let mut res = Vec::new(); @@ -136,6 +162,11 @@ fn parse(pattern: &String, offset: usize res.push(Box::new(Asterisk{content: token})); i += 1; } + '+' => { + let token = res.pop().unwrap(); + res.push(Box::new(Plus{content: token})); + i += 1; + } c => { res.push(Box::new(Symbol{position: i+offset, value: c})); i += 1; @@ -202,7 +233,7 @@ impl Regexp { fn main() { let tests = ["a", "ab", "aabb", "abab", "abcd", "abcbcdbcd"]; - for pattern in ["a*b*", "(ab)*", "a((bc)*d)*"] { + for pattern in ["a*b*", "a+b+", "(ab)*", "(ab)+", "a((bc)*d)*"] { println!("# {pattern}"); let r = Regexp::new(&pattern.to_string()); for &t in tests.iter() {