| 1 | import os |
| 2 | |
| 3 | fn regex_match(src string, pat string) bool { |
| 4 | src_size := src.len + 1 |
| 5 | pat_size := pat.len + 1 |
| 6 | mut memo := [][]int{len: src_size, init: []int{len: pat_size, init: -1}} |
| 7 | return regex_match_core(src, pat, 0, 0, mut memo) |
| 8 | } |
| 9 | |
| 10 | fn regex_match_core(src string, pat string, src_pos int, pat_pos int, mut memo [][]int) bool { |
| 11 | if memo[src_pos][pat_pos] != -1 { |
| 12 | return memo[src_pos][pat_pos] == 1 |
| 13 | } |
| 14 | mut spos := src_pos |
| 15 | mut ppos := pat_pos |
| 16 | if spos >= src.len && ppos >= pat.len { |
| 17 | memo[src_pos][pat_pos] = 1 |
| 18 | return true |
| 19 | } else if spos < src.len && ppos >= pat.len { |
| 20 | memo[src_pos][pat_pos] = 0 |
| 21 | return false |
| 22 | } else if spos >= src.len && ppos < pat.len { |
| 23 | if pat[ppos] == `\\` { |
| 24 | ppos++ |
| 25 | } |
| 26 | res := ppos + 1 < pat.len && pat[ppos + 1] in [`*`, `?`] |
| 27 | && regex_match_core(src, pat, spos, ppos + 2, mut memo) |
| 28 | memo[src_pos][pat_pos] = if res { 1 } else { 0 } |
| 29 | return res |
| 30 | } else { |
| 31 | first_is_bslash := pat[ppos] == `\\` |
| 32 | if first_is_bslash { |
| 33 | ppos++ |
| 34 | } |
| 35 | first_bslash_and_match := first_is_bslash && ppos < pat.len |
| 36 | && (((pat[ppos] == `d` && src[spos].is_digit()) |
| 37 | || (pat[ppos] == `D` && !src[spos].is_digit()) |
| 38 | || (pat[ppos] == `s` && src[spos].is_space()) |
| 39 | || (pat[ppos] == `S` && !src[spos].is_space()) |
| 40 | || (pat[ppos] == `w` && (src[spos].is_digit() || src[spos].is_letter() |
| 41 | || src[spos] == `_`)) || (pat[ppos] == `W` && !(src[spos].is_digit() |
| 42 | || src[spos].is_letter() || src[spos] == `_`))) |
| 43 | || (pat[ppos] in [`d`, `D`, `s`, `S`, `w`, `W`] && ppos + 1 < pat.len |
| 44 | && pat[ppos + 1] in [`*`, `?`, `+`]) |
| 45 | || (pat[ppos] !in [`d`, `D`, `s`, `S`, `w`, `W`] && src[spos] == pat[ppos])) |
| 46 | if ppos + 1 < pat.len { |
| 47 | match pat[ppos + 1] { |
| 48 | `*` { |
| 49 | if first_bslash_and_match { |
| 50 | res := regex_match_core(src, pat, spos + 1, ppos - 1, mut memo) |
| 51 | || regex_match_core(src, pat, spos, ppos + 2, mut memo) |
| 52 | memo[src_pos][pat_pos] = if res { 1 } else { 0 } |
| 53 | return res |
| 54 | } else if src[spos] == pat[ppos] || pat[ppos] == `.` { |
| 55 | res := regex_match_core(src, pat, spos + 1, ppos, mut memo) |
| 56 | || regex_match_core(src, pat, spos, ppos + 2, mut memo) |
| 57 | memo[src_pos][pat_pos] = if res { 1 } else { 0 } |
| 58 | return res |
| 59 | } else { |
| 60 | res := regex_match_core(src, pat, spos, ppos + 2, mut memo) |
| 61 | memo[src_pos][pat_pos] = if res { 1 } else { 0 } |
| 62 | return res |
| 63 | } |
| 64 | } |
| 65 | `+` { |
| 66 | if first_bslash_and_match { |
| 67 | res := regex_match_core(src, pat, spos + 1, ppos - 1, mut memo) |
| 68 | || regex_match_core(src, pat, spos + 1, ppos + 2, mut memo) |
| 69 | memo[src_pos][pat_pos] = if res { 1 } else { 0 } |
| 70 | return res |
| 71 | } else if src[spos] == pat[ppos] || pat[ppos] == `.` { |
| 72 | res := regex_match_core(src, pat, spos + 1, ppos, mut memo) |
| 73 | || regex_match_core(src, pat, spos + 1, ppos + 2, mut memo) |
| 74 | memo[src_pos][pat_pos] = if res { 1 } else { 0 } |
| 75 | return res |
| 76 | } else { |
| 77 | memo[src_pos][pat_pos] = 0 |
| 78 | return false |
| 79 | } |
| 80 | } |
| 81 | `?` { |
| 82 | if first_bslash_and_match || src[spos] == pat[ppos] || pat[ppos] == `.` { |
| 83 | res := regex_match_core(src, pat, spos + 1, ppos + 2, mut memo) |
| 84 | || regex_match_core(src, pat, spos, ppos + 2, mut memo) |
| 85 | memo[src_pos][pat_pos] = if res { 1 } else { 0 } |
| 86 | return res |
| 87 | } else { |
| 88 | res := regex_match_core(src, pat, spos, ppos + 2, mut memo) |
| 89 | memo[src_pos][pat_pos] = if res { 1 } else { 0 } |
| 90 | return res |
| 91 | } |
| 92 | } |
| 93 | else {} |
| 94 | } |
| 95 | } |
| 96 | if first_is_bslash { |
| 97 | res := first_bslash_and_match |
| 98 | && regex_match_core(src, pat, spos + 1, ppos + 1, mut memo) |
| 99 | memo[src_pos][pat_pos] = if res { 1 } else { 0 } |
| 100 | return res |
| 101 | } else { |
| 102 | res := (src[spos] == pat[ppos] || pat[ppos] == `.`) && pat[ppos] != `\\` |
| 103 | && regex_match_core(src, pat, spos + 1, ppos + 1, mut memo) |
| 104 | memo[src_pos][pat_pos] = if res { 1 } else { 0 } |
| 105 | return res |
| 106 | } |
| 107 | } |
| 108 | } |
| 109 | |
| 110 | fn main() { |
| 111 | mut cnt := 0 |
| 112 | println('currently supported patterns: . ? + * \\ \\d \\D \\s \\S \\w \\W') |
| 113 | println('example: source `[email protected]` matches pattern `\\w+@domain\\.net`') |
| 114 | println('enter `exit` to quit\n') |
| 115 | for { |
| 116 | cnt++ |
| 117 | src := os.input('[${cnt}] enter source string: ') |
| 118 | if src == 'exit' { |
| 119 | break |
| 120 | } |
| 121 | pat := os.input('[${cnt}] enter pattern string: ') |
| 122 | if pat == 'exit' { |
| 123 | break |
| 124 | } |
| 125 | println('[${cnt}] whether `${src}` matches `${pat}`: ${regex_match(src, pat)}') |
| 126 | } |
| 127 | } |