Dada una ruta absoluta para un archivo (estilo Unix), simplifique. Tenga en cuenta que la ruta absoluta siempre comienza con ‘/’ (directorio raíz), un punto en la ruta representa el directorio actual y un punto doble representa el directorio principal.
Ejemplos:
"/a/./" --> means stay at the current directory 'a'
"/a/b/.." --> means jump to the parent directory
from 'b' to 'a'
"////" --> consecutive multiple '/' are a valid
path, they are equivalent to single "/".
Input : /home/
Output : /home
Input : /a/./b/../../c/
Output : /c
Input : /a/..
Output:/
Input : /a/../
Output : /
Input : /../../../../../a
Output : /a
Input : /a/./b/./c/./d/
Output : /a/b/c/d
Input : /a/../.././../../.
Output:/
Input : /a//b//c//////d
Output : /a/b/c/d
Nota: La entrada dada siempre tendrá una ruta absoluta válida.
Enfoque 1: al observar los ejemplos, podemos ver que el proceso de simplificación anterior simplemente se comporta como una pila . Cada vez que encontramos el nombre de cualquier archivo, simplemente lo empujamos a la pila. cuando nos cruzamos”. » no hacemos nada. Cuando encontramos «..» en nuestra ruta, simplemente sacamos el elemento superior ya que tenemos que volver al directorio principal.
Cuando vemos múltiples «////» simplemente los ignoramos ya que son equivalentes a un solo «/». Después de iterar a través de toda la string, los elementos que quedan en la pila son nuestra ruta absoluta simplificada. Tenemos que crear otra pila para invertir los elementos almacenados dentro de la pila original y luego almacenar el resultado dentro de una string.
Implementación:
C++
/* C++ program to simplify a Unix
styled absolute path of a file */
#include <bits/stdc++.h>
using namespace std;
// function to simplify a Unix - styled
// absolute path
string simplify(string A)
{
// stack to store the file's names.
stack<string> st;
// temporary string which stores the extracted
// directory name or commands("." / "..")
// Eg. "/a/b/../."
// dir will contain "a", "b", "..", ".";
string dir;
// contains resultant simplifies string.
string res;
// every string starts from root directory.
res.append("/");
// stores length of input string.
int len_A = A.length();
for (int i = 0; i < len_A; i++) {
// we will clear the temporary string
// every time to accommodate new directory
// name or command.
dir.clear();
// skip all the multiple '/' Eg. "/////""
while (A[i] == '/')
i++;
// stores directory's name("a", "b" etc.)
// or commands("."/"..") into dir
while (i < len_A && A[i] != '/') {
dir.push_back(A[i]);
i++;
}
// if dir has ".." just pop the topmost
// element if the stack is not empty
// otherwise ignore.
if (dir.compare("..") == 0) {
if (!st.empty())
st.pop();
}
// if dir has "." then simply continue
// with the process.
else if (dir.compare(".") == 0)
continue;
// pushes if it encounters directory's
// name("a", "b").
else if (dir.length() != 0)
st.push(dir);
}
// a temporary stack (st1) which will contain
// the reverse of original stack(st).
stack<string> st1;
while (!st.empty()) {
st1.push(st.top());
st.pop();
}
// the st1 will contain the actual res.
while (!st1.empty()) {
string temp = st1.top();
// if it's the last element no need
// to append "/"
if (st1.size() != 1)
res.append(temp + "/");
else
res.append(temp);
st1.pop();
}
return res;
}
// Driver code.
int main()
{
// absolute path which we have to simplify.
string str("/a/./b/../../c/");
string res = simplify(str);
cout << res;
return 0;
}
Java
/* Java program to simplify a Unix
styled absolute path of a file */
import java.io.*;
import java.util.*;
class GFG
{
public static void main(String []args)
{
// absolute path which we have to simplify.
String str = new String("/a/./b/../../c/");
String res = simplify(str);
System.out.println(res);
}
// function to simplify a Unix - styled
// absolute path
static String simplify(String A)
{
// Stack to store the file's names.
Stack<String> st = new Stack<String>();
// temporary String which stores the extracted
// directory name or commands("." / "..")
// Eg. "/a/b/../."
// contains resultant simplifies String.
String res = "";
// every String starts from root directory.
res += "/";
// stores length of input String.
int len_A = A.length();
for (int i = 0; i < len_A; i++)
{
// we will clear the temporary String
// every time to accommodate new directory
// name or command.
// dir will contain "a", "b", "..", ".";
String dir = "";
// skip all the multiple '/' Eg. "/////""
while (i < len_A && A.charAt(i) == '/')
i++;
// stores directory's name("a", "b" etc.)
// or commands("."/"..") into dir
while (i < len_A && A.charAt(i) != '/')
{
dir += A.charAt(i);
i++;
}
// if dir has ".." just pop the topmost
// element if the Stack is not empty
// otherwise ignore.
if (dir.equals("..") == true)
{
if (!st.empty())
st.pop();
}
// if dir has "." then simply continue
// with the process.
else if (dir.equals(".") == true)
continue;
// pushes if it encounters directory's
// name("a", "b").
else if (dir.length() != 0)
st.push(dir);
}
// a temporary Stack (st1) which will contain
// the reverse of original Stack(st).
Stack<String> st1 = new Stack<String>();
while (!st.empty())
{
st1.push(st.pop());
// st.pop();
}
// the st1 will contain the actual res.
while (!st1.empty())
{
// if it's the last element no need
// to append "/"
if (st1.size() != 1)
res += (st1.pop() + "/");
else
res += st1.pop();
// st1.pop();
}
return res;
}
}
// This code is contributed by ankush_953
Python3
# Python program to simplify a Unix
# styled absolute path of a file
# function to simplify a Unix - styled
# absolute path
def simplify(A):
# stack to store the file's names.
st = []
# temporary string which stores the extracted
# directory name or commands("." / "..")
# Eg. "/a/b/../."
# dir will contain "a", "b", "..", ".";
dir = ""
# contains resultant simplifies string.
res = ""
# every string starts from root directory.
res += "/"
# stores length of input string.
len_A = len(A)
i = 0
while i < len_A:
# we will clear the temporary string
# every time to accommodate new directory
# name or command.
dir_str = ""
# skip all the multiple '/' Eg. "##/""
while (i < len_A and A[i] == '/'):
i += 1
# stores directory's name("a", "b" etc.)
# or commands("."/"..") into dir
while (i < len_A and A[i] != '/'):
dir_str += A[i]
i += 1
# if dir has ".." just pop the topmost
# element if the stack is not empty
# otherwise ignore.
if dir_str == "..":
if len(st):
st.pop()
# if dir has "." then simply continue
# with the process.
elif dir_str == '.':
continue
# pushes if it encounters directory's
# name("a", "b").
elif len(dir_str) > 0:
st.append(dir_str)
i += 1
# a temporary stack (st1) which will contain
# the reverse of original stack(st).
st1 = []
while len(st):
st1.append(st[-1])
st.pop()
# the st1 will contain the actual res.
while len(st1):
temp = st1[-1]
# if it's the last element no need
# to append "/"
if (len(st1) != 1):
res += (temp + "/")
else:
res += temp
st1.pop()
return res
# Driver code.
# absolute path which we have to simplify.
string = "/a/./b/../../c/"
res = simplify(string)
print(res)
# This code is contributed by ankush_953
C#
// C# program to simplify a Unix
// styled absolute path of a file
using System;
using System.Collections.Generic;
class GFG
{
public static void Main(String []args)
{
// absolute path which we have to simplify.
String str = ("/a/./b/../../c/");
String res = simplify(str);
Console.WriteLine(res);
}
// function to simplify a Unix - styled
// absolute path
static String simplify(String A)
{
// Stack to store the file's names.
Stack<String> st = new Stack<String>();
// temporary String which stores the extracted
// directory name or commands("." / "..")
// Eg. "/a/b/../."
// contains resultant simplifies String.
String res = "";
// every String starts from root directory.
res += "/";
// stores length of input String.
int len_A = A.Length;
for (int i = 0; i < len_A; i++)
{
// we will clear the temporary String
// every time to accommodate new directory
// name or command.
// dir will contain "a", "b", "..", ".";
String dir = "";
// skip all the multiple '/' Eg. "/////""
while (i < len_A && A[i] == '/')
i++;
// stores directory's name("a", "b" etc.)
// or commands("."/"..") into dir
while (i < len_A && A[i] != '/')
{
dir += A[i];
i++;
}
// if dir has ".." just pop the topmost
// element if the Stack is not empty
// otherwise ignore.
if (dir.Equals("..") == true)
{
if (st.Count!=0)
st.Pop();
}
// if dir has "." then simply continue
// with the process.
else if (dir.Equals(".") == true)
continue;
// pushes if it encounters directory's
// name("a", "b").
else if (dir.Length != 0)
st.Push(dir);
}
// a temporary Stack (st1) which will contain
// the reverse of original Stack(st).
Stack<String> st1 = new Stack<String>();
while (st.Count!=0)
{
st1.Push(st.Pop());
// st.pop();
}
// the st1 will contain the actual res.
while (st1.Count!=0)
{
// if it's the last element no need
// to append "/"
if (st1.Count!= 1)
res += (st1.Pop() + "/");
else
res += st1.Pop();
// st1.pop();
}
return res;
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// Javascript program to simplify a Unix
// styled absolute path of a file
// function to simplify a Unix - styled
// absolute path
function simplify(A)
{
// Stack to store the file's names.
let st = [];
// temporary String which stores the extracted
// directory name or commands("." / "..")
// Eg. "/a/b/../."
// contains resultant simplifies String.
let res = "";
// every String starts from root directory.
res += "/";
// stores length of input String.
let len_A = A.length;
for (let i = 0; i < len_A; i++)
{
// we will clear the temporary String
// every time to accommodate new directory
// name or command.
// dir will contain "a", "b", "..", ".";
let dir = "";
// skip all the multiple '/' Eg. "/////""
while (i < len_A && A[i] == '/')
i++;
// stores directory's name("a", "b" etc.)
// or commands("."/"..") into dir
while (i < len_A && A[i] != '/')
{
dir += A[i];
i++;
}
// if dir has ".." just pop the topmost
// element if the Stack is not empty
// otherwise ignore.
if (dir == "..")
{
if (st.length!=0)
st.pop();
}
// if dir has "." then simply continue
// with the process.
else if (dir == ".")
continue;
// pushes if it encounters directory's
// name("a", "b").
else if (dir.length != 0)
st.push(dir);
}
// a temporary Stack (st1) which will contain
// the reverse of original Stack(st).
let st1 = [];
while (st.length!=0)
{
st1.push(st[st.length - 1]);
st.pop();
}
// the st1 will contain the actual res.
while (st1.length!=0)
{
// if it's the last element no need
// to append "/"
if (st1.length!= 1)
{
res += (st1[st1.length - 1] + "/");
st.pop();
}
else
{
res += st1[st1.length - 1];
st1.pop();
}
}
return res;
}
// absolute path which we have to simplify.
let str = ("/a/./b/../../c/");
let res = simplify(str);
document.write(res);
// This code is contributed by divyesh072019.
</script>
Producción
/c
Complejidad de tiempo: O (longitud de la string).
Enfoque 2:
- En el enfoque 1, los directorios así formados se colocan primero en la pila y luego la pila se invierte para formar la ruta canónica.
- La única optimización aquí es reducir el número de operaciones de pila y esto se puede hacer usando vectores en lugar de una pila.
- Las operaciones push y pop se pueden realizar en vector usando las funciones push_back() y pop_back() respectivamente y la ruta canónica se puede generar simplemente recorriendo el vector de izquierda a derecha.
A continuación se muestra la implementación del enfoque 1 usando vectores.
C++
// C++ implementation of optimized Approach 1
#include <bits/stdc++.h>
using namespace std;
// function to simplify a Unix - styled
// absolute path
string simplify(string path)
{
// using vector in place of stack
vector<string> v;
int n = path.length();
string ans;
for (int i = 0; i < n; i++) {
string dir = "";
// forming the current directory.
while (i < n && path[i] != '/') {
dir += path[i];
i++;
}
// if ".." , we pop.
if (dir == "..") {
if (!v.empty())
v.pop_back();
}
else if (dir == "." || dir == "") {
// do nothing (added for better understanding.)
}
else {
// push the current directory into the vector.
v.push_back(dir);
}
}
// forming the ans
for (auto i : v) {
ans += "/" + i;
}
// vector is empty
if (ans == "")
return "/";
return ans;
}
// Driver Code
int main()
{
// absolute path which we have to simplify.
string str("/a/./b/../../c/");
string res = simplify(str);
cout << res;
return 0;
}
// This code is contributed by yashbeersingh42
Java
// Java implementation of optimized Approach 1
import java.util.*;
public class Main
{
// function to simplify a Unix - styled
// absolute path
static String simplify(String path)
{
// using vector in place of stack
Vector<String> v = new Vector<String>();
int n = path.length();
String ans = "";
for (int i = 0; i < n; i++) {
String dir = "";
// forming the current directory.
while (i < n && path.charAt(i) != '/') {
dir += path.charAt(i);
i++;
}
// if ".." , we pop.
if (dir.equals("..")) {
if (v.size() != 0)
{
v.remove(v.size() - 1);
}
}
else if (dir.equals(".") || dir.equals("")) {
// do nothing (added for better understanding.)
}
else {
// push the current directory into the vector.
v.add(dir);
}
}
// forming the ans
for(String i : v) {
ans += "/" + i;
}
// vector is empty
if (ans == "")
return "/";
return ans;
}
public static void main(String[] args) {
// absolute path which we have to simplify.
String str = "/a/./b/../../c/";
String res = simplify(str);
System.out.print(res);
}
}
// This code is contributed by decode2207.
Python3
# Python3 implementation of optimized Approach 1 # function to simplify a Unix - styled # absolute path def simplify(path): # using vector in place of stack v = [] n = len(path) ans = "" for i in range(n): Dir = "" # forming the current directory. while (i < n and path[i] != '/'): Dir += path[i] i+=1 # if ".." , we pop. if (Dir == "..") : if (len(v) > 0): v.pop() elif (Dir == "." or Dir == ""): # do nothing (added for better understanding.) continue else: # push the current directory into the vector. v.append(Dir) # forming the ans for i in v: ans += "/" + i # vector is empty if (ans == ""): return "/" return ans # absolute path which we have to simplify. Str = "/a/./b/../../c/" res = simplify(Str) print(res) # This code is contributed by rameshtravel07
C#
// C# implementation of optimized Approach 1
using System;
using System.Collections.Generic;
class GFG {
// function to simplify a Unix - styled
// absolute path
static string simplify(string path)
{
// using vector in place of stack
List<string> v = new List<string>();
int n = path.Length;
string ans = "";
for (int i = 0; i < n; i++) {
string dir = "";
// forming the current directory.
while (i < n && path[i] != '/') {
dir += path[i];
i++;
}
// if ".." , we pop.
if (dir == "..") {
if (v.Count != 0)
v.RemoveAt(v.Count - 1);
}
else if (dir == "." || dir == "") {
// do nothing (added for better understanding.)
}
else {
// push the current directory into the vector.
v.Add(dir);
}
}
// forming the ans
foreach(string i in v) {
ans += "/" + i;
}
// vector is empty
if (ans == "")
return "/";
return ans;
}
static void Main()
{
// absolute path which we have to simplify.
string str = "/a/./b/../../c/";
string res = simplify(str);
Console.Write(res);
}
}
// This code is contributed by divyeshrabadiya07.
Javascript
<script>
// Javascript implementation of optimized Approach 1
// function to simplify a Unix - styled
// absolute path
function simplify(path)
{
// using vector in place of stack
let v = [];
let n = path.length;
let ans = "";
for (let i = 0; i < n; i++) {
let dir = "";
// forming the current directory.
while (i < n && path[i] != '/') {
dir += path[i];
i++;
}
// if ".." , we pop.
if (dir == "..") {
if (v.length > 0)
v.pop();
}
else if (dir == "." || dir == "") {
// do nothing (added for better understanding.)
}
else {
// push the current directory into the vector.
v.push(dir);
}
}
// forming the ans
for(let i of v) {
ans += "/" + i;
}
// vector is empty
if (ans == "")
return "/";
return ans;
}
// absolute path which we have to simplify.
let Str = "/a/./b/../../c/";
let res = simplify(Str);
document.write(res);
// This code is contributed by mukesh07.
</script>
Producción
/c
Complejidad de tiempo: O (longitud de la string).
Este artículo es una contribución de arshpreet soodan . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA