Efficient String to Nested List Code

While completing an assignment for an introduction to computer science course I found it necessary, in order to solve a larger problem, to convert a string such as '((1|0)*1)' into a nested list that would look like this [['1', '|', '0'], '*', '1'].

My initial attempt at this solution involved iterating through the string until I got to a open parenthesis then making the contents of that open parenthesis part of a list when I came to a closed parenthesis. However, if I came to another open parenthesis I would recursively go back into the function and restart my parenthesis count.

This solution while being functional was very inefficient as it involved indexing through the string three times 3n.

So a better solution had to be made, one in which the efficiency could be done in n. This solution used stacks.

To do this we started out with a stack with an empty list in it.

stack = [[]]

We then went through the characters in the string and when we got to an open parenthesis we appended a new empty list to the top of the stack.

for char in regex:
            # append new list in stack for each open parenthesis
            if char == '(':
                stack.append([])

However if the program found a closed parenthesis we would remove the top of the stack and add it to the list directly below it (or the new top of the stack).

elif char == ')':
                temp = stack.pop()
                stack[-1].append(temp)

Else we would simply add the current character to the list at the top of the stack.

# append character in regular expression to top stack
else:
                stack[-1].append(char)

Then once every character in the string has been iterated through we simply return the remaining list in the stack.

return stack[0]

This solution to making  nested list using a string with parenthesis runs in n and is the most efficient system we could think of.

Object Oriented Programming and Recursion

OOP:

In class we learned about object oriented programming which essentially is a way of representing concepts as objects and then giving these created objects attributes. In my opinion this is useful in two ways one it allows us to represent objects in a very human way i.e. this is a car here are its attributes. And second it is useful to organize our concepts and reduce recursive code.

Recursion:

Recursion is essentially recalling the same method within the method. So instead of iterating over a loop you would call a function that then calls itself until certain parameters are met. I like this method of programming because it is a very human way of thinking about problems, however I understand that a lot of computer programmers are wary of efficiency problems. Our teacher has yet to give a satisfactory answer on how these problems can be overcome though he insures they can be.

Hello World!

I figured I should start my SLOG in the conventional way by welcoming you with one of the simplest programs ever. A program that almost every programmer has made at some point or another and that is the Hello World! program.

Since in the class I am writing this for we use python I'll write the code in that language below:

print('Hello World!')

Now here comes the interesting part that took me about 30 minutes to do, the reasoning is because in this class I am using python3 when I am used to python 2.7 where the code is:

print 'Hello World!'

Anyways welcome to my slog