Solución de Paréntesis Válido

Clase 26 de 41 • Curso de Algoritmos Avanzados: Estructuras de Datos Lineales

Contenido del curso

Introducción

1
¿Ya tomaste el Curso Avanzado de Algoritmos: Patrones de Arrays y Strings?
00:52 min

Lista Enlazada

Pilas y colas

Colas de prioridad

Próximos pasos

41
Toma el Curso Avanzado de Algoritmos: Grafos y Árboles
00:33 min

Tomar examen

Comentarios

Gabriel Revelo

student•

def isValid(s):
    pila=0
    for i in s:
        if i=='(':
          pila+=1
        elif i==')':
           pila-=1
        if pila<0:
           return False  
    return pila==0

isValid('(()))')

Nicolas Guillen

student•

Esa me gustó, yo usé un array para guardar la pila pero esta solución se ve clean 👌🏼

Nicolas Alpargatero

student•

Implementado con stacks como Linked List, pero el complex en el espacio sigue O(n)

Y sin usar Linked List, el espacio O(1), pero si aumenta la complejidad del ejercicio si creeria que es mejor con stacks como Linked List:

Santiago Amaya

student•

def check_parentesis(case:str)->bool:
    #Create the stack 
    new_stack = Stack()
    for i in case:
        new_stack.append(i)
    # iterate over the stack and chase '(' or ')'on it
    prev = new_stack.top
    current = prev.next
    check = Stack()
    flag = 0
    flag2 = 0
    while prev and prev.next:
        if prev and prev.data == ')':
            check.append(prev)
            flag += 1
        if current and current.data == '(':
            check.append(current)
            flag2 += 1 
        prev = prev.next
        current = current.next
    if flag and flag2 > 0 and flag == flag2:
        return True
    else:
        return False 
```def check\_parentesis(case:str)->bool:    #Create the stack     new\_stack = Stack()    for i in case:        new\_stack.append(i)    # iterate over the stack and chase '(' or ')'on it    prev = new\_stack.top    current = prev.next    check = Stack()    flag = 0    flag2 = 0    while prev and prev.next:        if prev and prev.data == ')':            check.append(prev)            flag += 1        if current and current.data == '(':            check.append(current)            flag2 += 1         prev = prev.next        current = current.next    if flag and flag2 > 0 and flag == flag2:        return True    else:        return False&#x20;

Francisco Roberto Gomez

student•

Mi solución sin utilizar pilas en C++


int parentesis=0;
std::string texto;
std::cin>>texto;
&#x20; for (int i = 0; i < texto.length(); ++i) {
&#x20;     if (texto\[i]=='('){
&#x20;         parentesis++;
&#x20;     }else if (texto\[i]==')'){
&#x20;         parentesis--;
&#x20;     }else
&#x20;         continue;
&#x20; }

&#x20; if (parentesis==0){
&#x20;     std::cout<<"Hay correcto orden de parentesis"<\<std::endl;
&#x20; }else{
&#x20;     std::cout<<"No hay correcto Orden"<\<std::endl;
&#x20; }

Angélica María Celis Torres

student•

Que pasa si tienes una entrada " ) ( ", funcionaria? Creo que por eso se necesita la pila, para poder verificar si estan en el orden correcto.

REYNALDO FABIAN NORIEGA ZAMBRANO

student•

Otro aporte en C++, sin usar espacio extra:

#include<iostream>
#include<string>


bool valid_parentheses(std::string input){
	
	int check_open = 0;
	for(char c: input){
		if(c == '('){
			check_open++;
		}
		else if (!check_open && c == ')' ){
			return false;
		}
		else if (check_open && c == ')' ){
			check_open--;
		}
	}


	if (check_open != 0) return false;
	return true;

}


int main(){


	std::string input = ")(";
	if(valid_parentheses(input)) std::cout << "valid" << std::endl;
	else std::cout << "not" << std::endl;
	input = "asd)asd(da";
	if(valid_parentheses(input)) std::cout << "valid" << std::endl;
	else std::cout << "not" << std::endl;
	input = "()()";
	if(valid_parentheses(input)) std::cout << "valid" << std::endl;
	else std::cout << "not" << std::endl;
	input = "(dfa)(asdf";
	if(valid_parentheses(input)) std::cout << "valid" << std::endl;
	else std::cout << "not" << std::endl;
	input = "(dfa)(asdf)";
	if(valid_parentheses(input)) std::cout << "valid" << std::endl;
	else std::cout << "not" << std::endl;
	input = "(dfa)(asdf))";
	if(valid_parentheses(input)) std::cout << "valid" << std::endl;
	else std::cout << "not" << std::endl;

	return 0;
}

REYNALDO FABIAN NORIEGA ZAMBRANO

student•

def valid_parentheses(input: str):
    print(f"checking {input=}")
    stack = []

    for elem in input:
        if elem == '(':
            stack.append(elem)
        elif elem == ')':
            if len(stack) != 0 and stack[-1] == '(':
                stack.pop()
            else:
                return "No valid"
        elif elem.isalpha() or elem.isnum():
            continue


    if len(stack) != 0:
        return "No valid"

    return "Valid"




print(valid_parentheses("()"))
print(valid_parentheses("(()))"))
print(valid_parentheses("("))
print(valid_parentheses(")"))
print(valid_parentheses(")("))
print(valid_parentheses("(caracoles)(decolores)()"))

```def valid\_parentheses(input: str):

