1. Uvozovky

Na vstupu je string, který obsahuje závorky "(" a ")". Cílem úlohy je naprogramovat funkci, která zjistí, zda jsou ve vstupu závorky správně vnořené a uzavřené.

Příklad správného chování

const checkParentheses = (input: string): boolean => {
   // Zde doplň tělo funkce
} 
// Examples:
checkParentheses("()"); // true
checkParentheses("("); // false
checkParentheses("()))"); // false
checkParentheses("()(()"); // false
checkParentheses("()(())"); // true

Detaily

• Pokud je vstup prázdný, je validní.
• Pokud vstup obsahuje jiné znaky, než závorky, je nevalidní.

Malá nápověda

Nejdřív si napiš testy. Až začnou procházet, máš hotovo.

Střední nápověda

Vzpomeň si na základní datové struktury.

Střední nápověda

Pořád nevíš jaká datová struktura? Krabičky a víčka.

Velká nápověda - algoritmus

Začni číst vstup znak po znaku. Pokud je to otevírací závorka "(", vlož ji na zásobník a pokračuj.

Pokud je to zavírací závorka ")", vyndej poslední prvek ze zásobníku a zkontroluj, že je to otevírací závorka "(". Pokud ano, pokračuj. Pokud ne, skonči - vstup není validní.

Pokud je po přečtení celého vstupu zásobník prázdný, je to validní.

Rozšíření úlohy

Pokud ti základ funguje, rozšiř funkci tak, aby uměla pracovat i s dalšími typy závorek - "[]", "{}", "<>".

Řešení

const startEndMap = {
    "(": ")",
    "[": "]",
    "<": ">",
    "{": "}",
} as const satisfies Record<string, string>;
 
const ALLOWED_CHARACTERS = [
    ...Object.values(startEndMap),
    ...Object.keys(startEndMap),
] as const;
 
export const checkParentheses = (input: string): boolean => {
    const stack: string[] = [];
 
    for (const character of input) {
        if (!ALLOWED_CHARACTERS.includes(character)) return false;
 
        const isStartingParenthesis = !!startEndMap[character];
 
        if (isStartingParenthesis) {
            stack.push(character);
            continue;
        }
 
        const startingParenthesis = stack.pop();
        if (!startingParenthesis) return false;
 
        // Was it closed correctly?
        if (startEndMap[startingParenthesis] !== character) return false;
    }
 
    // After the run the stack should be empty - all parentheses were closed
    if (stack.length === 0) return true;
 
    return false;
};