Introduction
这次需要代写的作业是用树来实现Polish Notation，没什么难度。
Prefix to infix based on tree data structure
Getting started
Create a directory for this assignment inside your SVN file system. Remember to commit your work early and often.
Important Notice
This assignment will only be marked by the testing script on websubmission (because our tutors’ contracts end before the deadline). There will be six test cases (1 mark each). The total mark is six as usual. You don’t have to write a design, because the testing script won’t be able to understand it anyway. (But feel free to write one for your own benefit.) The testing script doesn’t care about your code style either, so feel free to use variable names like aa, bb, cc, dd (I know some of you love these kinds of names – well, jk, please don’t).
Problem Description
Polish notation, also known as Polish prefix notation or simply prefix notation, is a form of notation for logic, arithmetic, and algebra. Its distinguishing feature is that it places operators to the left of their operands. (Many Lisp family programming languages require prefix notation, including the popular language Clojure.)
The expression for adding the numbers 1 and 2 is, in prefix notation, written “+ 1 2” rather than “1 + 2”. In more complex expressions, the operators still precede their operands, but the operands may themselves be nontrivial expressions including operators of their own. For instance, the expression that would be written in conventional infix notation as
(5 + 6) * 7
can be written in prefix as
* (+ 5 6) 7
You only need to care about binary operators: + - * and /
Also, you only need to care about operands that are from 0 to 9 (single digit).
For binary operators, prefix representation is unambiguous, and bracketing the prefix expression is un-necessary. As such, the previous expression can be further simplified to
* + 5 6 7
The processing of the product is deferred until its two operands are available (i.e., 5 plus 6, then multiplies the result with 7). As with any notation, the innermost expressions are evaluated first, but in prefix notation this “innermost-ness” is conveyed by order rather than bracketing.
You are asked to create a class that converts prefix expressions to infix expressions. You are asked to use a tree data structure to achieve this task. (Hint: use a binary tree, use the leaf nodes to store the operands and use the non-leaf nodes to store the operators.)
Create a main function that takes in one line. The line contains a list of operators and operands separated by spaces. The input doesn’t contain parenthesis. An operator is a character from +, -, *, and /. An operand is an integer from 0 to 9. You are asked to determine whether this line describes a valid prefix expression.
If so, output its infix form. Otherwise, output “Error”. (Division by zero is considered error.)
When you output the infix form, the output format should follow two rules
- Put parenthesis around all sub-expressions even if it is not necessary, but don’t put parenthesis around just numbers and don’t put parenthesis around the whole expression.
- 5 + 6 is valid
- (5) + 6 is not valid
- 5 + 6 is valid
- (5 + 6) is not valid
- 5 + (6 * 7) is valid
- 5 + 6 * 7 is not valid
- For every operator, put one space on each side, and no spaces elsewhere.
- 5 + (6 * 7) is valid
- 5 + 6 is valid
- 5 is valid
- 5 + 6 is not valid
- 5 + ( 6 * 7 ) is not valid
Sample input: * - 5 6 7
Sample output: (5 - 6) * 7
Sample input: * 5
Sample output: Error
Sample input: * 5 6 7
Sample output: Error
Sample input: + * - 5 6 7 3
Sample output: ((5 - 6) * 7) + 3
Sample input: / + * - 5 6 7 3 9
Sample output: (((5 - 6) * 7) + 3) / 9
Sample input: / + * - 5 6 7 3 0
Sample output: Error