&#x20;   print(f"checking {input=}")

&#x20;   stack = \[]



&#x20;   for elem in input:

&#x20;       if elem == '(':

&#x20;           stack.append(elem)

&#x20;       elif elem == ')':

&#x20;           if len(stack) != 0 and stack\[-1] == '(':

&#x20;               stack.pop()

&#x20;           else:

&#x20;               return "No valid"

&#x20;       elif elem.isalpha() or elem.isnum():

&#x20;           continue





&#x20;   if len(stack) != 0:

&#x20;       return "No valid"



&#x20;   return "Valid"









print(valid\_parentheses("()"))

print(valid\_parentheses("(()))"))

print(valid\_parentheses("("))

print(valid\_parentheses(")"))

print(valid\_parentheses(")("))

print(valid\_parentheses("(caracoles)(decolores)()"))

REYNALDO FABIAN NORIEGA ZAMBRANO

student•

Nein, algo salio mal al pegar el bloque de codigo :(

Bryan Castano

student•

#!/usr/bin/env python3
"""Check for valid or balanced parentheses"""

size = 50
stack = ['' for _ in range(size)]
top = -1

def push(ch: str) -> None:
    """Push ch into stack"""
    global top
    if top == size-1:
        return
    else:
        top += 1
        stack[top] = ch

def pop() -> int:
    """Pop off the top data in the stack"""
    global top
    if top == -1:
        return -1
    else:
        data = stack[top]
        top -= 1
        return data
        
        
def isStackEmpty() -> bool:
    """Check if stack is empty"""
    if (top == -1):
        return True
    else:
        return False
        
def isStackFull() -> bool:
    """Check if stack is full"""
    if (top == size-1):
        return True
    else:
        return False
        
def isBalanced(str: str) -> bool:
    """Check if parenthese is valid"""
    for ch in str:
        if (ch == '(' or ch == '[' or ch == '{'):
            push(ch)
        else:
            if isStackEmpty():
                return False
            
            top = pop()
            
            if ((ch == ')' and top != '(') or
                (ch == ']' and top != '[') or
                (ch == '}' and top != '{')):
                
                return False
                
    return isStackEmpty()
        
        
def isValid(str: strg) -> bool:
    """Check if parenthese is valid"""
    parentheses = {'(':')', '[':']', '{':'}'}
    stack = []
    for ch in strg:
        if (ch in parentheses.keys()):
            stack.append(ch)
        else:
            if stack == []:
                 return False
    
            top = stack.pop()
            
            if ch != parentheses[top]:
            
                return False
                
    return stack == []
    


if __name__ == '__main__':

    parentheses = input("Enter parentheses to test\n").strip()
    
    if (isBalanced(parentheses)):
        print("Valid parentheses")
    else:
        print("Oops! Invalid parentheses")
    
    if (isBalanced(parentheses)):
        print("Valid parentheses")
    else:
        print("Oops! Invalid parentheses")
        
        
        
```#!/usr/bin/env python3

"""Check for valid or balanced parentheses"""



size = 50

stack = \['' for \_ in range(size)]

top = -1



def push(ch: str) -> None:

&#x20;   """Push ch into stack"""

&#x20;   global top

&#x20;   if top == size-1:

&#x20;       return

&#x20;   else:

&#x20;       top += 1

&#x20;       stack\[top] = ch



def pop() -> int:

&#x20;   """Pop off the top data in the stack"""

&#x20;   global top

&#x20;   if top == -1:

&#x20;       return -1

&#x20;   else:

&#x20;       data = stack\[top]

&#x20;       top -= 1

&#x20;       return data

&#x20;      &#x20;

&#x20;      &#x20;

def isStackEmpty() -> bool:

&#x20;   """Check if stack is empty"""

&#x20;   if (top == -1):

&#x20;       return True

&#x20;   else:

&#x20;       return False

&#x20;      &#x20;

def isStackFull() -> bool:

&#x20;   """Check if stack is full"""

&#x20;   if (top == size-1):

&#x20;       return True

&#x20;   else:

&#x20;       return False

&#x20;      &#x20;

def isBalanced(str: str) -> bool:

&#x20;   """Check if parenthese is valid"""

&#x20;   for ch in str:

&#x20;       if (ch == '(' or ch == '\[' or ch == '{'):

&#x20;           push(ch)

&#x20;       else:

&#x20;           if isStackEmpty():

&#x20;               return False

&#x20;          &#x20;

&#x20;           top = pop()

&#x20;          &#x20;

&#x20;           if ((ch == ')' and top != '(') or

&#x20;               (ch == ']' and top != '\[') or

&#x20;               (ch == '}' and top != '{')):

&#x20;              &#x20;

&#x20;               return False

&#x20;              &#x20;

&#x20;   return isStackEmpty()

&#x20;      &#x20;

&#x20;      &#x20;

def isValid(str: strg) -> bool:

&#x20;   """Check if parenthese is valid"""

&#x20;   parentheses = {'(':')', '\[':']', '{':'}'}

&#x20;   stack = \[]

&#x20;   for ch in strg:

&#x20;       if (ch in parentheses.keys()):

&#x20;           stack.append(ch)

&#x20;       else:

&#x20;           if stack == \[]:

&#x20;                return False

&#x20;  &#x20;

&#x20;           top = stack.pop()

&#x20;          &#x20;

&#x20;           if ch != parentheses\[top]:

&#x20;          &#x20;

&#x20;               return False

&#x20;              &#x20;

&#x20;   return stack == \[]

&#x20;  &#x20;





if \_\_name\_\_ == '\_\_main\_\_':



&#x20;   parentheses = input("Enter parentheses to test\n").strip()

&#x20;  &#x20;

&#x20;   if (isBalanced(parentheses)):

&#x20;       print("Valid parentheses")

&#x20;   else:

&#x20;       print("Oops! Invalid parentheses")

&#x20;  &#x20;

&#x20;   if (isBalanced(parentheses)):

&#x20;       print("Valid parentheses")

&#x20;   else:

&#x20;       print("Oops! Invalid parentheses")

&#x20;      &#x20;

&#x20;      &#x20;

&#x20;      &#x20;

Miguel Angel Reyes Moreno

student•

class Solution: def isValid(self, s: str) -> bool: stack = [] mapping = { ')': '(', '}': '{', ']': '[' } for char in s: if char in mapping: top_element = stack.pop() if stack else '#' if mapping[char] != top_element: return False else: stack.append(char) return not stack

Luis Rodolfo Reyes

student•

Luis Rodolfo Reyes

student•

versión de Javascript

Luis Rodolfo Reyes

student•

// versión de javascript

function isValid(param) {

const openChars = ['{', '[', '(']

const closeChars = ['}', ']', ')']

const arr = param.split('')

let stackLength = 0

arr.forEach(e => {

if(openChars.includes(e)){

stackLength ++

}

if(closeChars.includes(e)){

stackLength --

}

})

return stackLength === 0

}

console.log(

isValid("{{}}")

)

Tomás Santa Cruz

student•

Mi solucion en c++

#include <iostream>
#include <stack>
#include <string>

using namespace std;

bool esParentesisValido(string cadena)
{
    stack<char> pila;

    for (int i = 0; i < cadena.length(); i++)
    {
        if (cadena[i] == '(')
        {
            pila.push(cadena[i]);
        }
        else if (cadena[i] == ')')
        {
            if (pila.empty())
            {
                return false;
            }
            pila.pop();
        }
    }
    return true;
}

int main()
{
    string cadena = "())";
    if (esParentesisValido(cadena))
    {
        cout << "La cadena es valida" << endl;
    }
    else
    {
        cout << "La cadena no es valida" << endl;
    }
    return 0;
}

Diego Herrera Prado

student•

Comparto mi solución en python usando complejidad espacial O(1) . . . . . . . .

def isValid(s):
   num_open = 0
   for i in range(len(s)):
      if num_open <0:
         return False

      if s[i] == "(":
         num_open +=1
      elif s[i] == ")":
         num_open -= 1

   return num_open == 0

Gabriel Revelo

student•

puedes usar s sin range y sin len

def isValid(s):
    pila=0
    for i in s:
        if i=='(':
          pila+=1
        elif i==')':
           pila-=1
        if pila<0:
           return False  
    return pila==0

isValid('(()))')

def check_parentesis(case:str)->bool:
    #Create the stack 
    new_stack = Stack()
    for i in case:
        new_stack.append(i)
    # iterate over the stack and chase '(' or ')'on it
    prev = new_stack.top
    current = prev.next
    check = Stack()
    flag = 0
    flag2 = 0
    while prev and prev.next:
        if prev and prev.data == ')':
            check.append(prev)
            flag += 1
        if current and current.data == '(':
            check.append(current)
            flag2 += 1 
        prev = prev.next
        current = current.next
    if flag and flag2 > 0 and flag == flag2:
        return True
    else:
        return False 
```def check\_parentesis(case:str)->bool:    #Create the stack     new\_stack = Stack()    for i in case:        new\_stack.append(i)    # iterate over the stack and chase '(' or ')'on it    prev = new\_stack.top    current = prev.next    check = Stack()    flag = 0    flag2 = 0    while prev and prev.next:        if prev and prev.data == ')':            check.append(prev)            flag += 1        if current and current.data == '(':            check.append(current)            flag2 += 1         prev = prev.next        current = current.next    if flag and flag2 > 0 and flag == flag2:        return True    else:        return False&#x20;

int parentesis=0;
std::string texto;
std::cin>>texto;
&#x20; for (int i = 0; i < texto.length(); ++i) {
&#x20;     if (texto\[i]=='('){
&#x20;         parentesis++;
&#x20;     }else if (texto\[i]==')'){
&#x20;         parentesis--;
&#x20;     }else
&#x20;         continue;
&#x20; }

&#x20; if (parentesis==0){
&#x20;     std::cout<<"Hay correcto orden de parentesis"<\<std::endl;
&#x20; }else{
&#x20;     std::cout<<"No hay correcto Orden"<\<std::endl;
&#x20; }

#include<iostream>
#include<string>


bool valid_parentheses(std::string input){
	
	int check_open = 0;
	for(char c: input){
		if(c == '('){
			check_open++;
		}
		else if (!check_open && c == ')' ){
			return false;
		}
		else if (check_open && c == ')' ){
			check_open--;
		}
	}


	if (check_open != 0) return false;
	return true;

}


int main(){


	std::string input = ")(";
	if(valid_parentheses(input)) std::cout << "valid" << std::endl;
	else std::cout << "not" << std::endl;
	input = "asd)asd(da";
	if(valid_parentheses(input)) std::cout << "valid" << std::endl;
	else std::cout << "not" << std::endl;
	input = "()()";
	if(valid_parentheses(input)) std::cout << "valid" << std::endl;
	else std::cout << "not" << std::endl;
	input = "(dfa)(asdf";
	if(valid_parentheses(input)) std::cout << "valid" << std::endl;
	else std::cout << "not" << std::endl;
	input = "(dfa)(asdf)";
	if(valid_parentheses(input)) std::cout << "valid" << std::endl;
	else std::cout << "not" << std::endl;
	input = "(dfa)(asdf))";
	if(valid_parentheses(input)) std::cout << "valid" << std::endl;
	else std::cout << "not" << std::endl;

	return 0;
}

def valid_parentheses(input: str):
    print(f"checking {input=}")
    stack = []

    for elem in input:
        if elem == '(':
            stack.append(elem)
        elif elem == ')':
            if len(stack) != 0 and stack[-1] == '(':
                stack.pop()
            else:
                return "No valid"
        elif elem.isalpha() or elem.isnum():
            continue

    if len(stack) != 0:
        return "No valid"

    return "Valid"

print(valid_parentheses("()"))
print(valid_parentheses("(()))"))
print(valid_parentheses("("))
print(valid_parentheses(")"))
print(valid_parentheses(")("))
print(valid_parentheses("(caracoles)(decolores)()"))

```def valid\_parentheses(input: str):

&#x20;   print(f"checking {input=}")

&#x20;   stack = \[]

&#x20;   for elem in input:

&#x20;       if elem == '(':

&#x20;           stack.append(elem)

&#x20;       elif elem == ')':

&#x20;           if len(stack) != 0 and stack\[-1] == '(':

&#x20;               stack.pop()

&#x20;           else:

&#x20;               return "No valid"

&#x20;       elif elem.isalpha() or elem.isnum():

&#x20;           continue

&#x20;   if len(stack) != 0:

&#x20;       return "No valid"

&#x20;   return "Valid"

print(valid\_parentheses("()"))

print(valid\_parentheses("(()))"))

print(valid\_parentheses("("))

print(valid\_parentheses(")"))

print(valid\_parentheses(")("))

print(valid\_parentheses("(caracoles)(decolores)()"))

#!/usr/bin/env python3
"""Check for valid or balanced parentheses"""

size = 50
stack = ['' for _ in range(size)]
top = -1

def push(ch: str) -> None:
    """Push ch into stack"""
    global top
    if top == size-1:
        return
    else:
        top += 1
        stack[top] = ch

def pop() -> int:
    """Pop off the top data in the stack"""
    global top
    if top == -1:
        return -1
    else:
        data = stack[top]
        top -= 1
        return data
        
def isStackEmpty() -> bool:
    """Check if stack is empty"""
    if (top == -1):
        return True
    else:
        return False
        
def isStackFull() -> bool:
    """Check if stack is full"""
    if (top == size-1):
        return True
    else:
        return False
        
def isBalanced(str: str) -> bool:
    """Check if parenthese is valid"""
    for ch in str:
        if (ch == '(' or ch == '[' or ch == '{'):
            push(ch)
        else:
            if isStackEmpty():
                return False
            
            top = pop()
            
            if ((ch == ')' and top != '(') or
                (ch == ']' and top != '[') or
                (ch == '}' and top != '{')):
                
                return False
                
    return isStackEmpty()
        
def isValid(str: strg) -> bool:
    """Check if parenthese is valid"""
    parentheses = {'(':')', '[':']', '{':'}'}
    stack = []
    for ch in strg:
        if (ch in parentheses.keys()):
            stack.append(ch)
        else:
            if stack == []:
                 return False
    
            top = stack.pop()
            
            if ch != parentheses[top]:
            
                return False
                
    return stack == []
    
if __name__ == '__main__':

    parentheses = input("Enter parentheses to test\n").strip()
    
    if (isBalanced(parentheses)):
        print("Valid parentheses")
    else:
        print("Oops! Invalid parentheses")
    
    if (isBalanced(parentheses)):
        print("Valid parentheses")
    else:
        print("Oops! Invalid parentheses")
        
```#!/usr/bin/env python3

"""Check for valid or balanced parentheses"""

size = 50

stack = \['' for \_ in range(size)]

top = -1

def push(ch: str) -> None:

&#x20;   """Push ch into stack"""

&#x20;   global top

&#x20;   if top == size-1:

&#x20;       return

&#x20;   else:

&#x20;       top += 1

&#x20;       stack\[top] = ch

def pop() -> int:

&#x20;   """Pop off the top data in the stack"""

&#x20;   global top

&#x20;   if top == -1:

&#x20;       return -1

&#x20;   else:

&#x20;       data = stack\[top]

&#x20;       top -= 1

&#x20;       return data

&#x20;      &#x20;

&#x20;      &#x20;

def isStackEmpty() -> bool:

&#x20;   """Check if stack is empty"""

&#x20;   if (top == -1):

&#x20;       return True

&#x20;   else:

&#x20;       return False

&#x20;      &#x20;

def isStackFull() -> bool:

&#x20;   """Check if stack is full"""

&#x20;   if (top == size-1):

&#x20;       return True

&#x20;   else:

&#x20;       return False

&#x20;      &#x20;

def isBalanced(str: str) -> bool:

&#x20;   """Check if parenthese is valid"""

&#x20;   for ch in str:

&#x20;       if (ch == '(' or ch == '\[' or ch == '{'):

&#x20;           push(ch)

&#x20;       else:

&#x20;           if isStackEmpty():

&#x20;               return False

&#x20;          &#x20;

&#x20;           top = pop()

&#x20;          &#x20;

&#x20;           if ((ch == ')' and top != '(') or

&#x20;               (ch == ']' and top != '\[') or

&#x20;               (ch == '}' and top != '{')):

&#x20;              &#x20;

&#x20;               return False

&#x20;              &#x20;

&#x20;   return isStackEmpty()

&#x20;      &#x20;

&#x20;      &#x20;

def isValid(str: strg) -> bool:

&#x20;   """Check if parenthese is valid"""

&#x20;   parentheses = {'(':')', '\[':']', '{':'}'}

&#x20;   stack = \[]

&#x20;   for ch in strg:

&#x20;       if (ch in parentheses.keys()):

&#x20;           stack.append(ch)

&#x20;       else:

&#x20;           if stack == \[]:

&#x20;                return False

&#x20;  &#x20;

&#x20;           top = stack.pop()

&#x20;          &#x20;

&#x20;           if ch != parentheses\[top]:

&#x20;          &#x20;

&#x20;               return False

&#x20;              &#x20;

&#x20;   return stack == \[]

&#x20;  &#x20;

if \_\_name\_\_ == '\_\_main\_\_':

&#x20;   parentheses = input("Enter parentheses to test\n").strip()

&#x20;  &#x20;

&#x20;   if (isBalanced(parentheses)):

&#x20;       print("Valid parentheses")

&#x20;   else:

&#x20;       print("Oops! Invalid parentheses")

&#x20;  &#x20;

&#x20;   if (isBalanced(parentheses)):

&#x20;       print("Valid parentheses")

&#x20;   else:

&#x20;       print("Oops! Invalid parentheses")

&#x20;      &#x20;

&#x20;      &#x20;

&#x20;      &#x20;

#include <iostream>
#include <stack>
#include <string>

using namespace std;

bool esParentesisValido(string cadena)
{
    stack<char> pila;

    for (int i = 0; i < cadena.length(); i++)
    {
        if (cadena[i] == '(')
        {
            pila.push(cadena[i]);
        }
        else if (cadena[i] == ')')
        {
            if (pila.empty())
            {
                return false;
            }
            pila.pop();
        }
    }
    return true;
}

int main()
{
    string cadena = "())";
    if (esParentesisValido(cadena))
    {
        cout << "La cadena es valida" << endl;
    }
    else
    {
        cout << "La cadena no es valida" << endl;
    }
    return 0;
}

def isValid(s):
   num_open = 0
   for i in range(len(s)):
      if num_open <0:
         return False

      if s[i] == "(":
         num_open +=1
      elif s[i] == ")":
         num_open -= 1

   return num_open == 0 

Solución de Paréntesis Válido

Introducción

¿Ya tomaste el Curso Avanzado de Algoritmos: Patrones de Arrays y Strings?

Lista Enlazada

Estructura de datos: Lista Enlazada

Programando listas enlazadas con Java

Cómo Invertir una Lista Enlazada

Odd Even Linked List: análisis del problema

Solución de Odd Even Linked List

Playground: Odd Even Liked List

Programando Odd Even Linked List con C++

Linked List Cycle: análisis del problema

Solución de Linked List Cycle

Playground: Linked List Cycle

Programando Linked List Cycle con Python

Palindrome Linked List: análisis del problema

Solución de Palindrome Linked List

Playground: Palindrome Linked List

Programando Palindrome Linked List con Java

Reorder List: análisis del problema

Solución de Reorder List

Programando Reorder List con JavaScript

Playground: Reorder List Without Repeated Values

Reto: LRU Caché

Ejercicios Prácticos con Listas Enlazadas y Historial de Navegador

Operaciones con Listas Enlazadas: Suma, Intercambio y Navegador

Pilas y colas

Estructura de datos: Pilas y Colas

Paréntesis Válido: análisis del problema