Directory Hopper

Medium · stack

A learner is practising on a text terminal. The folders form a tree: the root folder is written /, and every other folder is a path such as /home/me. The terminal starts in the home folder /home/me.

You are given a list of commands, run in order. Each command is one of:

"cd path": change to the folder that path points to.
"pushd path": first remember the current folder on a folder stack, then change folder exactly like cd.
"popd": remove the top folder from the folder stack and change to it. If the folder stack is empty, do nothing.

A path is made of names separated by /:

If it starts with /, it is measured from the root. If it starts with the name ~, it is measured from the home folder /home/me. Otherwise it is measured from the current folder.
The name . means "stay here", and the name .. means "go to the parent folder" (the root has no parent, so .. at the root stays there). Any other name goes into the folder with that name, which always exists.
Extra slashes, such as a//b or a slash at the end, change nothing.

Return the folder the terminal ends up in, written as a path that starts with /, has no . or .., no repeated slashes and no slash at the end (except for the root itself, which is /).

Examples

Example 1

Input: commands = ["cd ..", "cd docs/../notes"]

Output: "/home/notes"

Going up from /home/me gives /home. The path docs/../notes enters docs, leaves it again and enters notes.

Example 2

Input: commands = ["pushd /var/log", "cd ../tmp", "popd", "cd work"]

Output: "/home/me/work"

pushd remembers /home/me. After popd the terminal is back there, and cd work goes into work.

Example 3

Input: commands = ["cd /", "cd ../..", "pushd ~/a//b/.", "popd", "popd"]

Output: "/"

Going up from the root stays at the root. The pushd remembers / and popd returns to it. The last popd finds the folder stack empty and does nothing.

Constraints

1 <= len(commands) <= 10^4
Every command is cd or pushd followed by one space and a non-empty path of at most 100 characters, or exactly popd.
A name is 1 to 10 lower-case letters and digits. The name ~ appears only as the first name of a path.