Frontend School

Syntax Validation: Nested Parentheses and Contextual Brackets

DSA
medium

Syntax Validation: Nested Parentheses and Contextual Brackets

Medium
Stack
String
Parsing
syntax-validation
Data Structures
Coding-Interview
practice

Overview

This problem challenges you to validate the syntax of a simplified programming construct involving multiple types of nested delimiters. You are given a string representing a snippet of "MacroScript" code. The task is to determine if all delimiters are correctly matched, properly nested, and adhere to specific contextual rules for a special "macro block" delimiter. This problem is a classic application of stack data structures for parsing and syntax validation.

What you need to do / Task

Implement a function isValidMacroScript that takes a string s representing a MacroScript snippet. The function should return true if the string has a valid sequence of delimiters according to the rules below, and false otherwise.

The delimiters are:

  1. Standard parentheses: ( and )
  2. Square brackets: [ and ]
  3. Curly braces: { and }
  4. Macro block delimiters: | and | (The same character | serves as both opening and closing.)

Rules for validity:

  • Every opening delimiter must have a corresponding closing delimiter of the same type.
  • Opening delimiters must be closed in the correct order (i.e., they must be properly nested).
  • Special Rule for Macro Blocks: A macro block |...| can only contain standard parentheses () and square brackets []. It cannot contain curly braces {}. If a curly brace { or } is encountered within a |...| block, the string is invalid.
  • Other characters (non-delimiter characters) in the input string should be ignored for validation purposes.

Input & output

Input: s: A string consisting of various characters, including the specified delimiters.

Output: boolean: true if the input string s is valid according to the rules, false otherwise.

Function Signature (TypeScript):

function isValidMacroScript(s: string): boolean

Function Signature (JavaScript):

function isValidMacroScript(s: string): boolean

Clarifications

  • Q: What if the string is empty or contains only non-delimiter characters?
    • A: An empty string or a string with only non-delimiter characters is considered valid.
  • Q: How should | be handled if it's not part of a pair?
    • A: A single | character acts as both an opening and a closing delimiter for macro blocks. If you encounter | and the top of the stack is also |, it signifies a closing | for the current macro block. Otherwise, it acts as an opening |.
  • Q: Do | characters count as matching if they are not the top of the stack?
    • A: No. Like other delimiters, | must match the most recently opened | (which would be at the top of the stack). For example, (|[]) is invalid because ) is attempting to close |.
  • Q: Are there any length limits on the input string?
    • A: Yes, refer to the "Constraints & assumptions" section.

Examples

1

Example 1

Input:

s = "([{}])"

Output:

true

Note:

All standard delimiters are matched and properly nested. No macro blocks are present, so the special rule is not violated.

2

Example 2

Input:

s = "|[a]b(c)|"

Output:

true

Note:

The macro block |...| contains only square brackets and parentheses, which is allowed. All delimiters are matched and nested correctly.

3

Example 3

Input:

s = "|{a}|"

Output:

false

Note:

The macro block |...| contains curly braces {}, which violates the special rule (macro blocks cannot contain curly braces).

4

Example 4

Input:

s = "([)]"

Output:

false

Note:

The square bracket [ is not closed before the parenthesis ( is closed. This is an example of incorrect nesting.

5

Example 5

Input:

s = "|(|)"

Output:

false

Note:

When processing |(|):

  1. |: Push |. Stack: [|]
  2. (: Push (. Stack: [|, (]
  3. |: This acts as an opening | (stack top is (). Push |. Stack: [|, (, |]
  4. ): Mismatches with stack top |. Invalid.

Constraints

Constraints & assumptions

  • 1 <= s.length <= 10^4
  • The string s will only contain standard ASCII characters.
  • The delimiters are (, ), [, ], {, }, and |.
  • All other characters should be ignored for validation purposes.

What graders evaluate

  • Correctness: Does the solution accurately determine the validity of all test cases, including edge cases for empty strings, strings with only non-delimiters, and strings violating the macro block rule?
  • Efficiency: Does the solution process the input string in optimal time and space complexity, typically O(N) time and O(N) space where N is the length of the string?
  • Clarity and Readability: Is the code well-structured, easy to understand, and appropriately commented?
  • Edge Case Handling: Does the solution correctly manage scenarios like unmatched opening/closing delimiters, or invalid nesting?

Loading editor...