Balancing Parenthesis Algorithm Using Stacks

Admin 1
Viewed 167

So I am learning on Data Structures and Algorithms currently working on Stacks, Queues and Dequeus

I have this question that says I should implement a Stack to check if the string given has balanced parenthesis and I am told in the question that the string contains only parenthesis and the string has no spaces

So I did implement my Stack class and then tried solving the problem Checking if the Parenthesis balance and I did a simple test case '[]' and it return False instead of True So I fail to spot the error in the code.

Below is my thought process to solving the question so you can clearly see where I could have went wrong:

  1. Firstly I checked if the length of the string is even if not I return False

  2. I scan through the string and every time I see an opening parenthesis I push it to the stack

  3. Then when I see a closing parenthesis I use the knowledge of stacks that LIFO I know that if now I am seeing a closing parenthesis the previous one should be the corresponding opening which was the last item pushed to stack so I then pop it off the stack and save it into a variable

  4. I then make a check if they correspond and if they do not I return False

  5. I then check if the stack is Empty then I know the is no corresponding opening parenthesis I return False

  6. Finally if the loop finished without any return I check if stack is empty I return True else I False

Code Below

class Stack(object):

    def __init__(self):
        self.items = []

    def isEmpty(self):

        return self.items == 0

    def get_size(self):

        return len(self.items)


    def push(self, data):

        self.items.append(data)

    def peek(self):

        return self.items[len(self)-1]

    def remove_item(self):

        self.items.pop()


stack = Stack()


def balance_check(s):

    if len(s) % 3 == 0:
        return False


    openings = set('({[')
    matches = set([ ('{', '}') , ('(', ')') , ('[', ']') ])

    for paren in s:

        if paren in openings:
            stack.push(paren)


        else:

            if stack.get_size() == 0:
                return False

            last_open = stack.remove_item()

            if (last_open, paren) not in matches:

                return False

    if stack.get_size() == 0:
        return True


print(balance_check('[]'))
data-structures algorithm python
2 Answers

Great attempt. You were very close. Just a couple of issues or typos.

  1. remove_item() removed the item from the list, but not returned.
  2. odd/even check is done by % 2 == 1, not % 3.
class Stack(object):
    def __init__(self):
        self.items = []
    def isEmpty(self):
        return self.items == 0
    def get_size(self):
        return len(self.items)
    def push(self, data):
        self.items.append(data)
    def peek(self):
        return self.items[len(self.items)-1]
    def remove_item(self):
        # you were not returning here
        return self.items.pop()

stack = Stack()

def balance_check(s):
    # odd/even check is done like this, not by % 3
    if len(s) % 2 == 1:
        return False

    openings = set('({[')
    matches = set([('{', '}'), ('(', ')'), ('[', ']')])

    for paren in s:
        if paren in openings:
            stack.push(paren)
        else:
            if stack.get_size() == 0:
                return False
            last_open = stack.remove_item()
            if (last_open, paren) not in matches:
                return False

    # simplified return
    return stack.get_size() == 0


print(balance_check('{[]{()}}'))

You can add more quick checks like:

  1. If string starts with closing parenthesis, return False
  2. If String ends with opening parenthesis, return False
user_84301550

Your algorithm is wrong, since this is not a valid string: "]]]][[[["

instead, every time you see an open parenthesis, you push onto the stack, a closed parenthesis gets popped, if the length is 0 before the string is exhausted, the answer is "false", if the length is NOT zero when the string is exhausted, the answer is "false". Otherwise, "true".

user_29772560
Related