Abstract Syntax Tree (AST) Builder in JavaScript

Building an Abstract Syntax Tree (AST) is a fundamental task in many programming language tools, including compilers, interpreters, and code linters. This challenge asks you to create a simplified AST builder that transforms a basic arithmetic expression string into its corresponding AST representation. Successfully completing this challenge will give you a deeper understanding of how programming languages are parsed and represented internally.

Problem Description

You are tasked with creating a JavaScript function buildAST that takes a string representing a simple arithmetic expression as input and returns a JavaScript object representing the Abstract Syntax Tree (AST) for that expression. The expression will consist of integers, addition (+), and subtraction (-) operators. No parentheses or other operators are allowed.

The AST should be structured as follows:

• Number Node: Represents a numerical value. Has a type property set to "Number" and a value property holding the integer value.
• Binary Operator Node: Represents an addition or subtraction operation. Has a type property set to "BinaryOperator", a operator property holding the operator character ("+" or "-"), a left property referencing the AST node for the left operand, and a right property referencing the AST node for the right operand.

The buildAST function should parse the input string from left to right, constructing the AST incrementally. It should handle multiple operations in the expression correctly.

Key Requirements:

• The function must correctly parse valid arithmetic expressions.
• The function must return a valid AST object as described above.
• The function should handle single numbers correctly.
• The function should handle expressions with multiple operators.

Expected Behavior:

The function should return null if the input string is invalid (e.g., contains non-numeric characters other than '+', '-', or is empty).

Edge Cases to Consider:

• Empty input string.
• Input string containing only a number.
• Input string starting with an operator.
• Input string ending with an operator.
• Consecutive operators (e.g., "1++2"). These should be considered invalid.
• Non-numeric characters in the input string.

Examples

Example 1:

Input: "1+2-3"
Output: {
  type: "BinaryOperator",
  operator: "+",
  left: { type: "Number", value: 1 },
  right: {
    type: "BinaryOperator",
    operator: "-",
    left: { type: "Number", value: 2 },
    right: { type: "Number", value: 3 }
  }
}
Explanation: The expression is parsed from left to right. "1+2" creates a binary operator node with 1 as the left operand and "2-3" as the right operand. "2-3" then creates another binary operator node with 2 as the left operand and 3 as the right operand.

Example 2:

Input: "5"
Output: { type: "Number", value: 5 }
Explanation: A single number is simply represented as a Number node.

Example 3:

Input: ""
Output: null
Explanation: An empty string is considered invalid.

Example 4:

Input: "1++2"
Output: null
Explanation: Consecutive operators are invalid.

Constraints

• The input string will contain only digits (0-9), '+', and '-'.
• The input string will have a maximum length of 256 characters.
• The function must return the AST object or null within 100ms for valid inputs.
• The AST should be constructed recursively.

Notes

• Consider using a recursive approach to build the AST.
• You can use regular expressions to validate the input string.
• Think about how to handle operator precedence (although this problem doesn't explicitly require it, it's a good practice to keep in mind). In this simplified case, left-to-right evaluation is sufficient.
• Error handling is important. Return null for invalid input.
• Focus on clarity and readability of your code. Well-structured code is easier to understand and maintain.