Solución de Paréntesis Válido

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:

```python 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

Mi solución sin utilizar pilas en C++ ```cpp int parentesis=0; std::string texto; std::cin>>texto; for (int i = 0; i < texto.length(); ++i) { if (texto\[i]=='('){ parentesis++; }else if (texto\[i]==')'){ parentesis--; }else continue; } if (parentesis==0){ std::cout<<"Hay correcto orden de parentesis"<\

```python 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): 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)()"))

```python #!/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: """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")

`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`


// 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("{{}}") )

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;
}

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