Regular expression matcher

ToPostfix.java

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);
            }
        }
    }
}