Created
January 23, 2017 02:00
-
-
Save phamtm/79e67a91a98ad1a17e7d68d58726a2b0 to your computer and use it in GitHub Desktop.
Regular expression matcher
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
package mp; | |
import java.util.ArrayDeque; | |
import java.util.Deque; | |
public class ToPostfix { | |
/** | |
* Don't handle error | |
* missing: escape char | |
* | |
* @param re String | |
* @return String | |
*/ | |
private static String toPostFix(String re) { | |
Deque<Character> s = new ArrayDeque<>(); | |
StringBuilder b = new StringBuilder(); | |
char c; | |
boolean concat = false; | |
for (int i = 0; i < re.length();) { | |
c = concat ? '.' : re.charAt(i); | |
switch (c) { | |
case '(': | |
s.push(c); | |
break; | |
case ')': | |
while (s.peek() != '(') | |
b.append(s.pop()); | |
s.pop(); // pop the '(' | |
break; | |
default: // normal char | |
while (!s.isEmpty()) { | |
if (precedence(c) <= precedence(s.peek())) | |
b.append(s.pop()); | |
else | |
break; | |
} | |
s.push(c); | |
break; | |
} | |
// append a '.' as concatenation operator if needed | |
concat = false; | |
if (c != '.' && i < re.length() - 1) { | |
char nextChar = re.charAt(i + 1); | |
concat = c != '(' && c != '|' && nextChar != ')' && !isMeta(nextChar); | |
} | |
if (!concat) | |
i++; | |
} | |
while (!s.isEmpty()) | |
b.append(s.pop()); | |
return b.toString(); | |
} | |
private static boolean isMeta(char c) { | |
return c == '?' || c == '*' || c == '+' || c == '|'; | |
} | |
private static int precedence(char c) { | |
switch (c) { | |
case '(': return 1; | |
case '.': return 2; | |
case '|': return 3; | |
case '+': return 4; | |
case '?': return 4; | |
case '*': return 4; | |
default: return 5; //why | |
} | |
} | |
public static void main(String[] args) { | |
String[] patterns = { | |
"a?", "a?", // 1 | |
"a?a", "a?a.", | |
"aa?b", "aa?.b.", | |
"a(bb)", "abb..", | |
"a(b?b)", "ab?b..", // 5 | |
"a(bb)?", "abb.?.", | |
"(ab)b", "ab.b.", | |
"(ab)?b", "ab.?b.", | |
"(a(bb))c", "abb..c.", | |
"(a(b|b))c", "abb|.c.", // 10 | |
"(a(bb)?)?c", "abb.?.?c.", | |
"a|b", "ab|", | |
"a|b|c", "ab|c|", | |
"aa|b", "aab|.", | |
"aa|b|c", "aab|c|.", //15 | |
"aa|bb", "aab|.b.", | |
"a(b|c)|d", "abc|d|.", | |
"aa|(bb|cc)", "aabbc|.c.|.", | |
"aa|(b(b|c)c)", "aabbc|.c.|.", | |
"aa|(b|cc)|d", "aabc|c.|d|.", // 20 | |
}; | |
for (int i = 0; i < patterns.length; i += 2) { | |
String re = patterns[i]; | |
boolean correct = toPostFix(re).equals(patterns[i+1]); | |
if (correct) { | |
System.out.println("Test " + i/2 + " passed"); | |
} else { | |
String err = String.format( | |
"Test [%2d] FAILED, expected %s, actual %s", i/2+1, patterns[i+1], toPostFix(re)); | |
System.out.println(err); | |
} | |
} | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment