% !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$}}}

\begin{document}

% BF IDE

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

\section*{Preliminary Part 8 (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 \cwEIGHT{} at 5pm and worth 3\%.}

\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*{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: