CareerCup

Will the input always start with / and consist only of folder/file names or . or .. separated by slashes? If so, I can make a stack and every time I see a name, I push it on the stack, every time I see . I ignore that, and every time I see .., I will pop the top element off the stack. At the end I'll pop off all the stack elements into a list, reverse the list, and print out /element for each element, so I'll get /element1/element2/element3 and so on.

Split string with / e.g. Path.Split("/")
ignore leading and trailing /
for each string push to stack
for each .. pop from stack
e.g. windows/abs/../temp/new/.../

Push windows
Push abs
pop abs
push temp
push new
pop new

you will be left with windows/temp

I think we can use a doubly linked list. Wheneever we get a path we create a new node and when we get .. we move to previous node and delete the next node
i.e for /windows/abs/../temp/new/.../
first you will get windows
windows -> null
now you got abs
windows -> abs
now .., which means move back and delete the node
windows
now you got temp
windows -> temp
now you got new
windows -> temp -> new
now you got ..
windows -> temp

So this is the absolute path

public static void main(String[] args)
    {
        String path = "/windows/abs/../temp/new/../";
        
        Stack<String> parts = new Stack<String>();
        
        String part;
        int start = 0;
        for(int i = start; i< path.length(); i++)
        {
            if(path.charAt(i) == '/')
            {
                part = path.substring(start, i);
                start = i + 1;
                
                if(part.isEmpty()) continue;
                
                if(part.equals(".."))
                {
                    if(parts.isEmpty())
                    {
                        throw new IllegalArgumentException();
                    }
                    else
                    {
                        parts.pop();
                    }
                }
                else
                {
                    parts.push(part);
                }
            }
        }
        
        Stack<String> result = new Stack<String>();
        while(!parts.isEmpty())
        {
            result.push(parts.pop());
        }

        if(result.isEmpty())
        {
            System.out.print("/");
        }
        else
        {
            while(!result.isEmpty())
            {
                System.out.print("/");
                System.out.print(result.pop());
            }
        }
    }

for the Ruby crowd

def absolute_path(path)
	abs_path = Array.new
	path.split("/").each do | f |
		if f.include?("..")
			abs_path.pop unless abs_path.empty?
		else
			abs_path.push(f)
		end
	end
	return abs_path.join("/")
end

my c++ based program. Using only stl: stack as helper.
No other stl or library is used (not even C++ string).
Hope it helps from-scratch implementation. Thanks @eugene.yarovoi for providing the idea. Though, I came up with the same logic but since u posted here earlier than me so I think acknowledgement is due :)

#include<iostream>
#include<cstring>
#include<stack>

using namespace std;

struct ll
{
	char *str;
	int len;
	// ll *next;
	
	ll(char* a=0, int l=0): str(a), len(l){}
};

void static clearStack(stack<ll*> &st)
{
	while(!st.empty())	
	{
		ll* temp = st.top();
		st.pop();
		delete(temp);
	}
	return;
}


void printStr(char* ptr, int len)
{ 
	if(!ptr || len == 0)
		return;
	for(int i=0; i<len; i++)
		cout << ptr[i];
}
void printPath(stack<ll*> &st)
{
	while(!st.empty())
	{
		ll* node = st.top();
		st.pop();
		printPath(st);
		printStr(node->str, node->len);
		delete(node);
		cout << "/";
	}
}
void relToAbs(char *rpath, int len)
{
	// STATE MACHINE TO PROCESS THE RELATIVE PATH STRING
	stack<ll*> st;
	char *aName = NULL;
	for(int  i=0; rpath[i] != '\0' && i<len; /* i++ */)
	{
		if(rpath[i] == '/')
		{
			i++;
		}
		else if(rpath[i] == '.')
		{
			if(rpath[++i] == '.')
			{
				if(!st.empty())
				{
					ll *aNode = st.top();
					st.pop();
					delete(aNode);
				}
				++i;
			}
		}
		else if(tolower(rpath[i]) >= 'a' && tolower(rpath[i]) <= 'z')// character is seen
		{
			aName = &rpath[i];
			int size = i;
			while(tolower(rpath[i]) >= 'a' && tolower(rpath[i]) <= 'z')
				i++;
			st.push(new ll(aName, i-size));
		}
		else
		{
			cout << "ill-formed path" << endl;
			clearStack(st);
			return ;
		}
	}
	//------------------------------------------------------
	
	return printPath(st);
	
}

void relToAbsDriver()
{
	char* str = "/windows/abs/../temp/new/../$";
	relToAbs(str, strlen(str));

	cout << endl << "--------------------------------" << endl;	
}