Parenthesis Checking Using Stack Python

Question

I am learning data structures in Python and working on stacks. I am trying to create a code that uses stacks to match the parenthesis in an expression, however I am not getting the right answer. This needs to be done without the use of Python libraries.

class Stack():
    def __init__(self):  # Initialize a new stack
        self._items = []
        self._size = 0
        self._top = -1

    def push(self, new_item):  #  Append the new item to the stack 
        self._items.append(new_item)
        self._top += 1
        self._size += 1
        self._items[self._top] = new_item

    def pop(self):  # Remove and return the last item from the stack
        old_item = self._items[self._top]
        self._top -= 1
        self._size -= 1
        return old_item

    def size(self):  # Return the total number of elements in the stack
       return len(self._items)

    def isEmpty(self):  #  Return True if the stack is empty and False if it is not empty 
        if self._items == 0:
            return True
        else:
            return False

    def peek(self):   # Return the element at the top of the stack or return None if the stack is

empty if self.isEmpty(): return None else: return self._items[self._top]

def check_Par(exp):
    opening = ['(', '[', '{']
    closing = [')', ']', '}']
    balanced = True
    s = Stack()

    for x in exp:
        if x in opening:
            s.push(x)
        elif x in closing:
            position = s.pop()
            if closing.index(x) and opening.index(position):
                balanced = True
            else:
                balanced = False
            pass      

    if s.isEmpty():
        balanced = False
    return balanced    

exp1 = "(2)+(-5)" # True
exp2 = "((2))*((3))" # True
exp3 = "(4))]" #False

print(check_Par(exp1))
print(check_Par(exp2))
print(check_Par(exp3))

I get an error for line 14 IndexError: list index out of range

Also, I know the for loop is not completed and I am having a hard time fix it. Any advice it would be greatly appreciated. Lois

This doesn't answer your problem, but can use a list directly instead of making your own stack class. You can use list.append and list.pop. — ssp
– ssp, Commented Dec 9, 2020 at 4:06
@Moosefeather - I know that list.append will get me the right answer, however, i need to use the stack class.... — Lois
– Lois, Commented Dec 9, 2020 at 4:14
@Lois You are getting IndexError because s.pop() gets called when s._top < 0 and s._size == 0 at some point. — ssp
– ssp, Commented Dec 9, 2020 at 4:23

ssp · Accepted Answer · 2020-12-09 05:19:46Z

1

Here's a solution using a list as a stack, you can translate it to your stack class:

closing_to_opening = {')': '(', ']': '[', '}': '{'}
opening = list(closing_to_opening.values())

def check_par(exp):
    stack = []
    for c in exp:
        if c in opening:
            stack.append(c)
        elif c in closing_to_opening:
            if not stack or stack.pop() != closing_to_opening[c]:
                # The above checks '(' <-> ')', '[' <-> ']' etc
                return False
    # return True if stack is empty:
    return not stack

answered Dec 9, 2020 at 5:19

ssp

1,72013 silver badges17 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Parenthesis Checking Using Stack Python

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related