Basic JIT Compiler in JavaScript

This challenge asks you to implement a simplified Just-In-Time (JIT) compiler in JavaScript. JIT compilers dynamically translate code during runtime, offering a balance between the portability of interpreted languages and the performance of compiled languages. This exercise will focus on a very basic subset of JavaScript to illustrate the core concepts.

Problem Description

You are tasked with creating a rudimentary JIT compiler that can optimize simple arithmetic expressions. The compiler will receive a string representing an expression consisting of addition (+) and subtraction (-) operations between integer numbers. The compiler should parse this expression, identify common sub-expressions, and then generate a new, optimized expression string. The optimization strategy is to evaluate and replace any constant sub-expression (e.g., "2 + 3") with its calculated value (e.g., "5").

What needs to be achieved:

1. Parsing: Parse the input expression string into a tree-like structure (you can represent this as nested arrays).
2. Evaluation: Evaluate constant sub-expressions within the parsed tree. A constant sub-expression is one where all operands are numbers.
3. Replacement: Replace the constant sub-expression with its calculated numerical value in the expression string.
4. String Reconstruction: Reconstruct the optimized expression string from the modified tree.

Key Requirements:

• The input expression will only contain integers, '+', and '-' operators.
• The input expression will be well-formed (no syntax errors).
• The compiler should handle multiple levels of nested expressions.
• The output should be a string representing the optimized expression.

Expected Behavior:

The compiler should prioritize evaluating and replacing the innermost constant sub-expressions first. The order of evaluation within the same level of nesting doesn't matter.

Edge Cases to Consider:

• Expressions with only a single number (no operations).
• Expressions with leading or trailing spaces (should be ignored).
• Expressions with multiple consecutive operators (e.g., "2 + -3"). Treat these as valid.
• Negative numbers.

Examples

Example 1:

Input: "2 + 3 - 1"
Output: "5 - 1"
Explanation: The sub-expression "2 + 3" is evaluated to 5, replacing it in the original string.

Example 2:

Input: "1 + 2 + 3 - 4"
Output: "3 + 3 - 4"
Explanation: "1 + 2" is evaluated to 3, replacing it. Then "3 + 3" is evaluated to 6, replacing it.

Example 3:

Input: "5 - 2 + 1 - 3"
Output: "3 + 1 - 3"
Explanation: "5 - 2" is evaluated to 3, replacing it.

Example 4:

Input: "10"
Output: "10"
Explanation: A single number is not an expression requiring optimization.

Example 5:

Input: "2 + 3 - (4 - 1)"
Output: "2 + 3 - 3"
Explanation: Parentheses are not supported in this simplified JIT compiler. The expression is treated as "2 + 3 - 4 + 1".

Constraints

• The input expression string will have a maximum length of 256 characters.
• All numbers in the expression will be integers between -1000 and 1000 (inclusive).
• The compiler should complete within 100ms for any valid input.
• The output string should not contain any leading or trailing spaces.

Notes

• You can use recursion to traverse the expression tree.
• Consider using a helper function to evaluate a sub-expression.
• Focus on the core concepts of parsing, evaluation, and replacement. Error handling and more complex optimizations are beyond the scope of this challenge.
• The parsing can be done by splitting the string based on operators, but be mindful of negative numbers. A more robust parsing strategy might be needed for more complex expressions.
• Think about how to represent the expression tree in a way that makes evaluation and replacement easy. A nested array structure is a good starting point.