{"id":2336,"date":"2018-08-12T02:35:04","date_gmt":"2018-08-12T07:35:04","guid":{"rendered":"http:\/\/bluegalaxy.info\/codewalk\/?p=2336"},"modified":"2020-01-08T10:01:53","modified_gmt":"2020-01-08T15:01:53","slug":"python-how-to-implement-a-lifo-stack","status":"publish","type":"post","link":"https:\/\/bluegalaxy.info\/codewalk\/2018\/08\/12\/python-how-to-implement-a-lifo-stack\/","title":{"rendered":"Python: How to implement a LIFO stack"},"content":{"rendered":"

Stacks are a computer science data structure useful for special types of computation where you essentially add information to the top of the ‘stack’ and also remove information only from the top of the stack. LIFO stands for Last-In-First-Out, which is an acronym that aids in remembering what is going on in a stack, i.e. the last item added to the to the stack is the first item that will be removed from the stack.<\/p>\n

In Python, a stack can be implemented as an array where we use built-in Python methods such as list.append()<\/code> which can ‘push’ information onto the stack and list.pop()<\/code> which can ‘pop’ information off of the stack.<\/p>\n

Both of these methods act on the end<\/em> of an array, so all we have to do to visualize a Python list as a stack is turn the array 90 degrees counter clockwise so that the\u00a0 front of the array is at the bottom and the end of the array is considered the ‘top’ of the stack. Or, you can just imagine the horizontal end of a Python list as the top of the stack.<\/p>\n

Here is what Wikipedia says about stacks:<\/p>\n

In computer science, a stack is an abstract data type that serves as a collection of elements, with two principal operations:<\/p>\n

push, which adds an element to the collection, and
\npop, which removes the most recently added element that was not yet removed.<\/p><\/blockquote>\n

Here is one way to visualize what is going on in a stack:<\/p>\n

\"\"<\/p>\n

Next I will illustrate how a stack can be useful in solving real problems. Let’s say I am creating a parser that reads every line of a source code file looking for opening and closing parenthesis in order to capture all function calls. The parser is working except it is finding function calls that should not be included because they are inside of larger strings such as HTML constructions or SQL queries. For example, here is an HTML construction that contains function calls that should be ignored due to the fact that the calls are inside of a string.<\/p>\n

html += '<p><a href=\"#\" onclick=\"javascript:$(\\'#help_note\\').hide();\">Close<\/a><\/p>';<\/pre>\n
Technically there are function calls inside this string, but I don’t want to capture them because I am trying to gather only function calls that are actually being used in the surrounding code. Notice this string is surrounded by single quotes, then it has some double quotes inside, followed by more double quotes with single quotes inside them.<\/p>\n
\"\"<\/p>\n
The problem is, how do you parse this line so that you can tell where the string begins and ends? You can’t just go to the next occurrence of single quote that you find, because it is inside of another double quote inside the string. Counting single and double quotes like you would count opening and closing brackets won’t work either, because you don’t know ahead of time how long the string is so you don’t know if any given quotes you find are the last.<\/p>\n
This is where the concept of a stack becomes really useful. When reading a line of text like the above example, character by character from left to right, whenever we encounter a single or double quote, we can add it to the stack. Because we have both single and double quotes, we need to represent them differently in the stack. For example, we could call the single quotes ‘s’ and the double quotes ‘d’.<\/p>\n
The algorithm works like this:<\/strong><\/h5>\n
If we see a single quote, push an ‘s’ onto the stack. If we see a double quote, push a ‘d’ onto the stack. However, before adding an ‘s’ or ‘d’ to the stack, check the top of the stack to see if it matches what we just found. For example, if I just found double quotes, check the top of the stack. If the top of the stack already contains a ‘d’, then pop the ‘d’ off of the stack. Otherwise, push a ‘d’ onto the stack.<\/p>\n
This works the same way for ‘s’. When\u00a0 encountering a new single quote in the string, if the top of the stack already contains an ‘s’, then pop it off of the stack. Otherwise, push an ‘s’ onto the stack.<\/p>\n
Now all we have to do to find the end of the string is to check the stack to see if it is empty. If the stack is empty, we have found the end of the string and we are done.<\/p>\n
Here is how this plays out with the example string above:<\/p>\n