CareerCup

store in the stack array only the string between /and/.
Once u find .. pop the stack.
when u find . ignore it

At the end the stack can be read for the absolute path.

We can also use java strings with function lastindexOf() to attain the same.

-Sachin

Initially I told him one recursive solution then he asked me to implement using efficient algorithm so i implemented it using double linked list.

procedure:

1)get tokens of input string
2)create double linked list node for each token
3) parse the list if you find .. back track two positions and point to the next node of .. in list ,so we can get new list or if we have found . then backtrack one node and delete . node and pointer to next node

4)Repeat step3 for all nodes

5)Now traverse double linked list it will give u absolute path.

How about stack? The stack is simpler to handle than the doubly linked list. However the approach is the same.

are you given the relative path as a string ? well tahts the assumption my soln is based on.
1. initialize an output array of size equal to the input string, and maintain a counter, initialised to 0.
2. read the string in reverse order.. ie. keep a pointer pi for the input array, pointer po for the output array and progress them from back to front. initilaize both pi and po to len(i/p string)
4. when you come across a "\.", freeze po, but let pi continue
5. when you come across a "\..", , freeze po, increment the counter and let pi continue. Repeat (6.) for the number of times you see a continuos "\..", Once you encounter no more "\.."s, allow pi to continue beyond this for the number of times specified by the counter. po should remain frozen all this time. Now reset the counter and loop through 4,5,6.
6. if its any other character..write the character at pi to po and progress both (pi, po)
7. loop through 4,5,6.
8. the output string could be well shorter than the input,so the output string could contain a lot of blanks/gibberish before the actual answer but you can jus return the pointer po.. works well with strings !

what abt using unis subsitute .

just used reg ex /\/.*\//\/

How about using a stack and popping up the element when we encounter .. ?

Input . in the path string needs to be ignored in this case.

I have a simple tested program which uses a stack(AStack.java):

public class AStack
{
protected Object head[];
protected int pointer;
public AStack() {
head=new Object[10];
pointer=-1;
}
public AStack(int capacity) {
head=new Object[capacity];
pointer=-1;
}
public int size() {
return pointer;
}
public boolean isEmpty() {
return pointer==-1;
}
public void push(Object i) {
if(pointer+1 <head.length)
head[++pointer]=i;
}
public Object pop() {
if(isEmpty())
return null;
return head[pointer--];
}
}
The program is as follows(cd.java):
import java.util.*;
public class cd
{
public cd() {
}
public static void print(AStack stack) {
String str=new String((String)stack.pop());
if(str.equals("."))
return;
else
print(stack);
System.out.print("\\"+str);
}
public static void main(String[] args)
{
AStack stack=new AStack();
stack.push(".");
StringTokenizer tmp = new StringTokenizer(args[0],"\\");
while(tmp.hasMoreElements())
{ String str=new String((String)tmp.nextElement());
//if(str!= ".." && str!= ".")
if( str.equals(".."))
stack.pop();
else if(!str.equals("."))
stack.push(str);
else
continue;
}
cd.print(stack);
}
}
Program input:
>java cd C:\Dir1\Dir2\..\Dir3\.\Dir4\helloworld.txt
Program output:\C:\Dir1\Dir3\Dir4\helloworld.txt

The program expects correct data input as command line argument.

Always keen to hear suggestions and implement them..

