Common Subexpression Elimination in JavaScript

Common subexpression elimination (CSE) is an optimization technique used in compilers to reduce code size and improve performance. It identifies identical expressions within a program and replaces them with a single calculation, storing the result in a temporary variable for reuse. This challenge asks you to implement a simplified CSE algorithm in JavaScript to identify and eliminate common subexpressions within an array of JavaScript expressions.

Problem Description

You are tasked with creating a JavaScript function eliminateCommonSubexpressions(expressions) that takes an array of JavaScript expressions as input and returns a new array with common subexpressions eliminated. The expressions are represented as strings. The function should analyze the input array, identify identical expressions, and replace subsequent occurrences of those expressions with a reference to a temporary variable. The temporary variable names should be unique and follow the format temp_1, temp_2, etc.

Key Requirements:

• Expression Identification: The function must accurately identify identical expressions within the input array.
• Temporary Variable Generation: It should generate unique temporary variable names (e.g., temp_1, temp_2) for storing the results of common subexpressions.
• Replacement: Subsequent occurrences of a common subexpression should be replaced with the generated temporary variable name.
• Order Preservation: The order of the remaining unique expressions should be preserved.
• String Manipulation: The function should work with expressions represented as strings.

Expected Behavior:

The function should return a new array where common subexpressions have been replaced with temporary variables. The original array should not be modified.

Edge Cases to Consider:

• Empty input array.
• Array with only one expression.
• Expressions containing variables.
• Expressions with different whitespace. (Whitespace should be ignored when comparing expressions).
• Expressions that are substrings of other expressions.
• Expressions containing operators and parentheses.

Examples

Example 1:

Input: ["a + b", "a + b", "c * d", "a + b"]
Output: ["a + b", "temp_1", "c * d", "temp_1"]
Explanation: The expression "a + b" appears multiple times. It's stored in `temp_1`, and subsequent occurrences are replaced with `temp_1`.

Example 2:

Input: ["x * y", "x * y + z", "x * y", "z / w"]
Output: ["x * y", "temp_1 + z", "temp_1", "z / w"]
Explanation: "x * y" is a common subexpression. The first occurrence remains, subsequent occurrences are replaced with `temp_1`.

Example 3:

Input: ["2 * (a + b)", "2 * (a + b) + c", "2 * (a + b)"]
Output: ["2 * (a + b)", "temp_1 + c", "temp_1"]
Explanation:  Handles expressions with parentheses and operators correctly.

Example 4:

Input: []
Output: []
Explanation: Handles empty input array.

Constraints

• The input array expressions will contain strings representing JavaScript expressions.
• Each expression string will have a maximum length of 256 characters.
• The number of expressions in the input array will be between 0 and 100.
• The function should have a time complexity of O(n^2) where n is the number of expressions in the input array. While more efficient algorithms exist, this constraint is to keep the problem manageable.
• The function should have a space complexity of O(n) where n is the number of expressions in the input array.

Notes

• You can ignore whitespace when comparing expressions. For example, "a + b" and "a+b" should be considered identical.
• Focus on identifying and replacing exact string matches. Don't attempt to parse or evaluate the expressions.
• The temporary variable names should be simple and consistent (e.g., temp_1, temp_2, temp_3).
• Consider using a Map or Set to efficiently track already encountered expressions.
• The goal is to demonstrate the core concept of CSE, not to create a production-ready compiler optimization tool.