Dada una string de expresión, escriba un programa de python para encontrar si una string dada tiene paréntesis balanceados o no.
Ejemplos:
Input : {[]{()}}
Output : Balanced
Input : [{}{}(]
Output : Unbalanced
Enfoque n. ° 1: uso de la pila
Un enfoque para verificar los paréntesis balanceados es usar stack. Cada vez que encuentre un paréntesis abierto, empújelo en la pila, y cuando encuentre un paréntesis cerrado, empápelo con la parte superior de la pila y extráigalo. Si la pila está vacía al final, devuelve Equilibrado, de lo contrario, Desequilibrado.
# Python3 code to Check for
# balanced parentheses in an expression
open_list = ["[","{","("]
close_list = ["]","}",")"]
# Function to check parentheses
def check(myStr):
stack = []
for i in myStr:
if i in open_list:
stack.append(i)
elif i in close_list:
pos = close_list.index(i)
if ((len(stack) > 0) and
(open_list[pos] == stack[len(stack)-1])):
stack.pop()
else:
return "Unbalanced"
if len(stack) == 0:
return "Balanced"
else:
return "Unbalanced"
# Driver code
string = "{[]{()}}"
print(string,"-", check(string))
string = "[{}{})(]"
print(string,"-", check(string))
string = "((()"
print(string,"-",check(string))
{[]{()}} - Balanced
[{}{})(] - Unbalanced
((() - Unbalanced
Enfoque #2: Usar la cola
Primero Correlacione los paréntesis de apertura con los respectivos paréntesis de cierre. Itere a través de la expresión dada usando ‘i’, si ‘i’ es un paréntesis abierto, agregue en la cola, si ‘i’ es un paréntesis cerrado, verifique si la cola está vacía o ‘i’ es el elemento superior de la cola, si es así, devolver «Desequilibrado», de lo contrario «Equilibrado».
# Python3 code to Check for
# balanced parentheses in an expression
def check(expression):
open_tup = tuple('({[')
close_tup = tuple(')}]')
map = dict(zip(open_tup, close_tup))
queue = []
for i in expression:
if i in open_tup:
queue.append(map[i])
elif i in close_tup:
if not queue or i != queue.pop():
return "Unbalanced"
if not queue:
return "Balanced"
else:
return "Unbalanced"
# Driver code
string = "{[]{()}}"
print(string, "-", check(string))
string = "((()"
print(string,"-",check(string))
{[]{()}} - Balanced
((() - Unbalanced
Enfoque n. ° 3: basado en la eliminación
En cada iteración, los corchetes más internos se eliminan (reemplazados con una string vacía). Si terminamos con una string vacía, la inicial estaba balanceada; de otra forma no.
# Python3 code to Check for
# balanced parentheses in an expression
def check(my_string):
brackets = ['()', '{}', '[]']
while any(x in my_string for x in brackets):
for br in brackets:
my_string = my_string.replace(br, '')
return not my_string
# Driver code
string = "{[]{()}}"
print(string, "-", "Balanced"
if check(string) else "Unbalanced")
{[]{()}} - Balanced
Publicación traducida automáticamente
Artículo escrito por Smitha Dinesh Semwal y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA