DSA Simplifying a Unix Path

The problem

Simplifying a Unix path rewrites a file path into its shortest clean form. The clean form names the same folder. It drops every redundant step along the way.

The input is an absolute path string. It starts with a slash. The output is the simplified path, also starting with a slash.

Three part kinds carry no folder of their own. An empty part comes from doubled or trailing slashes. A single dot means the current folder. A double dot means the parent folder.

cases = [
    ("/home/", "/home"),
    ("/home//foo/", "/home/foo"),
    ("/home/user/Documents/../Pictures", "/home/user/Pictures"),
    ("/../", "/"),
    ("/.../a/../b/c/../d/./", "/.../b/d"),
]
for path, expected in cases:
    print(path, "->", expected)

Read one row at a time. The third row climbs out of Documents into its parent, then enters Pictures. The last row keeps the three-dot name, because three dots are an ordinary folder name.

Intuition: splitting alone is not the answer

The first idea is to split the path on slashes and join the parts back. Splitting is the right start. It is not the whole job.

Two part kinds defeat a plain split and join. The empty parts from doubled slashes would survive as gaps. Worse, the double dot is an instruction, not a name: it cancels the folder before it, and a join keeps both.

for path in ("/home//foo/", "/a/b/../c"):
    print(path, "splits to:", path.split("/"))

The first split shows two empty strings. The second keeps the .. part beside the b it should erase. The parts need decisions, one by one, in order.

Brute force: rewrite the string until it settles

A straightforward method rewrites the path text itself. Each pass removes one doubled slash, one dot segment, or one name-plus-double-dot pair. The passes repeat until a full pass changes nothing.

The method reaches the same answers on simple paths. Its cost is the repetition: each rewrite rescans and rebuilds the whole string, and one fix can expose the next.

import re

def simplify_slow(path):
    passes = 0
    previous = None
    while previous != path:
        previous = path
        passes += 1
        path = path.replace("//", "/")
        path = path.replace("/./", "/")
        path = re.sub(r"/[^/]+/\.\./", "/", path)
        if path.endswith("/."):
            path = path[:-2] + "/"
        if path.endswith("/.."):
            path = re.sub(r"/[^/]+/\.\.$", "/", path)
    if len(path) > 1 and path.endswith("/"):
        path = path[:-1]
    return path, passes

for path in ("/home//foo/", "/home/user/Documents/../Pictures", "/.../a/../b/c/../d/./"):
    result, passes = simplify_slow(path)
    print(path, "->", result, "passes:", passes)

The results match three of the cases. The pass counts show the shape of the cost: the work depends on how many rewrites the string needs, and each rewrite is a full scan.

The optimal solution: a stack of kept names

Keep a stack of real folder names: push each ordinary name, pop on a double dot, and skip empty parts and single dots. That one pass leaves exactly the names of the clean path, in order.

def simplify(path):
    stack = []
    for part in path.split("/"):
        if part == "" or part == ".":
            continue
        if part == "..":
            if stack:
                stack.pop()
        else:
            stack.append(part)
    return "/" + "/".join(stack)

paths = ["/home/", "/home//foo/", "/home/user/Documents/../Pictures", "/../", "/.../a/../b/c/../d/./"]
for path in paths:
    print(path, "->", simplify(path))

All five cases pass. A double dot at the root pops nothing, because the stack is empty and the root has no parent. Joining the stack behind one leading slash builds the answer.

Walkthrough: /a/b/../c/./d

Watch the kept names on one mixed path. The stack prints after each part of the split, including the parts that get skipped.

def simplify_traced(path):
    stack = []
    for part in path.split("/"):
        if part == "" or part == ".":
            action = "skipped"
        elif part == "..":
            if stack:
                stack.pop()
            action = "pops"
        else:
            stack.append(part)
            action = "pushed"
        print("part", repr(part), action, "-> stack", stack)
    return "/" + "/".join(stack)

print("result:", simplify_traced("/a/b/../c/./d"))

The b name is pushed and then popped by the double dot. The single dot changes nothing. The answer reads off the stack at the end: /a/c/d.

Complexity

Time is O(n) for a path of length n: the split makes each part once, and each part is pushed or popped at most once.

Space is O(n) in the worst case: a path of plain names keeps every name on the stack.

def count_visits(path):
    stack = []
    visits = 0
    for part in path.split("/"):
        visits += 1
        if part == "" or part == ".":
            continue
        if part == "..":
            if stack:
                stack.pop()
        else:
            stack.append(part)
    return visits

for path in ("/a/b/c", "/a/b/c/d/e/f", "/a//b/./c/../d/e"):
    print(path, "parts visited:", count_visits(path))

The visit count equals the part count every time. Nothing is rescanned after a pop. That single pass is the whole advantage over the rewriting method.

Edge cases and pitfalls

The root alone simplifies to itself. The split gives only empty parts, the stack stays empty, and the join behind the leading slash is just the slash.

Extra double dots at the root are harmless. Each one finds an empty stack and pops nothing. Climbing above the root is impossible in an absolute path.

def simplify(path):
    stack = []
    for part in path.split("/"):
        if part == "" or part == ".":
            continue
        if part == "..":
            if stack:
                stack.pop()
        else:
            stack.append(part)
    return "/" + "/".join(stack)

print("root:", simplify("/"))
print("above root:", simplify("/a/../../"))
print("three dots kept:", simplify("/.../x"))
print("many slashes:", simplify("/a//b////c/d//././/.."))
print("trailing dot:", simplify("/a/b/."))

One pitfall is treating any dot run as special. Only the exact parts . and .. carry meaning. A name like ... or .hidden is an ordinary folder name and must be kept.