here is the sample code(:-

public static void main(String args[])
{
String s= "C:\Dir1\Dir2\..\Dir3\.\Dir4\Dir5";
int i = s.indexOf("..",s);
while(i!=-1)
{
if(i==s.length()-2) \\incase .. is at end of string
s = s.substring(0,s.lastindexOf("\",i-2));
else
s = s.substring(0,s.lastindexOf("\",i-2)) + s.substring(i+2);
i = s.indexOf("..",s);
}

i = s.indexOf(".",s);
while(i!=-1)
{
if(i==s.length()-1) \\incase . is at end of string
s = s.substring(i-1);
else
s = s.substring(i-1) + s.substring(i+1);
i = s.indexOf(".",s);
}

System.out.println(s);
}

No need of any external datastructure i feel.. It wil simply complicate things. I have an algorithm that solves in O(n). Just parse this string from back. and when u encounter "." or ".." perform necessary actions. How about it guys.

Here is the code. Do the necessary modifcations.

#include "stdafx.h"

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

#include <string.h>

void remove_char(char **string)
{
int count = 0;
//char *ptr1 = *string;
char *ptr2 = *string;
while((*string)[count] != '\0')
{
if((*string)[count] == '.')
{
if((*string)[count + 1] == '.')
{

}
else
{
while(*ptr2 != '/')
{
*ptr2 = ' ';
ptr2--;

}
}
ptr2 = (*string) + count;
}
ptr2++;
count++;
//(*string)++;
}
}

void remove_char_opposite(char **string)
{
int length = strlen(*string);
char *ptr = (*string) + length -1;

while(length != 0)
{
if((*string)[length] == '.')
{
if((*string)[length-1] == '.')
{
int countofslashfound = 0;

while(countofslashfound != 2)
{
if((*string)[length] == '/')
{
countofslashfound+=1;
}
(*string)[length] = ' ';
length--;
}
}
else if((*string)[length-1] == '/')
{
int countofslashfound = 0;

while(countofslashfound != 1)
{
if((*string)[length] == '/')
{
countofslashfound+=1;
}
(*string)[length] = ' ';
length--;
}
}
}
length--;
}
}

int main()
{

char *string = (char *)malloc(sizeof(char));
strcpy(string,"C:/Dir1/Dir2/../Dir3/./Dir4/helloworld.txt");

remove_char(&string);

printf("String after reversal = %s",string);

}

Algo goes here:

AbsolutePath( string relativePath , string &absolutePath )
{
step 1: Maniuplate the string with / baais and start a loop.
step 2: do
step 3: switch ( dir )
step 4: case "..": pop from stack
step 5: defalut : push to stack
step 6: done
step 7: iterate the stack and form the string
step 8: if absolutePath.empty() then
step 9: absolutePath = s.pop();
step 10: else
step 11: absolutePath = s.pop() +"\" + absoultePath
}

how about just simple regexes? substitute <dirname>\.. with empty string and \. with empty string
which means c:\dir1\dir2\..\dir3\.\sometext.txt becomes c:\dir1\dir3\sometext.txt ? shouldnt that work?

Java program:
File temp = new File(str)
print temp.getAbsolutePath()

:D

scan the string token-wise (delimited by "/") from the right to the left; maintain a global variable the number of "..": incremental the global variable when visiting it and decrement it when a token is not ".." and the global variable is positive.

code in c++

main()
{
    string str="C:/Dir1/../Dir2/../Dir3/./Dir4/./helloworld.txt";

    int count=str.find("/..");

    while( count != string::npos)
    {
       int b=str.find_last_of("/",count-1);
       string s1=str.substr(0,b);
       string s2=str.substr(count+3);
       str= s1 + s2;
       cout<<str<<"\n";
       count=str.find("/..");
    }
    count=str.find("/./");

    while( count != string::npos)
    {
       str.replace(count,3,"/");
       count=str.find("/./");
    }

    cout<<str;

}

code in c++

main()
{
    string str="C:/Dir1/../Dir2/../Dir3/./Dir4/./helloworld.txt";

    int count=str.find("/..");

    while( count != string::npos)
    {
       int b=str.find_last_of("/",count-1);
       string s1=str.substr(0,b);
       string s2=str.substr(count+3);
       str= s1 + s2;
       cout<<str<<"\n";
       count=str.find("/..");
    }
    count=str.find("/./");

    while( count != string::npos)
    {
       str.replace(count,3,"/");
       count=str.find("/./");
    }

    cout<<str;

}

File temp = new File(input);
System.out.println( temp.getCanonicalPath());