The set of tokens of the language is {+,-,^,(,),NUMBER}. The token NUMBER represents unsigned integers, i.e., non-empty sequences of digits. Examples of correct expressions are

• “-(1)”
• “1+2^-3”
• “4^(-1+-2)^3”
• “1++2”

whereas

• “1+”
• “1(^2)”
• “2^^4”
• “1 2”

are not. The generated AST must correspond to an interpretation of the + and - binary operators as left-associative and exponentiation as right-associative. The precedence is as usual, with unary operators having the highest precedence, followed by exponentiation. As an example, for input 1^(-2+-3)^4 the resulting AST must be ^(1,^(+(-(2),-(3)),4)) i.e., as if the implicit parenthesization was 1^(((-2)+(-3))^4)