Matcher.java

package regex.parser;

import javafx.util.Pair;
import java.util.ArrayList;
import java.util.Stack;


public class Matcher {
    private FSA fsa;

    private Matcher(FSA fsa) {
        this.fsa = fsa;
    }

    public static Matcher createMatcher(String pattern) {
        FSA fsa = new FSA(pattern);
        if (fsa.isBuildSuccess()) {
            return new Matcher(fsa);
        }

        return null;
    }

    public boolean isMatch(String inputString) {
        return fsa.isMatch(inputString);
    }
}


class FSA {
    private static class State {
        boolean terminal = false;
        boolean anyChar = false;
        char charToState;

        State nextStateDirect = null;
        ArrayList<State> otherWays = new ArrayList<>();
    }

    private State start = new State();

    FSA(String pattern) {
        if (pattern == null) {
            start = null;
            return;
        }

        if (pattern.length() == 0) {
            start.terminal = true;
            return;
        }

        // Only vertexes with chars without * modifier
        State currentState = start;
        char[] patternArray = pattern.toCharArray();
        for (int i = 0; i < patternArray.length; i++) {
            char c = patternArray[i];
            if (c == '*') {
                continue;
            }

            State state = new State();
            if (c == '.') {
                state.anyChar = true;
            } else {
                state.charToState = c;
            }


            if (i < patternArray.length - 1 && patternArray[i + 1] == '*') {
                if (i == patternArray.length - 2) {
                    currentState.terminal = true;
                }
                currentState.otherWays.add(state);
                for (State otherState : currentState.otherWays) {
                    if (i == patternArray.length - 2) {
                        otherState.terminal = true;
                    }
                    otherState.otherWays.add(state);
                }
            } else {
                if (i == patternArray.length - 1) {
                    state.terminal = true;
                }
              currentState.nextStateDirect = state;
              for (State otherState : currentState.otherWays) {
                  otherState.nextStateDirect = state;
              }
              currentState = state;
            }
        }
    }

    boolean isBuildSuccess() {
        return start != null;
    }


    boolean isMatch(String input) {
        if (input.length() == 0) {
            return start.terminal;
        }

        // Node : visited node
        // Integer : counter of visited node ways out
        Stack<Pair<State, Integer>> visited = new Stack<>();
        int i = 0;

        visited.push(new Pair<>(start, -1));

        while (i < input.length()) {
            if (visited.empty()) {
                return false;
            }
            Pair<State, Integer> peeked = visited.peek();

            State nextDirect = peeked.getKey().nextStateDirect;
            ArrayList<State> otherDirections = peeked.getKey().otherWays;
            int checkCounter = peeked.getValue();

            // If there's way by next node
            if (checkCounter == -1) {
                visited.pop();
                visited.push(new Pair<>(peeked.getKey(), checkCounter + 1));

                if (nextDirect != null && (nextDirect.charToState == input.charAt(i) || nextDirect.anyChar)) {
                    ++i;
                    visited.push(new Pair<>(nextDirect, -1));
                }

            // If exists way through repeatable symbols
            } else if (checkCounter < otherDirections.size()) {
                visited.pop();
                visited.push(new Pair<>(peeked.getKey(), checkCounter + 1));

                if ((otherDirections.get(checkCounter).charToState == input.charAt(i) ||
                        otherDirections.get(checkCounter).anyChar)) {
                    ++i;
                    visited.push(new Pair<>(otherDirections.get(checkCounter), -1));
                }

            // If there's no way from current state
            } else if (!visited.empty()) {
                // Going back
                visited.pop();
                --i;
            }
        }

        if (visited.empty()) {
            return false;
        }

        return visited.peek().getKey().terminal;
    }
}