I believe that once we build the tree, we should recurse down all the way to evaluate the expression. The recursion will stop when we reach a Number, because a Number can't be broken down any further.

Requirements:

• Number must be a subclass of ArithmeticExpression
• A Number should return its value as a string in evaluate(), and as a float in convert().
• A Number should have a constructor which takes a string and stores it as a float in a private variable

I may think of more later

Test Shilip's code.

#10

Ensure that a sequence like this:
"12345 32423"
causes the validator to return 0.

We need to implement this method so that we can convert the string expression returned by each ArithmeticExpression's evaluate() to a floating-point number. We also need to implement this in each subclass of ArithmeticExpression.

This algorithm assumes that the expression has already been validated.

Variables:

$n - The index in the string at which we start searching for unnecessary brackets
$l - The current "level" in the expression we are at - i.e., the # of left/right brackets seen so far.
$nPos - The position at which the number token starts in the string
$rBPos - The position at which the first right bracket is encountered.
$i - Current index in string (used while looping through the string)

Given a position $n which is the index of a starting left bracket:

1. Read the string from left to right, using tokens (not individual characters).
2. While reading - phase 1 (using a counter $i):
   • If the current token is a left bracket, increment a counter $l.
   • If you encounter a number token, store its starting position in the string in the variable $nPos.
   • Check if the next token is an operator. If it is, go back to step 2. If it isn't, check if it is a right bracket. If it is, store the position of the right bracket in the string in $rbPos and go to phase 2.
3. While reading - phase 2:
   • If the current token is a right bracket, decrement the counter $l.
   • If there is any token after a right bracket, we cannot simplify the brackets further. Go to the restart phase.
   • If you reach a position where the counter becomes 0, we have found the matching bracket of the one in position $n in the string. If we have not encountered any tokens after right brackets other than right brackets up to this point, we can simplify the expression. Go to step 4. Otherwise, go back to step 3.
4. Simplifying the expression:
   • If we got here, the previous parts of the algorithm have identified that the brackets in the ranges [$n, $nPos) and [$rbPos, $i] are unnecessary.
   • Use string functions to cut the number token out of the string (it occupies the positions in the range [$nPos, $rbPos)), and put it into a new string.
5. Restart phase:
   • Since we have identified that we cannot simplify this set of right brackets further, keep reading right and copying characters to the new string until your $l reaches 0 (following the rule of $l++ if we see a left bracket token, $l-- if we see a right bracket token.) This will allow you to skip the entire bracket which we started working with.
   • Search the string, going right until you find the first left bracket. Set $n to the position of this bracket, and restart the algorithm.

Implement the bonus, as described in the PDF.

• float convert
• string evaluate
• void print

The parser needs to be converted to use the project's classes.