JS – walidacja nawiasów

Jedno z podstawowych i najbardziej popularnych zagadnień stosowych – walidacja nawiasów. Poznajemy ten algorytm!

Ok, oto kod:

function validateBrackets_v2(str){

    const opening = new Set(["(", "[", "{"]);
    const closing = new Set(["}", ")", "]"]);

    let map = new Map();

    map.set("(", ")");
    map.set("[", "]");
    map.set("{", "}");
    
    let stack = [];

    for(let i = 0; i <str.length; i++){
        if(opening.has(str[i])){
            stack.push(str[i]);
        } 
        else if(closing.has(str[i])){
            let lastInserted = stack.pop();
            if(map.get(lastInserted) !== str[i])
                return false;
        }
        
    }

    return stack.length === 0;
    

}

console.log(validateBrackets_v2("((( [[]] {{{}}}  )))"));

Mechanizm działania jest następujący:

• Przejdź po każdym znaku
• Jeżeli znak jest znakiem otwierającym, wrzuć go na stos
• Jeżeli znak jest znakiem zamykającym zrzuć ostatni otwierający ze stosu i porównaj, czy są odpowiednie (czy się zgadzają otwarcie z zamknięciem)
• Jeżeli pętla się zakończyła i nie było return false to i tak trzeba porównać, czy stos jest pusty, (edge case gdy ktoś otworzył więcej niż zamknął co nie zostało wykryte wcześniej z oczywistych względów)

Możemy tam dodać kolejne znaki, np. < oraz > i dalej będzie ok…