Skip to content

Instantly share code, notes, and snippets.

@32teeth

32teeth/validateUsingDomParser.js

Last active September 5, 2024 18:09
Show Gist options
  • Save 32teeth/0eae76379ff8a0be2c53c8ce263202dc to your computer and use it in GitHub Desktop.
Save 32teeth/0eae76379ff8a0be2c53c8ce263202dc to your computer and use it in GitHub Desktop.
Download ZIP
Pfft.
Raw
validateUsingDomParser.js
/**
* Ask clarifying questions:
* - What types of input are we expecting (valid HTML strings)?
* - What should happen in the event of invalid or non-HTML inputs?
* - Should we focus solely on HTML or handle any generic XML/HTML-like string input?
*
* Analyze various solutions and tradeoffs:
* - We could use `DOMParser()` to parse the HTML and detect structural errors.
* - Alternative methods like regular expressions are not suitable for parsing HTML due to its complexity.
* - A browser's `DOMParser` is the standard way to check for valid HTML structure.
*
* Plan solution with pseudocode:
* - Parse the input string using `DOMParser` in 'text/xml' mode (strict).
* - Check if a `parsererror` element is generated in the parsed document.
* - If a `parsererror` is found, the HTML is invalid, otherwise it's valid.
*
*/
/**
* Implement solution:
* @param {string} html - Input HTML string to validate
* @returns {boolean} - True if HTML is valid, false if it's invalid
*/
const validateUsingDomParser = (html) => {
/**
* Constraints:
* - Expected return: boolean (true for valid, false for invalid HTML)
* - TypeError: If a non-string input is provided.
* - DOMParser will treat the input as 'text/xml' to strictly parse the HTML structure.
*/
if (typeof html !== 'string') throw new TypeError('Expected a string input'); // TypeError for non-string input
/**
* Plan:
* - Use `DOMParser` to parse the input string.
* - Use 'text/xml' mode to detect any structural errors in the HTML.
* - Check if the parsed document contains a `parsererror` element.
* - Return false if a parsing error is found, otherwise return true.
*/
const parser = new DOMParser();
const doc = parser.parseFromString(html, 'text/xml'); // Set mode to 'text/xml' to avoid lenient parsing of HTML
// If 'parsererror' exists in the parsed document, the HTML is invalid
return doc.documentElement.querySelector('parsererror') ? false : true;
}
console.table(results);
/** HTML Tests *
* Known Pass, Forced Fail / Eject
*/
const strings = [
'', // Empty string
'<html></html>', // Simple valid case
'<html><head></head><body></body></html>', // Valid HTML structure
'<html><head></head><body></body>', // Unbalanced opening tag
'<html><head></head></html></body>', // Unbalanced closing tag
'<html><head></head><body></body>', // Unbalanced opening tag
'<html><head></head><body></body></html>', // Unbalanced closing tag
'<html><head></head><body></body></html',
'<html><head></head><body></body></html>',
'<html><head></head></html><body></body>', // Unbalanced closing tag
null, // Null input, should throw TypeError
undefined, // Undefined input, should throw ReferenceError
123, // Number input, should throw TypeErro
];
let results = strings.map((html) => {
try {
return { input: html, output: validateUsingDomParser(html) };
} catch (error) {
return { input: html, error: error.name, message: error.message };
}
});
console.table(results);
Raw
validateUsingRegex.js
/**
* Ask clarifying questions:
* - What types of input are we expecting (strings, numbers, etc.)?
* - What should happen in the event of non-string inputs?
* - Are we always expecting balanced and valid bracket expressions, or should we handle invalid input gracefully?
*
* Analyze various solutions and tradeoffs:
* - We could iterate over the string and push each opening bracket to a stack and pop when encountering a matching closing bracket (standard stack-based approach).
* - We could use regular expressions to strip out matching pairs and keep reducing the string until no more matches exist (current approach).
* - Stack-based solution may be clearer but possibly slower for large inputs, while the regular expression solution can be faster in some cases but harder to reason about for maintainers.
*
* Plan solution with pseudocode:
* - Remove all non-bracket characters.
* - Keep replacing matching pairs of brackets using regular expressions.
* - Check if the final string is empty.
*
*/
/**
* Implement solution:
* @param {*} str
* @returns
*/
const validateUsingRegex = (str) => {
/** Clarifications / Problem: Validate balanced brackets in a string */
/**
* Constraints:
* - Expected return: boolean (true if valid, false otherwise)
* - TypeError: If a non-string input is provided.
* - RangeError: If the input string exceeds a safe integer limit (improbable in most real cases).
* - ReferenceError: If the string is undefined.
*/
if (typeof str === 'undefined') throw new ReferenceError('Input string is undefined'); // ReferenceError for undefined input
if (typeof str !== 'string') throw new TypeError('Expected a string input'); // TypeError for non-string input
if (str.length > Number.MAX_SAFE_INTEGER) throw new RangeError('Input string is too large'); // RangeError for exceedingly large input
if (!str.length) return true; // Empty string is considered valid
/** Plan:
* - Remove non-bracket characters.
* - Iteratively remove matching pairs of brackets ({} [] ()).
* - If the string is empty after these replacements, return true.
* - Otherwise, return false.
*/
let tmp_str;
str = str.replace(/[^{}[\]()]/g, ''); // Remove non-bracket characters
if (!str.length) return false; // If the string is empty, return false
while (tmp_str !== str) {
tmp_str = str;
str = str.replace(/{}|\[]|\(\)/g, ''); // Remove matching pairs
}
// return the offending bracket with a message
if (str.length) {
throw new Error(`Unbalanced brackets ${str}`);
}
return !str; // Return true if the string is empty, otherwise return false
}
/** Tradeoffs:
* - Regular expressions are compact but may not be as clear to read as a stack-based solution.
* - Performance could degrade for very large inputs compared to a more manual stack-based approach.
*/
/** Tests *
* Known Pass, Forced Fail / Eject
*/
const strings = [
'', // Empty string
'{<>}', // Simple valid case
'[]', // Simple valid case
'()', // Simple valid case
'{', // Unbalanced opening bracket
'}', // Unbalanced closing bracket
'[', // Unbalanced opening bracket
']', // Unbalanced closing bracket
'(', // Unbalanced opening bracket
')', // Unbalanced closing bracket
'{{{{}}}}', // Nested valid braces
'[{()}]', // Nested different types, valid
'{[[(())]]}', // Deeply nested valid
'{{[[(())]]}}', // More complex nesting
'{[([()])]}', // Nested with mix of valid cases
'{[{[{[{[{[]}]}]}]}]}', // Very deep nesting
'{[(])}', // Incorrectly nested
'(((((())))))', // Only parentheses, deeply nested
'[{]}', // Incorrectly nested
'{ [(] ) }', // Mixed with a misplaced closing bracket
'{[() ()]}[(])', // Mixed valid and invalid
'[[[[[[[[[]]]]]]]]]', // Deeply nested with only square brackets
'[[[[[[[[]]]]]]]]', // Unbalanced deeply nested
null, // Null input, should throw TypeError
undefined, // Undefined input, should throw ReferenceError
123, // Number input, should throw TypeError
'abc', // Non-bracket string, should return false
'({)}', // Incorrectly nested
'abc{def[ghi]jkl}mno', // Non-bracket characters
'<[]>', // Angle brackets included, valid case
'<[()]>', // Angle brackets with valid nesting
'<[()]><{}>', // Multiple valid bracket pairs
'<[({})]>', // Mixed valid nested brackets
'<[({})]>[]{}()', // Mixed valid
'<({[}])>', // Incorrectly nested with angle brackets
];
let results = strings.map((str) => {
try {
return { input: str, output: validateUsingRegex(str) };
} catch (error) {
return { input: str, error: error.name, message: error.message };
}
});
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment