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

@@ @@ -83,24 +83,28 @@ class Chain(Token): @@
 		for token in self.content:
 			for t in previous:
 				for x in t.list_last():
 					for y in token.list_first():
 						yield (x, y)
 			yield from token.list_neighbours()
 			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
 	for (i, c) in enumerate(pattern[k:]):
 		if c == "(":
 			counter += 1
 		elif c == ")":
 			counter -= 1
@@ @@ -150,37 +154,39 @@ class Regexp: @@
 			if key not in rules:
 				rules[key] = set()
 			rules[key].add(i)
 		for (i, j) in r.list_neighbours():
 			c = s[j]
 			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}
 		for c in s:
 			new_state = set()
 			for st in current:
 				key = (st, c)
 				if key in self.rules:
 					new_state.update(self.rules[key])
 			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

@@ @@ -78,24 +78,28 @@ impl Token for Plus { @@
 		for x in self.list_last() {
 			for y in self.list_first() {
 				res.push((x, y));
+			}
+		}
 		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;}
+		}
 		return res;
+	}
 	fn list_last(&self) -> Vec<usize> {
 		let mut res = Vec::new();
@@ @@ -197,25 +201,28 @@ impl Regexp { @@
 			};
+		}
 		for (i, j) in r.list_neighbours() {
 			let c = pattern_chars[j];
 			let key = (i, c);
 			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]);
 		for c in s.chars() {
 			let mut new_multistate = HashSet::new();
 			for state in multistate {
 				if let Some(x) = self.rules.get(&(state, c)) {
@@ @@ -223,22 +230,22 @@ impl Regexp { @@
 				} else if let Some(x) = self.rules.get(&(state, '.')) {
 					new_multistate = new_multistate.union(&x).map(|&y| y).collect();
+				}
+			}
 			multistate = new_multistate;
+		}
 		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()));
+		}
 		println!();
+	}
+}

0 comments (0 inline, 0 general)