Conditions of the problem

Implement and export a default function that accepts a string consisting of only opening and closing parentheses as input and checks whether this string is valid. An empty string (no parentheses) is considered valid.

A string is considered correct (balanced) if the bracket structure contained in it meets the requirements:

Скобки — это парные структуры. У каждой открывающей скобки должна быть соответствующая ей закрывающая скобка. Закрывающая скобка не должна идти впереди открывающей.

import areBracketsBalanced from 'roundBracketsValidator';

areBracketsBalanced ('(())'); // true areBracketsBalanced ('((())'); // false

My solution is not validated. Writes const str7 = '()) (()';

37 | expect (areBracketsBalanced (str7)). toBe (false); My code below

 const areBracketsBalanced = (str) => { let leftBrackets = ''; let rightBrackets = ''; switch(str[0]) { case ')': return false; break; case '': return true; break; }; if (str[str.length - 1] === '(') { return false; }; for (let i = 0; i < str.length; i++) { if (str[i] === '(') { leftBrackets += str[i]; } else if (str[i] === ')') { rightBrackets += str[i]; } }; if (leftBrackets.length === rightBrackets.length) { return true; } else { return false; } }; export default areBracketsBalanced;

What can be fixed?

  • 3
    Why so hard? just run along the line and count. Opening - plus one, closing - minus one, if suddenly the sum minus one is a slanting line, you can not look further, if the result is not zero - a slanting line. Everything ... - Akina
  • Once I did it in php like this: bitbucket.org/num8er/gsm-tasks/src/master/public/… ... stack method - num8er

1 answer 1

Your algorithm is heavily overloaded with unnecessary actions, but if you still want to implement a check like this - with the accumulation of leftBrackets and rightBrackets - then you still need to make sure that in the process of accumulating these strings rightBrackets.length never exceeds leftBrackets.length . This should be checked precisely in the accumulation cycle, and not after it. If rightBrackets.length > leftBrackets.length at some point, the parentheses are not balanced and further testing is meaningless.

Additional private checks that you set before the loop are completely unnecessary and only complicate the code. The cycle itself perfectly captures these violations.

But in fact, all this can be implemented much easier. No strings need to be accumulated at all. You just need to start the counter of open brackets, which is increased by 1 for ( and decreases by 1 for ) . The brackets are balanced if in the process of counting this counter never became negative and at the end of the count it is strictly 0 .

Such a simple solution is possible only for the case of brackets of the same type. As soon as it comes to several types of brackets at the same time, an algorithm is required that requires either additional memory (stack) or multi-pass / random access to the input sequence.

  • one
    As soon as it comes to several types of brackets at the same time, an algorithm requiring additional memory (stack) is required. Not necessary. Its own variable for each type of brackets, and permission for a closing bracket of a different type (change of type compared to the previous bracket), only if for the current type the amount has become zero. - Akina
  • @Akina: I do not understand. Here in this case ([{}]) where is the "type change from the previous bracket"? - AnT
  • First bracket: cnt '()' = 1, curr = '()'. The second bracket: cnt '[]' = 1, curr = '[]'. Third bracket: cnt '{}' = 1, curr = '{}'. The fourth bracket: closing, the type coincides with curr - valid, cnt '{}' = 0, curr = null (if the counter became non-zero, the type would remain curr = '{}'). Fifth bracket: closing, curr does not limit - valid, cnt '[]' = 0, curr = null. The sixth bracket: closing, curr does not limit - valid, cnt '()' = 0, curr = null. End of parsing, all counters are zero, the line is valid. - Akina
  • So here is just? Well, now please disassemble [({}]) . How can your out of memory algorithm distinguish between the correct ([{}]) and the incorrect [({}]) ? - AnT
  • @Akina stack is required for several types of brackets (except for the tricky replacement option, which requires even more memory). write the answer with the code "without stack", I will easily select, a counterexample. This is a standard task with interviews, it regularly someone breaks up without a stack to solve :) - PashaPash ♦