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
