scala代写 - Preliminary Part 3 (Scala, 3 Marks)
时间:2020-12-02
Important
• This part is about the shunting yard algorithm by Dijkstra. The prelim‑
inary part is due on 4 December at 5pm and worth 3%. Any 1% you
achieve in the preliminary part counts as your “weekly engagement”.
• Make sure the files you submit can be processed by just calling
scala <> on the commandline.1 Use the template files
provided and do not make any changes to arguments of functions or to
any types. You are free to implement any auxiliary function you might
need.
• Do not leave any test cases running in your code because this might
slow down your program! Comment out test cases before submission,
otherwise you might hit a time‑out.
• Do not use any mutable data structures in your submissions! They are
not needed. This means you cannot create new Arrays or ListBuffers,
for example.
• Do not use return in your code! It has a different meaning in Scala than
in Java. It changes the meaning of your program, and you should never
use it.
• Do not use var! This declares a mutable variable. Only use val! • Do not use any parallel collections! No .par therefore! Our testing and
marking infrastructure is not set up for it.
Also note that the running time of each part will be restricted to a maximum of
30 seconds on my laptop.
Disclaimer
It should be understood that the work you submit represents your own effort!
You have not copied from anyone else. An exception is the Scala code I showed
during the lectures or uploaded to KEATS, which you can freely use.
1All major OSes, including Windows, have a commandline. So there is no good reason to not
download Scala, install it and run it on your own computer. Just do it!
1
Reference Implementation
This Scala assignment comes with two reference implementations in form of
jar‑files. This allows you to run any test cases on your own computer. For ex‑
ample you can call Scala on the command line with the option ‐cp postfix.jar
and then query any function from the postfix.scala file (similarly for file
postfix2.scala). As usual you have to prefix the calls with CW8a and CW8b,
respectively.
$ scala ‐cp postfix.jar
scala> CW8a.syard(CW8a.split("( 5 + 7 ) * 2"))
val res0: CW8a.Toks = List(5, 7, +, 2, *)
Preliminary Part (3 Marks, files postfix.scala, postfix2.scala)
The Shunting Yard Algorithm has been developed by Edsger Dijkstra, an influ‑
ential computer scientist who developed many well‑known algorithms. This
algorithm transforms the usual infix notation of arithmetic expressions into the
postfix notation, sometimes also called reverse Polish notation.
Why on Earth do people use the postfix notation? It is much more conve‑
nient to work with the usual infix notation for arithmetic expressions. Most
modern pocket calculators (as opposed to the ones used 20 years ago) under‑
stand infix notation. So why on Earth? …Well, many computers under the
hood, even nowadays, use postfix notation extensively. For example if you
give to the Java compiler the expression 1 + ((2 ∗ 3) + (4 3)), it will generate
the Java Byte code
ldc 1
ldc 2
ldc 3
imul
ldc 4
ldc 3
isub
iadd
iadd
where the command ldc loads a constant onto the stack, and imul, isub and
iadd are commands acting on the stack. Clearly this is the arithmetic expression
in postfix notation.
The shunting yard algorithm processes an input token list using an operator
stack and an output list. The input consists of numbers, operators (+, , ∗, /) and parentheses, and for the purpose of the assignment we assume the in‑
put is always a well‑formed expression in infix notation. The calculation in the
2
shunting yard algorithm uses information about the precedences of the opera‑
tors (given in the template file). The algorithm processes the input token list as
follows:
• If there is a number as input token, then this token is transferred directly
to the output list. Then the rest of the input is processed.
• If there is an operator as input token, then you need to check what is
on top of the operator stack. If there are operators with a higher or equal
precedence, these operators are first popped off from the stack and moved
to the output list. Then the operator from the input is pushed onto the
stack and the rest of the input is processed.
• If the input is a left‑parenthesis, you push it on to the stack and continue
processing the input.
• If the input is a right‑parenthesis, then you pop off all operators from
the stack to the output list until you reach the left‑parenthesis. Then you
discharge the ( and ) from the input and stack, and continue processing
the input list.
• If the input is empty, then you move all remaining operators from the
stack to the output list.
Tasks (file postfix.scala)
(1) Implement the shunting yard algorithm described above. The function,
called syard, takes a list of tokens as first argument. The second and
third arguments are the stack and output list represented as Scala lists.
The most convenient way to implement this algorithm is to analyse what
the input list, stack and output list look like in each step using pattern‑
matching. The algorithm transforms for example the input
List(3, +, 4, *, (, 2, ‐, 1, ))
into the postfix output
List(3, 4, 2, 1, ‐, *, +)
You can assume the input list is always a list representing a well‑formed
infix arithmetic expression. [1 Mark]
(2) Implement a compute function that takes a postfix expression as argu‑
ment and evaluates it generating an integer as result. It uses a stack to
evaluate the postfix expression. The operators +, , ∗ are as usual; / is
division on integers, for example 7/3 = 2. [1 Mark]
3
Task (file postfix2.scala)
(3/4) Extend the code in (1) and (2) to include the power operator. This requires
proper account of associativity of the operators. The power operator is
right‑associative, whereas the other operators are left‑associative. Left‑
associative operators are popped off if the precedence is bigger or equal,
while right‑associative operators are only popped off if the precedence is
bigger. [1 Marks]