Identifying the linear evaluation pattern

The linear evaluation technique we learned earlier can only solve certain types of sequence evaluation problems. These are generally easy or medium problems where we are given a sequence of data items and triggers and certain rules dictating how to evaluate results when we hit a trigger. The sequence must not have any form of nesting, and each trigger should always only use data either exclusively from before it or exclusively from after it in the sequence (never both), which is what allows the sequence to be processed in a single linear pass.

If the problem statement or its solution follows the generic template below, it can be solved by using the linear evaluation technique using a stack.

Template:

Given a sequence of data items and triggers without any nesting and a set of evaluation rules on hitting a trigger, evaluate the sequence.

Example

Let's consider the following problem as an example to better understand how to identify and solve a problem using the linear evaluation technique.

Problem statement: Given a string `path` that contains the absolute path (starting with a /) to a directory in UNIX style. Write a function to simplify the path to make it a canonical path.

The following rules govern the simplification:

. (dot) refers to the current directory

.. (double-dot) refers to the directory up a level

// (multiple slashes) is treated as a single slash

All other items are treated as directories