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.
No comments:
Post a Comment