Regular-Expresso Changeset

Changeset - a86ff65ec321

Parent rev.

Child rev.

[Not reviewed]

default

0 2 0

Laman - 10 months ago 2024-06-12 23:27:53

fixed the negative match for an empty string

2 files changed with 16 insertions and 3 deletions:

regexp.py

src/main.rs

0 comments (0 inline, 0 general)

regexp.py

➞

Show inline comments

@@ @@ -89,12 +89,16 @@ class Chain(Token): @@
 			if token.is_skippable:
 				previous.append(token)
 			else:
 				previous = [token]
 	@property
 	def is_skippable(self):
 		return all(x.is_skippable for x in self.content)
 	def __str__(self):
 		return "(" + "".join(str(x) for x in self.content) + ")"
 def find_closing_parenthesis(pattern, k):
 	counter = 0
@@ @@ -156,12 +160,14 @@ class Regexp: @@
 			key = (i, c)
 			if key not in rules:
 				rules[key] = set()
 			rules[key].add(j)
 		end_states = set(r.list_last())
 		if r.is_skippable:
 			end_states.add(-1)
 		return rules, end_states
 	def match(self, s):
 		current = {-1}
@@ @@ -174,13 +180,13 @@ class Regexp: @@
 			current = new_state
 		return any(st in self.end_states for st in current)
 if __name__ == "__main__":
 	tests = ["a", "ab", "aabb", "abab", "abcd", "abcbcdbcd"]
+	tests = ["", "a", "ab", "aabb", "abab", "abcd", "abcbcdbcd"]
 	for pattern in ["a*b*", "a+b+", "(ab)*", "(ab)+", "a((bc)*d)*"]:
 		print("#", pattern)
 		r = Regexp(pattern)
 		for t in tests:
 			print(t, r.match(t))
 		print()

src/main.rs

➞

Show inline comments

@@ @@ -84,12 +84,16 @@ impl Token for Plus { @@
 		return res;
+	}
+}
 impl Token for Chain {
 	fn is_skippable(&self) -> bool {
 		return self.content.iter().all(|x| x.is_skippable());
+	}
 	fn list_first(&self) -> Vec<usize> {
 		let mut res = Vec::new();
 		for token in self.content.iter() {
 			res.append(&mut token.list_first());
 			if !token.is_skippable() {break;}
+		}
@@ @@ -203,13 +207,16 @@ impl Regexp { @@
 			match rules.get_mut(&key) {
 				Some(set) => {set.insert(j);},
 				None => {rules.insert(key, HashSet::from([j]));}
 			};
+		}
 		let end_states = HashSet::from_iter(r.list_last().into_iter());
 		let mut end_states = HashSet::from_iter(r.list_last().into_iter());
 		if r.is_skippable() {
 			end_states.insert(START);
+		}
 		return Regexp{rules, end_states};
+	}
 	pub fn eval(&self, s: String) -> bool {
 		let mut multistate = HashSet::from([START]);
@@ @@ -229,13 +236,13 @@ impl Regexp { @@
 		return multistate.iter().any(|x| self.end_states.contains(x));
+	}
+}
 fn main() {
 	let tests = ["a", "ab", "aabb", "abab", "abcd", "abcbcdbcd"];
+	let tests = ["", "a", "ab", "aabb", "abab", "abcd", "abcbcdbcd"];
 	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() {
 			println!("{t} {}", r.eval(t.to_string()));
+		}

0 comments (0 inline, 0 general)