Re: [algogeeks] Regex tester
ya, it is correct, i misunderstood it.. any optimization on the same though ? On Fri, Dec 28, 2012 at 9:55 AM, shady sinv...@gmail.com wrote: @ritesh umm, well here's a simple testcase to show the problem in the code.. isMatch(aa, a*) On Thu, Dec 27, 2012 at 7:17 PM, Ritesh Mishra rforr...@gmail.com wrote: @shady : either the string will be stored in heap or stack. thus accessing address in heap or stack is not going to give u seg fault . and rest things are very well handled in the code :) As saurabh sir has explained in thread https://mail.google.com/mail/u/1/#inbox/13ba918bdb9aac9e when seg fault occurs . Regards, Ritesh Kumar Mishra Information Technology Third Year Undergraduate MNNIT Allahabad On Thu, Dec 27, 2012 at 6:43 PM, ~*~VICKY~*~ venkat.jun...@gmail.comwrote: I'm giving you a simple recursive code which i wrote long back. Please let me know if it fails for any cases. Ignore the funny cout's It used to help me debug and i'm lazy to remove it. :P :) #includeiostream #includestring using namespace std; /* abasjc a*c while(pattern[j] == '*' text[i] == pattern[j]) {i++; j++} */ bool match(string text, string pattern, int x, int y) { if(pattern.length() == y) { couthey\n; return 1; } if(text.length() == x) { coutshit\n; return 0; } if(pattern[y] == '.' || text[x] == pattern[y]) { coutin matchendl; return match(text,pattern,x+1,y+1); } if(pattern[y] == '*') return match(text,pattern,x+1,y) || match(text,pattern,x+1,y+1) || match(text,pattern,x,y+1); if(text[x] != pattern[y]) { coutshit1\n; return 0; } } int main() { string text,pattern; cin text pattern; cout match(text, pattern,0, 0); } On Thu, Dec 27, 2012 at 6:10 PM, shady sinv...@gmail.com wrote: Thanks for the link Ritesh, if (isMatch(s, p+2)) return true; isnt this line incorrect in the code, as it can lead to segmentation fault... how can we directly access p+2 element, we know for sure that p is not '\0', but p+1 element can be '\0' , therefore leading to p+2 to be undefined. On Thu, Dec 27, 2012 at 6:23 AM, Ritesh Mishra rforr...@gmail.comwrote: try to solve it by recursion .. http://www.leetcode.com/2011/09/regular-expression-matching.html Regards, Ritesh Kumar Mishra Information Technology Third Year Undergraduate MNNIT Allahabad On Sun, Dec 23, 2012 at 11:14 PM, Prem Krishna Chettri hprem...@gmail.com wrote: Well I can tell you Something about design pattern to solve this case.. What I mean is by using The State Machine Design Pattern, Anyone can solve this. but Ofcourse it is complicated. On Sun, Dec 23, 2012 at 11:01 PM, shady sinv...@gmail.com wrote: that's the point, Have to implement it from scratch... otherwise java has regex and matcher, pattern to solve it... On Sun, Dec 23, 2012 at 10:28 PM, saurabh singh saurab...@gmail.com wrote: If you need to implement this for some project then python and java have a very nice library Saurabh Singh B.Tech (Computer Science) MNNIT blog:geekinessthecoolway.blogspot.com On Sun, Dec 23, 2012 at 7:48 PM, shady sinv...@gmail.com wrote: http://stackoverflow.com/questions/13144590/to-check-if-two-strings-match-with-alphabets-digits-and-special-characters any solution for this. we need to implement such regex tester some complex cases : *string** regex * - * status* * * reesd re*.d - match re*eed reeed - match can some one help with this ? -- -- -- -- -- -- -- Cheers, Vicky -- -- --
Re: [algogeeks] Regex tester
i was asked the same question in my Microsoft interview. I gave the solution using a naive method by comparing each letter and tracking the next character. If the next character is *, then set a flag and check the equality, and if it is a . ignore and move on. He was ok with the solution but said that, there is a better way. On Sun, Dec 23, 2012 at 11:14 PM, Prem Krishna Chettri hprem...@gmail.com wrote: Well I can tell you Something about design pattern to solve this case.. What I mean is by using The State Machine Design Pattern, Anyone can solve this. but Ofcourse it is complicated. On Sun, Dec 23, 2012 at 11:01 PM, shady sinv...@gmail.com wrote: that's the point, Have to implement it from scratch... otherwise java has regex and matcher, pattern to solve it... On Sun, Dec 23, 2012 at 10:28 PM, saurabh singh saurab...@gmail.com wrote: If you need to implement this for some project then python and java have a very nice library Saurabh Singh B.Tech (Computer Science) MNNIT blog:geekinessthecoolway.blogspot.com On Sun, Dec 23, 2012 at 7:48 PM, shady sinv...@gmail.com wrote: http://stackoverflow.com/questions/13144590/to-check-if-two-strings-match-with-alphabets-digits-and-special-characters any solution for this. we need to implement such regex tester some complex cases : string regex-status reesd re*.d - match re*eed reeed - match can some one help with this ? -- -- -- -- --
Re: [algogeeks] Regex tester
@shady : look for the implementation of Matcher class.. may be that could help . On Sun, Dec 23, 2012 at 11:01 PM, shady sinv...@gmail.com wrote: that's the point, Have to implement it from scratch... otherwise java has regex and matcher, pattern to solve it... On Sun, Dec 23, 2012 at 10:28 PM, saurabh singh saurab...@gmail.comwrote: If you need to implement this for some project then python and java have a very nice library Saurabh Singh B.Tech (Computer Science) MNNIT blog:geekinessthecoolway.blogspot.com On Sun, Dec 23, 2012 at 7:48 PM, shady sinv...@gmail.com wrote: http://stackoverflow.com/questions/13144590/to-check-if-two-strings-match-with-alphabets-digits-and-special-characters any solution for this. we need to implement such regex tester some complex cases : *string** regex * - * status* * * reesd re*.d - match re*eed reeed - match can some one help with this ? -- -- -- -- best wishes!! Vaibhav --
Re: [algogeeks] Regex tester
try to solve it by recursion .. http://www.leetcode.com/2011/09/regular-expression-matching.html Regards, Ritesh Kumar Mishra Information Technology Third Year Undergraduate MNNIT Allahabad On Sun, Dec 23, 2012 at 11:14 PM, Prem Krishna Chettri hprem...@gmail.comwrote: Well I can tell you Something about design pattern to solve this case.. What I mean is by using The State Machine Design Pattern, Anyone can solve this. but Ofcourse it is complicated. On Sun, Dec 23, 2012 at 11:01 PM, shady sinv...@gmail.com wrote: that's the point, Have to implement it from scratch... otherwise java has regex and matcher, pattern to solve it... On Sun, Dec 23, 2012 at 10:28 PM, saurabh singh saurab...@gmail.comwrote: If you need to implement this for some project then python and java have a very nice library Saurabh Singh B.Tech (Computer Science) MNNIT blog:geekinessthecoolway.blogspot.com On Sun, Dec 23, 2012 at 7:48 PM, shady sinv...@gmail.com wrote: http://stackoverflow.com/questions/13144590/to-check-if-two-strings-match-with-alphabets-digits-and-special-characters any solution for this. we need to implement such regex tester some complex cases : *string** regex * - * status* * * reesd re*.d - match re*eed reeed - match can some one help with this ? -- -- -- -- --
Re: [algogeeks] Regex tester
Thanks for the link Ritesh, if (isMatch(s, p+2)) return true; isnt this line incorrect in the code, as it can lead to segmentation fault... how can we directly access p+2 element, we know for sure that p is not '\0', but p+1 element can be '\0' , therefore leading to p+2 to be undefined. On Thu, Dec 27, 2012 at 6:23 AM, Ritesh Mishra rforr...@gmail.com wrote: try to solve it by recursion .. http://www.leetcode.com/2011/09/regular-expression-matching.html Regards, Ritesh Kumar Mishra Information Technology Third Year Undergraduate MNNIT Allahabad On Sun, Dec 23, 2012 at 11:14 PM, Prem Krishna Chettri hprem...@gmail.com wrote: Well I can tell you Something about design pattern to solve this case.. What I mean is by using The State Machine Design Pattern, Anyone can solve this. but Ofcourse it is complicated. On Sun, Dec 23, 2012 at 11:01 PM, shady sinv...@gmail.com wrote: that's the point, Have to implement it from scratch... otherwise java has regex and matcher, pattern to solve it... On Sun, Dec 23, 2012 at 10:28 PM, saurabh singh saurab...@gmail.comwrote: If you need to implement this for some project then python and java have a very nice library Saurabh Singh B.Tech (Computer Science) MNNIT blog:geekinessthecoolway.blogspot.com On Sun, Dec 23, 2012 at 7:48 PM, shady sinv...@gmail.com wrote: http://stackoverflow.com/questions/13144590/to-check-if-two-strings-match-with-alphabets-digits-and-special-characters any solution for this. we need to implement such regex tester some complex cases : *string** regex * - * status* * * reesd re*.d - match re*eed reeed - match can some one help with this ? -- -- -- -- -- --
Re: [algogeeks] Regex tester
I'm giving you a simple recursive code which i wrote long back. Please let me know if it fails for any cases. Ignore the funny cout's It used to help me debug and i'm lazy to remove it. :P :) #includeiostream #includestring using namespace std; /* abasjc a*c while(pattern[j] == '*' text[i] == pattern[j]) {i++; j++} */ bool match(string text, string pattern, int x, int y) { if(pattern.length() == y) { couthey\n; return 1; } if(text.length() == x) { coutshit\n; return 0; } if(pattern[y] == '.' || text[x] == pattern[y]) { coutin matchendl; return match(text,pattern,x+1,y+1); } if(pattern[y] == '*') return match(text,pattern,x+1,y) || match(text,pattern,x+1,y+1) || match(text,pattern,x,y+1); if(text[x] != pattern[y]) { coutshit1\n; return 0; } } int main() { string text,pattern; cin text pattern; cout match(text, pattern,0, 0); } On Thu, Dec 27, 2012 at 6:10 PM, shady sinv...@gmail.com wrote: Thanks for the link Ritesh, if (isMatch(s, p+2)) return true; isnt this line incorrect in the code, as it can lead to segmentation fault... how can we directly access p+2 element, we know for sure that p is not '\0', but p+1 element can be '\0' , therefore leading to p+2 to be undefined. On Thu, Dec 27, 2012 at 6:23 AM, Ritesh Mishra rforr...@gmail.com wrote: try to solve it by recursion .. http://www.leetcode.com/2011/09/regular-expression-matching.html Regards, Ritesh Kumar Mishra Information Technology Third Year Undergraduate MNNIT Allahabad On Sun, Dec 23, 2012 at 11:14 PM, Prem Krishna Chettri hprem...@gmail.com wrote: Well I can tell you Something about design pattern to solve this case.. What I mean is by using The State Machine Design Pattern, Anyone can solve this. but Ofcourse it is complicated. On Sun, Dec 23, 2012 at 11:01 PM, shady sinv...@gmail.com wrote: that's the point, Have to implement it from scratch... otherwise java has regex and matcher, pattern to solve it... On Sun, Dec 23, 2012 at 10:28 PM, saurabh singh saurab...@gmail.comwrote: If you need to implement this for some project then python and java have a very nice library Saurabh Singh B.Tech (Computer Science) MNNIT blog:geekinessthecoolway.blogspot.com On Sun, Dec 23, 2012 at 7:48 PM, shady sinv...@gmail.com wrote: http://stackoverflow.com/questions/13144590/to-check-if-two-strings-match-with-alphabets-digits-and-special-characters any solution for this. we need to implement such regex tester some complex cases : *string** regex * - * status* * * reesd re*.d - match re*eed reeed - match can some one help with this ? -- -- -- -- -- -- -- Cheers, Vicky --
Re: [algogeeks] Regex tester
@shady : either the string will be stored in heap or stack. thus accessing address in heap or stack is not going to give u seg fault . and rest things are very well handled in the code :) As saurabh sir has explained in thread https://mail.google.com/mail/u/1/#inbox/13ba918bdb9aac9e when seg fault occurs . Regards, Ritesh Kumar Mishra Information Technology Third Year Undergraduate MNNIT Allahabad On Thu, Dec 27, 2012 at 6:43 PM, ~*~VICKY~*~ venkat.jun...@gmail.comwrote: I'm giving you a simple recursive code which i wrote long back. Please let me know if it fails for any cases. Ignore the funny cout's It used to help me debug and i'm lazy to remove it. :P :) #includeiostream #includestring using namespace std; /* abasjc a*c while(pattern[j] == '*' text[i] == pattern[j]) {i++; j++} */ bool match(string text, string pattern, int x, int y) { if(pattern.length() == y) { couthey\n; return 1; } if(text.length() == x) { coutshit\n; return 0; } if(pattern[y] == '.' || text[x] == pattern[y]) { coutin matchendl; return match(text,pattern,x+1,y+1); } if(pattern[y] == '*') return match(text,pattern,x+1,y) || match(text,pattern,x+1,y+1) || match(text,pattern,x,y+1); if(text[x] != pattern[y]) { coutshit1\n; return 0; } } int main() { string text,pattern; cin text pattern; cout match(text, pattern,0, 0); } On Thu, Dec 27, 2012 at 6:10 PM, shady sinv...@gmail.com wrote: Thanks for the link Ritesh, if (isMatch(s, p+2)) return true; isnt this line incorrect in the code, as it can lead to segmentation fault... how can we directly access p+2 element, we know for sure that p is not '\0', but p+1 element can be '\0' , therefore leading to p+2 to be undefined. On Thu, Dec 27, 2012 at 6:23 AM, Ritesh Mishra rforr...@gmail.comwrote: try to solve it by recursion .. http://www.leetcode.com/2011/09/regular-expression-matching.html Regards, Ritesh Kumar Mishra Information Technology Third Year Undergraduate MNNIT Allahabad On Sun, Dec 23, 2012 at 11:14 PM, Prem Krishna Chettri hprem...@gmail.com wrote: Well I can tell you Something about design pattern to solve this case.. What I mean is by using The State Machine Design Pattern, Anyone can solve this. but Ofcourse it is complicated. On Sun, Dec 23, 2012 at 11:01 PM, shady sinv...@gmail.com wrote: that's the point, Have to implement it from scratch... otherwise java has regex and matcher, pattern to solve it... On Sun, Dec 23, 2012 at 10:28 PM, saurabh singh saurab...@gmail.comwrote: If you need to implement this for some project then python and java have a very nice library Saurabh Singh B.Tech (Computer Science) MNNIT blog:geekinessthecoolway.blogspot.com On Sun, Dec 23, 2012 at 7:48 PM, shady sinv...@gmail.com wrote: http://stackoverflow.com/questions/13144590/to-check-if-two-strings-match-with-alphabets-digits-and-special-characters any solution for this. we need to implement such regex tester some complex cases : *string** regex * - * status* * * reesd re*.d - match re*eed reeed - match can some one help with this ? -- -- -- -- -- -- -- Cheers, Vicky -- --
Re: [algogeeks] Regex tester
@ritesh umm, well here's a simple testcase to show the problem in the code.. isMatch(aa, a*) On Thu, Dec 27, 2012 at 7:17 PM, Ritesh Mishra rforr...@gmail.com wrote: @shady : either the string will be stored in heap or stack. thus accessing address in heap or stack is not going to give u seg fault . and rest things are very well handled in the code :) As saurabh sir has explained in thread https://mail.google.com/mail/u/1/#inbox/13ba918bdb9aac9e when seg fault occurs . Regards, Ritesh Kumar Mishra Information Technology Third Year Undergraduate MNNIT Allahabad On Thu, Dec 27, 2012 at 6:43 PM, ~*~VICKY~*~ venkat.jun...@gmail.comwrote: I'm giving you a simple recursive code which i wrote long back. Please let me know if it fails for any cases. Ignore the funny cout's It used to help me debug and i'm lazy to remove it. :P :) #includeiostream #includestring using namespace std; /* abasjc a*c while(pattern[j] == '*' text[i] == pattern[j]) {i++; j++} */ bool match(string text, string pattern, int x, int y) { if(pattern.length() == y) { couthey\n; return 1; } if(text.length() == x) { coutshit\n; return 0; } if(pattern[y] == '.' || text[x] == pattern[y]) { coutin matchendl; return match(text,pattern,x+1,y+1); } if(pattern[y] == '*') return match(text,pattern,x+1,y) || match(text,pattern,x+1,y+1) || match(text,pattern,x,y+1); if(text[x] != pattern[y]) { coutshit1\n; return 0; } } int main() { string text,pattern; cin text pattern; cout match(text, pattern,0, 0); } On Thu, Dec 27, 2012 at 6:10 PM, shady sinv...@gmail.com wrote: Thanks for the link Ritesh, if (isMatch(s, p+2)) return true; isnt this line incorrect in the code, as it can lead to segmentation fault... how can we directly access p+2 element, we know for sure that p is not '\0', but p+1 element can be '\0' , therefore leading to p+2 to be undefined. On Thu, Dec 27, 2012 at 6:23 AM, Ritesh Mishra rforr...@gmail.comwrote: try to solve it by recursion .. http://www.leetcode.com/2011/09/regular-expression-matching.html Regards, Ritesh Kumar Mishra Information Technology Third Year Undergraduate MNNIT Allahabad On Sun, Dec 23, 2012 at 11:14 PM, Prem Krishna Chettri hprem...@gmail.com wrote: Well I can tell you Something about design pattern to solve this case.. What I mean is by using The State Machine Design Pattern, Anyone can solve this. but Ofcourse it is complicated. On Sun, Dec 23, 2012 at 11:01 PM, shady sinv...@gmail.com wrote: that's the point, Have to implement it from scratch... otherwise java has regex and matcher, pattern to solve it... On Sun, Dec 23, 2012 at 10:28 PM, saurabh singh saurab...@gmail.comwrote: If you need to implement this for some project then python and java have a very nice library Saurabh Singh B.Tech (Computer Science) MNNIT blog:geekinessthecoolway.blogspot.com On Sun, Dec 23, 2012 at 7:48 PM, shady sinv...@gmail.com wrote: http://stackoverflow.com/questions/13144590/to-check-if-two-strings-match-with-alphabets-digits-and-special-characters any solution for this. we need to implement such regex tester some complex cases : *string** regex * - * status* * * reesd re*.d - match re*eed reeed - match can some one help with this ? -- -- -- -- -- -- -- Cheers, Vicky -- -- --
Re: [algogeeks] Regex tester
If you need to implement this for some project then python and java have a very nice library Saurabh Singh B.Tech (Computer Science) MNNIT blog:geekinessthecoolway.blogspot.com On Sun, Dec 23, 2012 at 7:48 PM, shady sinv...@gmail.com wrote: http://stackoverflow.com/questions/13144590/to-check-if-two-strings-match-with-alphabets-digits-and-special-characters any solution for this. we need to implement such regex tester some complex cases : *string** regex * - * status* * * reesd re*.d - match re*eed reeed - match can some one help with this ? -- --
Re: [algogeeks] Regex tester
that's the point, Have to implement it from scratch... otherwise java has regex and matcher, pattern to solve it... On Sun, Dec 23, 2012 at 10:28 PM, saurabh singh saurab...@gmail.com wrote: If you need to implement this for some project then python and java have a very nice library Saurabh Singh B.Tech (Computer Science) MNNIT blog:geekinessthecoolway.blogspot.com On Sun, Dec 23, 2012 at 7:48 PM, shady sinv...@gmail.com wrote: http://stackoverflow.com/questions/13144590/to-check-if-two-strings-match-with-alphabets-digits-and-special-characters any solution for this. we need to implement such regex tester some complex cases : *string** regex * - * status* * * reesd re*.d - match re*eed reeed - match can some one help with this ? -- -- --
Re: [algogeeks] Regex tester
Well I can tell you Something about design pattern to solve this case.. What I mean is by using The State Machine Design Pattern, Anyone can solve this. but Ofcourse it is complicated. On Sun, Dec 23, 2012 at 11:01 PM, shady sinv...@gmail.com wrote: that's the point, Have to implement it from scratch... otherwise java has regex and matcher, pattern to solve it... On Sun, Dec 23, 2012 at 10:28 PM, saurabh singh saurab...@gmail.comwrote: If you need to implement this for some project then python and java have a very nice library Saurabh Singh B.Tech (Computer Science) MNNIT blog:geekinessthecoolway.blogspot.com On Sun, Dec 23, 2012 at 7:48 PM, shady sinv...@gmail.com wrote: http://stackoverflow.com/questions/13144590/to-check-if-two-strings-match-with-alphabets-digits-and-special-characters any solution for this. we need to implement such regex tester some complex cases : *string** regex * - * status* * * reesd re*.d - match re*eed reeed - match can some one help with this ? -- -- -- --