CareerCup

import java.util.Stack;

public class canonical {

	
	public static void main(String arg[])
	{
		String path = "e/../../a/d/./../b/c";
		String cPath = getCanonicalPath(path);
		System.out.println(cPath);
	}
	
	public static String getCanonicalPath(String path)
	{
		Stack<String> directoryStack = new Stack<String>();
		for(String token: path.split("/"))
		{
			switch(token)
			{
			case "..":
				if(!directoryStack.isEmpty() && directoryStack.peek()!="..")
				{
					directoryStack.pop();
				}
				else
				{
					directoryStack.push("..");
				}
				break;
			case ".":
				break;
			default:
				directoryStack.push(token);
			
			}
		}
		
		StringBuffer cPath = new StringBuffer();
		for(String directory: directoryStack)
		{
		cPath.append(directory + "/");
		}
		return cPath.toString();
	}
}

public static String getCanonicalPath(String input){
		if(input==null||input.trim().length()==0){
			return null;
		}
		
		String[] path = input.split("/");
		Stack<String> canonicalForm = new Stack<String>();
		StringBuilder sb = new StringBuilder();
		for(String token:path){
			if(token.equals("..")){
			if(!(canonicalForm.isEmpty())&&canonicalForm.peek()!=".."){
				sb.append(canonicalForm.pop()+"/");
			}
			}else if(token.equals(".")){
				System.out.println("Skipping .");
			}else{
				canonicalForm.push(token);
			}
		}
		
		for(String token:canonicalForm){
			sb.append(token+"/");
		}
		return sb.toString();
		
	}

Can you please elaborate more on what is a canonical form. Still not clear what is the desired output

Can you please elaborate more on what is canonical form. Its still not clear.

Still feels like too much code!

std::string CanonicalPath(const char* pPath){
   std::string rval;
   std::vector<std::string> stack;
   int up = 0;
   while (*pPath){
      if (pPath[0] == '.'){
         if (pPath[1] == '.'){
            if (stack.size())
               stack.pop_back();
            else
               up++;
         }
         pPath += 2 + (pPath[1] == '.');
      }
      else{
         const char* pEnd = strchr(pPath, '/');
         if (!pEnd)
            pEnd = pPath + strlen(pPath);
         stack.push_back(std::string(pPath, pEnd - pPath));
         pPath = pEnd + 1;
      }
   }
   for (int i = 0; i < up; i++)
      rval += "../";
   for (auto& s : stack)
      rval += s + '/';
   return rval;
}

void main()
{
   std::cout << CanonicalPath("e/../../a/d/./../b/c");
   getch();
}

output:

../a/b/c/

Not efficient, since have to reverse at the end, but looks nice.

def canonicalPath(path: String): String = { 
  assert(path != null || !path.isEmpty)

  def resolve(ps: List[String]): List[String] = { 
    ps.foldLeft (List[String]()) { (acc, x) =>  
      if (x.equals(".."))
        acc.tail
      else if (x.equals("."))
        acc 
      else 
        x :: acc 
    }   
  }
  
  val ps = path.split('/')
  resolve(ps.toList).reverse.mkString("/")
}

#include <stdlib.h>
#include <stdio.h>
#include <string.h>

struct Node {
  struct Node *parent;
  char *name;
};

typedef struct Node Node;

Node *processToken(char *name, Node *current) {
  if (strcmp(name, ".") == 0) {
    return current;
  } else if (strcmp(name, "..") == 0) {
    if (current != NULL && current->parent != NULL) {
      return current->parent;
    } else {
      Node *node = malloc(sizeof(Node));
      node->name = name;
      node->parent = NULL;
      if (current != NULL) {
        current->parent = node;
      }
      return node;
    }
  } else {
      Node *node = malloc(sizeof(Node));
      node->parent = current;
      node->name = name;
      return node;
  }
}

void printNode(Node *node) {
  if (node == NULL) {
    return;
  }
  if (node->parent != NULL) {
    printNode(node->parent);
    printf("/");
  }
  printf("%s", node->name);
}

char *mystrsep(char **ps) {
  char *o = *ps;
  if (*o == '\0') {
    return NULL;
  }
  while (**ps != '/' && **ps != '\0') {
    (*ps)++;
  }
  if (**ps == '/') {
    **ps = '\0';
    (*ps)++;
  }
  return o;
}

int main(int argc, char **argv) {
  Node *current = NULL;
  char *s = strdup("e/../../a/d/./../b/c");
  char *token = NULL;
  while ((token = mystrsep(&s)) != NULL) {
    current = processToken(token, current);
  }
  printNode(current);
  printf("\n");
  return 0;
}

Here is my solution based only on simple arrays. I consider also one additional interesting case, when our path is not relevance and it is absolute, for example, /etc/../.././../usr/" -> "/usr"or "C:/..Windows/./systems32/../../temp/." - > "C:/temp"

import java.io.File;
import java.io.IOException;

/**
 * Created by Igor_Sokolov on 3/12/2015.
 */
