Understanding the linear evaluation pattern

There are some problems where we are given a sequence of data, and we need to evaluate it based on some rules. When dealing with such sequences, the evaluation may require storing contextual information and deferring evaluation until certain special items in the sequence, which we call triggers, are hit. In most cases, to evaluate the sequence, we must move through the sequence, keeping track of several data items and performing some operation on some of these data items on hitting a trigger. The triggers may themselves be of different types, each with its own set of rules for evaluation. Each evaluation may either add, remove, or update data items from the sequence (for example, a trigger could pop the last two numbers and push their sum), and subsequent triggers operate on the previously evaluated results.

An example of a sequence with data and triggers is given below.

The linear evaluation technique uses the LIFO property of a stack to solve such problems by storing data items in the stack, maintaining the most to least recent order, and incrementally evaluating the results using this data when certain triggers are hit.