Write a program that will evaluate a prefix expression. The operators can be any of the following +, - * or /. The operands can be either an unsigned constant or a call to a polynomial function. The user should be prompted first for the prefix expression. The input might look as follows:
+ * 2.5 + P 7.4 6.3 8
The infix equivalent for the above is:
((2.5 * (P(7.4) + 6.3)) + 8)
After the prefix expression is input one polynomial should be input that corresponds to the polynomial P in the expression. The following is an example of the required formatting, 5 3 4 1 8 0 represents the polynomial 5x3 + 4x + 8.
As the prefix expression is read in, a binary tree should be built that represents the expression. Rather than having an abstract method draw defined in Node, define a method called evaluate. The operators should become the interior nodes and the operands the exterior nodes. Use a similar strategy used by the makeNode method in the Tree class to build your binary tree.
There should be a Polynomial class which implements the Comparable interface, and includes a method evaluate that returns the value of the polynomial for the supplied value.
The Polynomial class should also contain the following methods.
1. A constructor.
2. A class method named input that reads in a polynomial. The buffered reader for the file should be passed to this method as a parameter. The polynomials in the file will be stored as integer pairs that represent a coefficient and its corresponding exponent. For example, 5 3 4 1 8 0 represents the polynomial 5x3 + 4x + 8. They will always be written from the highest exponent to the lowest. Exponents with zero coefficients will be omitted.
3. A toString method that converts a polynomial to a string. The polynomial 5x3 + 4x + 8 should be converted to the following string "5x^3 + 4x + 8".
4. A method compareTo that compares two polynomials. The comparison should be similar to the Big-O comparison of methods. If the two polynomials have different highest order exponents the one with the highest exponent is the greatest. If their highest exponents are the same their coefficients are compared. If two polynomials have the same highest order exponent with the same coefficients the next highest exponent is examined. The following examples should help explain the ordering:
After the expression and polynomial have been input the expression should be evaluated and its value should be displayed.
Example of user prompts:
>>Enter prefix expression: + * 2.5 + P 7.4 6.3 8
>>Enter P: 5 3 4 1 8 0
>>Result = 5183.05
Example of how:
((2.5 * (P(7.4) + 6.3)) + 8)
where P (7.4) = 5(7.4)3 + 4(7.4) + 8
= 2026.12 + 29.6 + 8
= 2063.72
=((2.5 *(2063.72 + 6.3)) + 8)
=((2.5 *2070.02) + 8)
=(5175.05 + 8)