Important:(No Late Assignment Is Accepted…there please be careful about the time line)
Objectives:
To gain experience with stacks and lists.
Documentation:
1. Explain the purpose of the program as detail as possible –13%.
2. Develop a solution for the problem and mention algorithms to be used –16%
3. List data structures to be used in solution. –5%.
4. Give a description of how to use the program and expected input/output –5%
5. Explain the purpose of each class you develop in the program. –5%.
Programming:
1. For each method, give the pre and post conditions and invariant, if any –10%
2. Program executionaccording to the requirements given36%
3. Naming of program as required5%
4. Print out of source code5%
Description of Program
Youare to write a program name expressionTree.javathat evaluates an infix expression entered by the user. The expression may contain the following tokens:
(1) Integer constants (a series of decimal digits).
(2) One alphabetic character – “x” (representing a value to be supplied later).
(3) Binary operators (+, -, *, / and % (modulo)).
(4) Unary operators + & –
(5) Parentheses
You will parse the input expression creating an expression tree with the tokens, then use the postOrdertree traversal algorithm to extract a postfix expression from the tree. Display this postfixexpression(String).You will supply this postfix expression (string) to the calculator engine (a function that you will write) to produce a result.
Spaces between tokens are allowed but not required. The program will repeatedly prompt the user for the value of x, displaying the value of the expression each time. When the user enters the letter q instead of a number, the program terminates.
The following example illustrates the behavior of the program (user input is in bold):
Enter infix expression:(x + 125) * (x – 2) / 4
Converted expression: x 125 + x 2 – * 4 /
Enter value of x:5
Answer to expression: 97
Enter value of x:7
Answer to expression: 165
Enter value of x:q
If the infix expression contains an error of any kind, the program must display the message Error in expression (with an optional explanation) and then terminate. The following examples illustrate various types of errors:
Enter infix expression:1 2 +
Error in expression!! No operator between operands. Also last token must be an operand.
Enter infix expression:10.4
Error in expression!! Cannot accept floating point numbers.
Enter infix expression:1 ( +2)
Error in expression!! No operator between operand and left parentheses.
Enter infix expression:5 – (x – 2))
Error in expression!! No matching left parentheses for a right parentheses.
Enter infix expression:1 ** 2
Error in expression!! The * operator cannot be preceded by a * operator.
The output of your program must match the format illustrated in this example.
Here are some other additional requirements for this program:
(1) You must use stack objects and list(or Linked List) during the translation from infix to the parse tree and during the evaluation of the postfix expression.
(2) Operators must have the correct precedence and associativity.
What to turn in:
….. containing expressionTree.java, expressionTree.class,and parse.java and parse.class (if you wrote a separate class for parsing)
Hints:
1. Do the program in stages. First, get the algorithm to convert from infix to a parse tree for binary operators and parentheses.
2. Next, implement the post order algorithm to produce the postfix expression then evaluate the postfix expression.
3. Finally, add code to check the infix expression for errors.
4. Use the examples from the hand out as a starting point for the program, but keep in mind that this code doesn’t handle associativity properly.
5. Use an underscore ‘_’ to represent the ‘-‘unary operator when parsing the input expression. The ‘+’ unary operator can be ignored.
6. To detect errors in the infix expression, you will need to check for several situations:
o A binary operator is preceded by an operator
o An operand is preceded by an operand.
o An illegal character is encountered (such as a period).
o The last token in the expression is not an operand.
o There is no left parentheses anywhere in the stack when a right parentheses is encountered.
o The stack contains a left parenthesis when the expression ends.
7. Use a string to store the postfix expression. Use a stack of operators and a stack of a list of nodes during the translation from infix to the parse tree.
