71. Simplify Path

原题：

Given an absolute path for a file (Unix-style), simplify it.

For example,
path = "/home/", => "/home"
path = "/a/./b/../../c/", => "/c"

click to show corner cases.

Corner Cases:

• Did you consider the case where path = "/../"?
  In this case, you should return "/".
• Another corner case is the path might contain multiple slashes '/' together, such as "/home//foo/".
  In this case, you should ignore redundant slashes and return "/home/foo".

思考过程：

一开始分很多情况进行操作，后来干脆用了自动机，不同状态进行不同处理。用ArrayList实现一个栈存储已经遍历过的目录，遇到"/../"就出栈。

几个终态含义：4表示/../；6表示/./；7表示正常目录。

AC代码：

ArrayList<String> stack = new ArrayList<>();
    int stackTop = -1;
    String currentString = "/";
    int state = 1;//标识自动机状态

    public String simplifyPath(String path) {
        String ret = "";
        int len = path.length();
        for (int i = 0;i < len;i++){
            char c = path.charAt(i);
            if (c != '/') currentString += c;
            int[] reslutState = new int[3];
            switch (state){
                case 1:{
                    reslutState[0] = 1;
                    reslutState[1] = 2;
                    reslutState[2] = 5;
                    break;
                }
                case 2:{
                    reslutState[0] = 6;
                    reslutState[1] = 3;
                    reslutState[2] = 5;
                    break;
                }
                case 3:{
                    reslutState[0] = 4;
                    reslutState[1] = 5;//"..."算是路径
                    reslutState[2] = 5;
                    break;
                }
                case 5:{
                    reslutState[0] = 7;
                    reslutState[1] = 5;
                    reslutState[2] = 5;
                    }
            }
            if (state != 4 && state != 7) state = changeState(state,c,reslutState);//非终点集转换状态即可
            if (state == 4 || state == 7 || state == 6)manageEndpoint(state);
        }
        if (currentString.charAt(currentString.length() - 1) != '/') {//处理最后一段不以'/'结尾的路径
            if (state == 5)
                push();
            if (state == 3)
                pop();
        }
        if (stackTop == -1) return "/";
        for (int i = 0;i <= stackTop;i++) ret += stack.get(i);
        return ret;
    }

    /*
    出栈函数
     */
    public void pop(){
        if (stackTop > -1) {
            stack.remove(stackTop);
            stackTop--;//遇到".."的情况要返回上级目录，也就是出栈
        }
    }
    /*
    入栈函数
     */
    public void push(){
        String s = currentString;
        stack.add(s);
        stackTop++;
    }

    public void manageEndpoint(int state){
        switch (state){//终点集要进行处理
            case 4:{
                pop();
                break;
            }
            case 7 :
                push();//放入此段路径
        }
        this.state = 1;//处理完此目录路径，恢复初始状态
        currentString = "/";//当前字符串也恢复初始状态
    }
    public int changeState(int state,char c,int[] resultState){//用于切换自动机状态
        switch (c){
            case '/':{
                state = resultState[0];
                break;
            }
            case '.':{
                state = resultState[1];
                break;
            }
            default:{
                state = resultState[2];
            }
        }
        return state;
    }