public class CarrerCup_5634050834300928 {
    public static void main(String[] args) throws IOException {
        String tests[] = {"e/../../a/d/./../b/c", "/etc/../.././../usr/", "C:/../Windows/./systems32/../../temp/."};
        for (int i = 0; i < tests.length; i++) {
            String path = getCanonicalPath(tests[i]);
            System.out.println(path);
        }
    }

    private static String getCanonicalPath(String line) {
        if (line.isEmpty()) {
            throw new RuntimeException("invalid path");
        }

        String root = extractRoot(line);
        if (root != null) {
            line = line.substring(root.length());
        }

        String[] terms = line.split("/");

        int j = 0;
        String[] result = new String[terms.length];

        int stepUp = 0;
        int i = terms.length - 1;
        while (i >= 0) {
            final String term = terms[i--];
            if (term == null || term.isEmpty()) {
                throw new RuntimeException("invalid path");
            }

            if (term.equals(".")) {
                continue;
            }

            if (term.equals("..")) {
                stepUp++;
                continue;
            }

            if (stepUp != 0) {
                stepUp--;
            } else {
                result[j++] = term;
            }
        }

        StringBuilder sb = new StringBuilder();
        if (root != null) {
            sb.append(root);
        }

        for (int k = j - 1; k >= 0; k--) {
            if (k != j - 1) {
                sb.append('/');
            }

            sb.append(result[k]);
        }

        return sb.toString();
    }

    private static String extractRoot(String line) {
        int pos = line.indexOf('/');
        // we assume this is unix path, for example "/etc/hosts"
        if (pos == 0) {
            return "/";
        }

        // maybe this is windows path, for example "C:/widows/system32"
        String root = line.substring(0, pos + 1);
        if (root.contains(":")) {
            return root;
        }

        return null;
    }


}

You don't need a stack for this. One can just use a doubly linked list with one pointer pointing to the head and another to the tail end. Back up one node if the next element in the path is ".." and you are not at the head, and add a node if the next element in the path is not "..". Read off the labels on the nodes from head to tail when you are done. No need to reverse the string.

def f(a) {
    def p = a.replaceAll(/\/\.\//,'//').replaceAll(/\/\//,'/').replaceAll(/[^.\/]+\/\.\.\//,'').replaceAll(/[^.\/]+\/\.\./,'')
    if (a != p) p = f(p)
    p
}
f('e/../../a/d/./../b/c');

def f(a) {
    def p = a.replaceAll(/\/\.\//,'//').replaceAll(/\/\//,'/').replaceAll(/[^.\/]+\/\.\.\//,'').replaceAll(/[^.\/]+\/\.\./,'')
    if (a != p) p = f(p)
    p
}
f('e/../../a/d/./../b/c'); // . ./a/b/c

public static String getCanonical(String path){
		
		String[] dir= path.split("/");
		LinkedList<String> stack = new LinkedList<String>();	
		for(String s:dir){
			if(s.equals(".")){		
				continue;
			}
			else if(s.equals("..")){				
				if(!stack.isEmpty())
					stack.pop();	
			}
			else{		
				stack.push(s);		
			}
		}
		
		StringBuilder sb = new StringBuilder();
		while(!stack.isEmpty()){
			sb.append(stack.pop());
			sb.append('/');
		}
		sb.deleteCharAt(sb.length()-1);
		return sb.reverse().toString();
	}

Here is my take, which supports going back further than the current directory.

Test cases

java StackTest "../asdf/../test/./es/../icles"
../test/icles

java StackTest "this/../test/es"
test/es

java StackTest "next/.."
.

Code:

import java.util.*;
public class StackTest {
	public static void main(String[] args) {
		System.out.println(getCanonical(args[0]));

	}
	public static String getCanonical(String path) {
		LinkedList<String> stack = new LinkedList<String>();
		StringBuilder sb = new StringBuilder();
		String[] parts = path.split("\\/");
		for(int i = 0; i < parts.length; i++) {
			String part = parts[i];
			if(part.equals("..") && stack.size()>0 && !stack.peek().equals("..")) {
				stack.pop();
			} else if(!part.equals(".")) {
				stack.push(parts[i]);
			}
		}
		if(stack.size()==0)
			sb.append(".");
		else
			sb.append(stack.removeLast());
		while(stack.size()>0) {
			sb.append("/");
			String item = stack.removeLast();
			sb.append(item);
		}
		return sb.toString();
	}
}

I already tried posting it once, but here's my take:

import java.util.*;
public class StackTest {
	public static void main(String[] args) {
		System.out.println(getCanonical(args[0]));

	}
	public static String getCanonical(String path) {
		LinkedList<String> stack = new LinkedList<String>();
		StringBuilder sb = new StringBuilder();
		String[] parts = path.split("\\/");
		for(int i = 0; i < parts.length; i++) {
			String part = parts[i];
			if(part.equals("..") && stack.size()>0 && !stack.peek().equals("..")) {
				stack.pop();
			} else if(!part.equals(".")) {
				stack.push(parts[i]);
			}
		}
		if(stack.size() == 0)
			sb.append(".");
		else
			sb.append(stack.removeLast());
		while(stack.size()>0) {
			sb.append("/");
			String item = stack.removeLast();
			sb.append(item);
		}
		return sb.toString();
	}
}

use stack