，。
Introduction
This consists of just one problem as a Part B. In addition to the requirements for the Java problems, you must observe the following requirements (for all homework submitted in this course):
- All programs should be literate, i.e., easily understandable by a human (say, your grader) and follow the Java Style Guidelines for CS112 posted on the class web site;
- All files for this homework should be submitted using WebSubmit, following the instructions on the class web site;
- You may not use data structure libraries such as ArrayList, since we are learning to write Java from the ground up and you must learn how these libraries are built; however, you are free to use (unless specifically directed otherwise) the basic libraries String, Character, Scanner, and Math; for this assignment, you may also use
Double.parseDouble(....);
- You may freely use code from the class web site, the textbook, or lecture (unless specifically directed otherwise) as long as you cite the source in your comments; but you may NEVER use code from the web or other students’ programs—this will be considered plagiarism and penalized accordingly.
Problem B.1: YAC (Yet Another Calculator)
This problem will be an exercise in hierarchical linked lists and in recursive evaluation of arithmetic expressions. There is not all that much coding to do (my solution added less than 50 lines of code to the template), but you will need to understand how to represent expressions using hierarchical or nested linked lists. As I explained in lecture, this is how Python and many other interpreted languages represent programs, and it is an important way to think about representing data and algorithms.
The primary data structure will be hierarchical linked lists, as described in lecture on Tuesday 10/25. As explained at that time on the board, an expression will consist of three different kinds of nodes, for operators (*, +, -, and /), positive numbers (doubles), and expressions (nested, fully-parenthesized expressions). For example, an infix expression such as
( ( 3.4 + 0.0 ) * ( 1.2 - 2.3 ) )
which can equivalently be represented in prefix form as
*( +( 3.4, 0.0 ), -( 1.2, 2.3 ) )
Representing Arithmetic Expressions by Hierarchical Linked Lists
There are three different kinds of nodes in such a hierarchical list, all represented by different configurations of Node objects:
1
2
3
4
5
6
7
8
|
private static class Node #123;
String op;
double num;
Node exp;
Node next;
..... constructors and toString() ......
#125;
|
Operator Nodes represent one of the four arithmetic operators *, +, -, or / and have an op field storing the operator as a String.
Note that the num field, a double, has to have some value, and since it is meaningless in this kind of node, we give it the default value 0.0; similarly, the exp field is not used, and is assigned null. The next field, as we show below, will point to null when the operator is pushed on the Ops stack and point to the two operands of the operator when it is part of an expression.
Expression Nodes are placeholders for expressions, and have default values for op and num, and a pointer to an operator node which starts a subexpression.
Therefore, it is easy to tell which kind of node is being represented:
- Operator nodes have a non-empty String in the op field, a 0.0 in the num field, and a null pointer in the exp field;
- Number nodes have an empty Stri䔠⡥䔠⥴⍥ㄠ㉮㍵㭭㰠⽦㸠㰨⁵⽬㹤㰬⼠㹣㱯㴮∰≮㹤††㭮㬠⁴㵸⁰㬼㬠⠠⤠㬠㰼⽬㹰㱲⽩㹯㱮㵥∠≮㸭⁵㭲㭥†䕥㵥 㭵㬾⡅⥡㭣㰠⽯㹥㱳⽯㹤㱥⽡㹹㰠†㵴∠≤㸠⁷㴭⡤䕩⥴㭥㱸⽴㹥㰠⽯㹷㰠⼠㹥㱸㵰∾∲㸠‽•⁴㩣㱡⽬㹵㱲⁶⽥㸭㱌⁴⽳㸢㰾㴠≅≳㹳††⁒㱩⽳㹨㰲 ⼼㹰㰾㵣∠≥㹳††㱤⽥㹤㰮⼠㹓㱴㴠≡≥㹦†⁹› ⁰㱩⽴㸯㱰 ⼼㹰㱲㵯≴≯㹴※††ⁱ⁵⁴※ⁱⁱ⁵⁵ⁱ⡵ ⁰⥥㱸⽰㹩㱯⽳㸠㱥㴊∼∊㸠†††‼‾†⁓⁴††㰼⼯㸊㰠†⼼㹬㱩ⁱ㵬≤∠㸫†⁸⁰⁰†㱤⽱㸦㱲⁵⽯㸻㰼㴾∍≁㹳†††䕥†⁴ †⁵㭮 ‼⡬⥮ⱳ㱩⽳㸠㱯⽮㸠㱯⁴㵤≥≮㹴†⁴†⁴⁷†††㰠⽮㸠㱰⽴㹩㱮†㵰≲≯㹮‼ ‾ ‼ ⁵‼⁷†㱨⽩㹥㱡⁁⼠㹳㱩†㵥∼∊㸼⁰‾‼‾′⁰㱥⽮㹴㱨⽥㹧㱩㵨≥≩㹧⁴†⁔†⁴⁺䕡㱮⽯㹦㱯⽷㹩㱮†㵴≯≤㹥††⁴⡥⁵⥣㱵⽲㹬㱹⁴⽯㸠㱳⁰㵯≮≰㸾 ‼′†‽•⁂⁵䑧䑡⡴⸭⥯⁴⁵⁈㱩⽳㹲㱯⁓⽴㹲㱩 㴼≰∠㹴⁰⁴††⁶†‼† 䕣†㱤⼠㹨㰠⁴⽵㹲㱮⼠㹬㱩㵮≳∠㹩†䅴⁶Ɱ†⁴䕥†⁈‶⁴㱵⽬㹴㰠†⽦㹯㱵㵩≣≲㹡⍴ㅯ㉲㕳㬮㰠⽙㹩㱬⽬㹳㱯⼠㹤ഠੴ††⁓㱴⽡㸠ൣ੬†⁷†⁵㱳⽥㹩൮ਠ⁈⁗†‰㰶⼻㸠൩ੳ㰠⽴㹲൳੩㱯⽮㸠൷੩㱴㈠㵣≯䕤ⵧ䠨䱨≷㹨䕩†䡴䱥㱣⽥㉩㹮ഠੴ㱨㸠⁰⁸㱯㸠⡴⥴㱥⼠㸠⁷⁶†ⱡ†⁴†⁵
⁴†Ɽ†⁴Ɱ††⁵⁹ ‾†㩰㱲⽤㹥ഠੴ㱨㵯≤∯㹣㱯⽤㸠഼㱯㹡൬ਨ†㰠㹤ਾ†⁔†㱥㹩൯੮††⁴㱨㵴≨≴㹨ਠ†⁴†㱥㹥㱤†㵲≴≡㸠ㅓ㱴⽲㹩㱮†⽡㸠㱨㵬∠≥㹤㈠㱬⽩㹵㱳⼠㹡㰠㵯≦∠㹴㍷㱯⼭㹫㱳⽴㹨㱯㴰∶∾㸍㐊㰼⽰㹹㱯⽯㹯㱫⁴㵧≯≭㸠㕦㱲⽯㸠㰰†⽹㹯㱵㵴≨≴㸠㙥㱶⽡㹥㱳⽥㸠㱥㴠≢≯㹲㝩㱮⽧㸠㱯⽡㹮㱤†㵴≡≮㹤㠠㱴⽨㹥㱲⽲㹳㰠⽯㹮൯ੴ†⁉†⁴㰠⽶㹩ൡੴ††⁴⁴†㱡㴬∠≩㹬൬ਠ⁴†㰠㹲㱡㴠≥∼㸯⠼†⥨⌠ㅯ㉰㍥㭲㱡⽴㹴㱡⼠㹡㱮⽸㹰㱲㴠≴≰㹥⁴†㱴⼠㹮㱥†⽰㹯㱩†㵬≬≡㹵†⁴†㱴⽯㹥㱭⽡㹲㱩†㵳≥≣㹯††⡬›‾⥧㱨⽬㸠㱰⽮㸢㰾㴊∼≥㸾 ††††‼⁴†††•㰢⼾㸠㰠†⼠㸠㰠㵡≮≳㹳‽••‾‾• ⁰†㱡⽮㸠㰯⽰㹡㱮㵮≥∯㹳⍰ㅡ㉮㔾㬼㱢⽲㹳㱰†⽣㹬㱡⽳㹬൩੮•‾‵‼ ⁰‾‼㱢⽲㸾഼ੳ⁰†㱳⼽㹩൮•‾‶‼㰯⽳㹢൲ਠ㰯⼾㸠ൣ੬㱡⽳㸽"line">7