Feature #9: Validate Program Brackets

Implement the "Validate Program Brackets" feature for our "Language Compiler" project.

We'll cover the following

Description

A compiler verifies multiple things during a specific language compilation. Sometimes, things get complex when new features are introduced in programming languages. For instance, consider the anonymous functions in JavaScript. Couple these with asynchronous calls, and functions nested inside functions, and things get even more complicated.

The compiler processes a piece of code and removes the line breaks, which leaves behind a string containing code with possibly nested braces, parentheses, and square brackets. Then, we take this string as input and validate that the braces, square brackets, and parentheses are all perfectly matched. The compiler verifies the brackets’ order to check the program’s validity and other verifications.

The following is the anonymous function structure:

alert((function(n) {
  return !(n > 1)
    ? 1
    : arguments.callee(n - 1) * n;
})(15));

Solution

We will solve this problem with the help of the stack data structure.

The complete algorithm is as follows:

  1. The function will receive a function code in input as a string.

  2. We will compare each character of the given string with all the possible delimiters in each loop iteration.

  3. The current loop iteration will stop immediately if the current character is not any of the following:

    • ( , [ , {
    • ) , ] , }

  4. Next, if the stack is not empty or the current string character is either a closing brace, parenthesis, or square bracket, we will perform a pop operation on the stack.

  5. Otherwise, if the current character is either a starting brace, parenthesis, or square bracket, we will push the current character to the stack.

  6. In the end, the program will return true if the stack is empty and false if it is not empty.

The following slides illustrate this process:

Level up your interview prep. Join Educative to access 70+ hands-on prep courses.