Background
The arithmetic expressions considered in this project consist of non-negative integers, operators "+", "-", and "*", and parentheses "(" and ")". Arithmetic expressions are usually written using the infix notation, in which operators appear between the two operands on which they act (e.g., "2 + 2"). The evaluation of expressions in infix notation is done according to the standard order of operations: multiplications must be done first, from left to right, then all additions and subtractions, again from left to right. Parentheses can be used to change the order in which operations must be performed, e.g., the expression inside the innermost parentheses must be evaluated first, etc.Since each of the considered operators takes exactly two operands, such an arithmetic expression can be represented as a proper binary tree whose internal nodes are associated with the expression's operators and whose leaves are associated with non-negative integers. This project requires you to write a program that reads a fully parenthesized arithmetic expression written in infix notation, constructs the corresponding binary tree, and then uses the tree to evaluate it and print the expression in postfix notation. A fully parenthesized infix expression is one where all operands are surrounded by either one parenthesis and one operator, or two parentheses. Recall that the postfix notation is an unambiguous way of writing an expression in which the operands precede the operator, and parentheses are not required. For example, the infix expression "( 3 * ( 4 + 7 ) )" would be written in postfix notation as "3 4 7 + *"
Implementation requirements
You must implement and use your own binary tree class, and must implement at least one of the methods operating on the expression tree recursively. If needed, generic implementations provided by the Java collections framework can be used for other data structures (e.g., stacks).Program Input
Your program should read from the standard input one line containing a fully parenthesized infix expression, with tokens (integers, operators, and parentheses) separated by spaces. You may assume that the expression is well-formed.Program Output
The program should print two lines (both terminated with newline characters). The first line should contain the expression in postfix notation, with the tokens separated by single spaces, and no leading or trailing spaces. The second line should contain a single integer, corresponding to the value to which the expression evaluatesSample Output
Comments
Post a Comment