CODEWITHSUNDEEP
python
user6304394
user6304394

Reputation:

Balanced Parenthesis checker problem without stack

I am trying to solve the parenthesis checker problem without stack after learning Python. My code does work on a lot of expressions but fails on plenty of them too. Especially when the same type of brackets appear concurrently.

exp = "([[]])"
#input("Enter the expression to evaluate: ")

def sumer(l):
    x=0
    for i in range(len(l)):
      x+=l[i]
    return x  

exp_num = list([])

for i in range(len(exp)):
   if exp[i]=="(":
        exp_num.append(1)
   if exp[i]==")":
        exp_num.append(-1)
   if exp[i]=="[":
        exp_num.append(2)
   if exp[i]=="]":
        exp_num.append(-2)
   if exp[i]=="{":
        exp_num.append(3)
   if exp[i]=="}":
        exp_num.append(-3)
del exp
for g, i in enumerate(exp_num):
    if i>0:
        try:
            op = exp_num.index(-i)
            sm = sumer(exp_num[g+1:op])
            if sm == 0:
                for x in range(g,op+1):
                    exp_num[x]= 0
        except ValueError:
            break
    else:
        continue      
if exp_num.count(0) == len(exp_num):
    print("The entered expression is valid !!")
else:
    print("The entered expression is not valid !!")

It works for above string but it will fail for ([[()]])

So far what I am doing it is:

Step 1: Give different type of braces a number, positive for opening and negative to closing. For example, '(' = 1 and ')' = -1. Finally, convert the input expression to a list of numbers in the same order.

Step 2: Start scanning the list and if a positive number(opening bracket) is found then find its corresponding negative(closing bracket). Find the sum of the numbers between these two.

Step 3: If the sum is 0 then simply replace all the processed items in the list with 0 and keep repeating.

In the end, if the list becomes with all items as zeroes then the expression is valid else the expression is not valid.

Upvotes: 2

Views: 1173

Answers (3)

Dipankar Nalui
Dipankar Nalui

Reputation: 1261

The following implemention is done without using stack. This Python code is very easy to understand. Hence i'm not giving much explanation. From the output iteration, we can understand it easily.

exp = "{{{{{{[[[(((((()))))][)][][][][]]]}}}}}}"
length = len(exp)
print("Length of the string = ", length)
half = int(length / 2)
print("Max iteration is needed to check if it's a balanced string = ",half)
count = 1
print("Iteration ", count)
print(exp)
while(count != half ):
    count = count + 1
    print("Iteration ", count)
    if ('()' in exp ) or ( '{}' in exp) or ( '[]' in exp):
        exp = exp.replace('[]', '')
        exp = exp.replace('{}', '')
        exp = exp.replace('()', '')
        print(exp)
    else:
        print("Not a Balance string")
        break
    if len(exp) == 0 :
        print("Balance string")
        break

Output with Unbalanced string: {{{{{{[[[(((((()))))][)][][][][]]]}}}}}}

Length of the string =  40
Max iteration is needed to check if it's a balanced string =  20
Iteration  1
{{{{{{[[[(((((()))))][)][][][][]]]}}}}}}
Iteration  2
{{{{{{[[[((((())))][)]]]}}}}}}
Iteration  3
{{{{{{[[[(((()))][)]]]}}}}}}
Iteration  4
{{{{{{[[[((())][)]]]}}}}}}
Iteration  5
{{{{{{[[[(()][)]]]}}}}}}
Iteration  6
{{{{{{[[[(][)]]]}}}}}}
Iteration  7
Not a Balance string

Output with balanced string: {{{{{{[[[(((((())))))][][][][]]]}}}}}}

Length of the string =  38
Max iteration is needed to check if it's a balanced string =  19
Iteration  1
{{{{{{[[[(((((())))))][][][][]]]}}}}}}
Iteration  2
{{{{{{[[[((((()))))]]]}}}}}}
Iteration  3
{{{{{{[[[(((())))]]]}}}}}}
Iteration  4
{{{{{{[[[((()))]]]}}}}}}
Iteration  5
{{{{{{[[[(())]]]}}}}}}
Iteration  6
{{{{{{[[[()]]]}}}}}}
Iteration  7
{{{{{{[[[]]]}}}}}}
Iteration  8
{{{{{{[[]]}}}}}}
Iteration  9
{{{{{{[]}}}}}}
Iteration  10
{{{{{}}}}}
Iteration  11
{{{{}}}}
Iteration  12
{{{}}}
Iteration  13
{{}}
Iteration  14
{}
Iteration  15

Balance string

Output with a perfect balaced string [([[[{{([{{[[[[]]]]}}])}}]]])]:

Length of the string =  30
Max iteration is needed to check if it's a balanced string =  15
Iteration  1
[([[[{{([{{[[[[]]]]}}])}}]]])]
Iteration  2
[([[[{{([{{[[[]]]}}])}}]]])]
Iteration  3
[([[[{{([{{[[]]}}])}}]]])]
Iteration  4
[([[[{{([{{[]}}])}}]]])]
Iteration  5
[([[[{{([{}])}}]]])]
Iteration  6
[([[[{{([])}}]]])]
Iteration  7
[([[[{{}}]]])]
Iteration  8
[([[[{}]]])]
Iteration  9
[([[[]]])]
Iteration  10
[([[]])]
Iteration  11
[([])]
Iteration  12
[]
Iteration  13

Balance string

Upvotes: 0

Amit Verma
Amit Verma

Reputation: 11

in ur soln, in statement delimeter[-1] == closing.index(char)

u should correct it like

opening.index(delimeter[-1]) == closing.index(char)

Upvotes: -1

Jaideep Shekhar
Jaideep Shekhar

Reputation: 886

I am trying to solve the parenthesis checker problem without stack after learning Python.

What if...

I could simply treat a list as a stack.

Let us initialise expr and delimiters:

expr = '[{[{<>}]}]'
delimiters = list()

And use delimiters as a stack:

# For each character in expression
for character in expr:
    # If it is an opening one
    if character in opening:
        # Add it's unique value to delimiters
        delimiters.append( opening.index(character) )
    # If it is a closing one
    if character in closing:
        # If there are opening delimiters and character matches the last opened one
        if delimiters and delimiters[-1] == closing.index(character):
            # It was valid, remove the opening delimiter
            del delimiters[-1]
        # Else, expression is invalid!
        else:
            break

where opening and closing are the matched pairs:

opening = '[({<'
closing = '])}>'

Last, if the list (previously called stack) is empty, the expression was valid:

print('Success!') if not delimiters else print('Invalid Expression!')
# same as:
# print('Success!') if delimiters == [] else print('Invalid Expression!')

Upvotes: 2

Related Questions