diff -r 017f621f5835 -r 3ffe978a5664 cws/pre_cw03.tex --- a/cws/pre_cw03.tex Thu Nov 04 12:20:12 2021 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,181 +0,0 @@ -% !TEX program = xelatex -\documentclass{article} -\usepackage{../style} -\usepackage{../langs} -\usepackage{disclaimer} -\usepackage{tikz} -\usepackage{pgf} -\usepackage{pgfplots} -\usepackage{stackengine} -%% \usepackage{accents} -\newcommand\barbelow[1]{\stackunder[1.2pt]{#1}{\raisebox{-4mm}{\boldmath$\uparrow$}}} -\usepackage{ulem} - -\begin{document} - -% BF IDE -% https://www.microsoft.com/en-us/p/brainf-ck/9nblgggzhvq5 - -\section*{Preliminary Part 3 (Scala, 3 Marks)} - -\mbox{}\hfill\textit{``[Google’s MapReduce] abstraction is inspired by the}\\ -\mbox{}\hfill\textit{map and reduce primitives present in Lisp and many}\\ -\mbox{}\hfill\textit{other functional languages.''}\smallskip\\ -\mbox{}\hfill\textit{ --- Dean and Ghemawat, who designed this concept at Google} -\bigskip - -\IMPORTANT{This part is about the shunting yard algorithm by Dijkstra. - The preliminary part is due on \sout{\cwEIGHT{}} \textcolor{red}{11 December} - at 5pm and worth 3\%. - Any 1\% you achieve in the preliminary part counts as your - ``weekly engagement''.} - -\noindent -Also note that the running time of each part will be restricted to a -maximum of 30 seconds on my laptop. - -\DISCLAIMER{} - -\subsection*{Reference Implementation} - -This Scala assignment comes with two reference implementations in -form of \texttt{jar}-files. This allows -you to run any test cases on your own computer. For example you can -call Scala on the command line with the option \texttt{-cp - postfix.jar} and then query any function from the -\texttt{postfix.scala} file (similarly for file \texttt{postfix2.scala}). As -usual you have to prefix the calls with \texttt{CW8a} and -\texttt{CW8b}, respectively. - - -\begin{lstlisting}[xleftmargin=1mm,numbers=none,basicstyle=\ttfamily\small] -$ scala -cp postfix.jar - -scala> CW8a.syard(CW8a.split("( 5 + 7 ) * 2")) -val res0: CW8a.Toks = List(5, 7, +, 2, *) -\end{lstlisting}%$ - - -\subsection*{Hints} - -\noindent -\textbf{For the Preliminary Part:} useful operations for determining -whether a string is a number are \texttt{.forall} and \texttt{.isDigit}. -One way to calculate the the power operation is to use \texttt{.pow} -on \texttt{BigInt}s, like \texttt{BigInt(n).pow(m).toInt}. -\bigskip - - -\subsection*{Preliminary Part (3 Marks, files postfix.scala, postfix2.scala)} - -The \emph{Shunting Yard Algorithm} has been developed by Edsger Dijkstra, -an influential 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 -convenient to work with the usual infix notation for arithmetic -expressions. Most modern pocket calculators (as opposed to the ones used 20 -years ago) understand infix notation. So why on Earth? \ldots{}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 - -\begin{lstlisting}[language=JVMIS,numbers=none] -ldc 1 -ldc 2 -ldc 3 -imul -ldc 4 -ldc 3 -isub -iadd -iadd -\end{lstlisting} - -\noindent -where the command \texttt{ldc} loads a constant onto the stack, and \texttt{imul}, -\texttt{isub} and \texttt{iadd} are commands acting on the stack. Clearly this -is the arithmetic expression in postfix notation.\bigskip - -\noindent -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 input is always a well-formed expression -in infix notation. The calculation in the shunting yard algorithm uses -information about the -precedences of the operators (given in the template file). The -algorithm processes the input token list as follows: - -\begin{itemize} -\item 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. -\item 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. -\item If the input is a left-parenthesis, you push it on to the stack - and continue processing the input. -\item 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. -\item If the input is empty, then you move all remaining operators - from the stack to the output list. -\end{itemize} - -\subsubsection*{Tasks (file postfix.scala)} - -\begin{itemize} -\item[(1)] Implement the shunting yard algorithm described above. The - function, called \texttt{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 - - \[ - \texttt{List(3, +, 4, *, (, 2, -, 1, ))} - \] - - into the postfix output - - \[ - \texttt{List(3, 4, 2, 1, -, *, +)} - \] - - You can assume the input list is always a list representing - a well-formed infix arithmetic expression.\hfill[1 Mark] - -\item[(2)] Implement a compute function that takes a postfix expression - as argument 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$. - \hfill[1 Mark] -\end{itemize} - -\subsubsection*{Task (file postfix2.scala)} - -\begin{itemize} -\item[(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.\hfill[1 Marks] -\end{itemize} - -\end{document} - - -%%% Local Variables: -%%% mode: latex -%%% TeX-master: t -%%% End: