Reputation:
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
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
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
Reputation: 886
I am trying to solve the parenthesis checker problem without stack after learning Python.
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