1 % !TEX program = xelatex

     2 \documentclass{article}

     3 \usepackage{../style}

     4 \usepackage{../langs}

     5 \usepackage{disclaimer}

     6 \usepackage{tikz}

     7 \usepackage{pgf}

     8 \usepackage{pgfplots}

     9 \usepackage{stackengine}

    10 %% \usepackage{accents}

    11 \newcommand\barbelow[1]{\stackunder[1.2pt]{#1}{\raisebox{-4mm}{\boldmath$\uparrow$}}}

    12 

    13 

    14 \begin{document}

    15 

    16 % BF IDE

    17 % https://www.microsoft.com/en-us/p/brainf-ck/9nblgggzhvq5

    18   

    19 \section*{Preliminary Part 8 (Scala, 3 Marks)}

    20 

    21 \mbox{}\hfill\textit{``[Google’s MapReduce] abstraction is inspired by the}\\

    22 \mbox{}\hfill\textit{map and reduce primitives present in Lisp and many}\\

    23 \mbox{}\hfill\textit{other functional languages.''}\smallskip\\

    24 \mbox{}\hfill\textit{ --- Dean and Ghemawat, who designed this concept at Google}

    25 \bigskip

    26 

    27 \IMPORTANT{This part is about the shunting yard algorithm by Dijkstra.

    28   The preliminary part is due on \cwEIGHT{} at 5pm and worth 3\%.}

    29 

    30 \noindent

    31 Also note that the running time of each part will be restricted to a

    32 maximum of 30 seconds on my laptop.  

    33 

    34 \DISCLAIMER{}

    35 

    36 \subsection*{Reference Implementation}

    37 

    38 This Scala assignment comes with two reference implementations in

    39 form of \texttt{jar}-files. This allows

    40 you to run any test cases on your own computer. For example you can

    41 call Scala on the command line with the option \texttt{-cp

    42   postfix.jar} and then query any function from the

    43 \texttt{postfix.scala} file (similarly for file \texttt{postfix2.scala}). As

    44 usual you have to prefix the calls with \texttt{CW8a} and

    45 \texttt{CW8b}, respectively.

    46 

    47 

    48 \begin{lstlisting}[xleftmargin=1mm,numbers=none,basicstyle=\ttfamily\small]

    49 $ scala -cp postfix.jar

    50 

    51 scala> CW8a.syard(CW8a.split("( 5 + 7 ) * 2"))

    52 val res0: CW8a.Toks = List(5, 7, +, 2, *)

    53 \end{lstlisting}%$

    54 

    55 

    56 \subsection*{Preliminary Part (3 Marks, files postfix.scala, postfix2.scala)}

    57 

    58 The \emph{Shunting Yard Algorithm} has been developed by Edsger Dijkstra,

    59 an influential computer scientist who developed many well-known

    60 algorithms. This algorithm transforms the usual infix notation of

    61 arithmetic expressions into the postfix notation, sometimes also

    62 called reverse Polish notation.

    63 

    64 Why on Earth do people use the postfix notation? It is much more

    65 convenient to work with the usual infix notation for arithmetic

    66 expressions. Most modern pocket calculators (as opposed to the ones used 20

    67 years ago) understand infix notation. So why on Earth? \ldots{}Well,

    68 many computers under the hood, even nowadays, use postfix notation

    69 extensively. For example if you give to the Java compiler the

    70 expression $1 + ((2 * 3) + (4 - 3))$, it will generate the Java Byte

    71 code

    72 

    73 \begin{lstlisting}[language=JVMIS,numbers=none]

    74 ldc 1 

    75 ldc 2 

    76 ldc 3 

    77 imul 

    78 ldc 4 

    79 ldc 3 

    80 isub 

    81 iadd 

    82 iadd

    83 \end{lstlisting}

    84 

    85 \noindent

    86 where the command \texttt{ldc} loads a constant onto the stack, and \texttt{imul},

    87 \texttt{isub} and \texttt{iadd} are commands acting on the stack. Clearly this

    88 is the arithmetic expression in postfix notation.\bigskip

    89 

    90 \noindent

    91 The shunting yard algorithm processes an input token list using an

    92 operator stack and an output list. The input consists of numbers,

    93 operators ($+$, $-$, $*$, $/$) and parentheses, and for the purpose of

    94 the assignment we assume the input is always a well-formed expression

    95 in infix notation.  The calculation in the shunting yard algorithm uses

    96 information about the

    97 precedences of the operators (given in the template file). The

    98 algorithm processes the input token list as follows:

    99 

   100 \begin{itemize}

   101 \item If there is a number as input token, then this token is

   102   transferred directly to the output list. Then the rest of the input is

   103   processed.

   104 \item If there is an operator as input token, then you need to check

   105   what is on top of the operator stack. If there are operators with

   106   a higher or equal precedence, these operators are first popped off

   107   from the stack and moved to the output list. Then the operator from the input

   108   is pushed onto the stack and the rest of the input is processed.

   109 \item If the input is a left-parenthesis, you push it on to the stack

   110   and continue processing the input.

   111 \item If the input is a right-parenthesis, then you pop off all operators

   112   from the stack to the output list until you reach the left-parenthesis.

   113   Then you discharge the $($ and $)$ from the input and stack, and continue

   114   processing the input list.

   115 \item If the input is empty, then you move all remaining operators

   116   from the stack to the output list.  

   117 \end{itemize}  

   118 

   119 \subsubsection*{Tasks (file postfix.scala)}

   120 

   121 \begin{itemize}

   122 \item[(1)] Implement the shunting yard algorithm described above. The

   123   function, called \texttt{syard}, takes a list of tokens as first

   124   argument. The second and third arguments are the stack and output

   125   list represented as Scala lists. The most convenient way to

   126   implement this algorithm is to analyse what the input list, stack

   127   and output list look like in each step using pattern-matching. The

   128   algorithm transforms for example the input

   129 

   130   \[

   131   \texttt{List(3, +, 4, *, (, 2, -, 1, ))}

   132   \]

   133 

   134   into the postfix output

   135 

   136   \[

   137   \texttt{List(3, 4, 2, 1, -, *, +)}

   138   \]  

   139   

   140   You can assume the input list is always a  list representing

   141   a well-formed infix arithmetic expression.\hfill[1 Mark]

   142 

   143 \item[(2)] Implement a compute function that takes a postfix expression

   144   as argument and evaluates it generating an integer as result. It uses a

   145   stack to evaluate the postfix expression. The operators $+$, $-$, $*$

   146   are as usual; $/$ is division on integers, for example $7 / 3 = 2$.

   147   \hfill[1 Mark]

   148 \end{itemize}

   149 

   150 \subsubsection*{Task (file postfix2.scala)}

   151 

   152 \begin{itemize}

   153 \item[(3/4)] Extend the code in (1) and (2) to include the power

   154   operator.  This requires proper account of associativity of

   155   the operators. The power operator is right-associative, whereas the

   156   other operators are left-associative.  Left-associative operators

   157   are popped off if the precedence is bigger or equal, while

   158   right-associative operators are only popped off if the precedence is

   159   bigger.\hfill[1 Marks]

   160 \end{itemize}

   161 

   162 \end{document}

   163 

   164 

   165 %%% Local Variables: 

   166 %%% mode: latex

   167 %%% TeX-master: t

   168 %%% End: