equal
deleted
inserted
replaced
62 \bigskip |
62 \bigskip |
63 |
63 |
64 |
64 |
65 \subsection*{Core Part (3 Marks, files postfix.scala, postfix2.scala)} |
65 \subsection*{Core Part (3 Marks, files postfix.scala, postfix2.scala)} |
66 |
66 |
67 The \emph{Shunting Yard Algorithm} has been developed by Edsger Dijkstra, |
67 The \textit{Shunting Yard Algorithm} has been developed by Edsger Dijkstra, |
68 an influential computer scientist who developed many well-known |
68 an influential computer scientist who developed many well-known |
69 algorithms. This algorithm transforms the usual infix notation of |
69 algorithms. This algorithm transforms the usual infix notation of |
70 arithmetic expressions into the postfix notation, sometimes also |
70 arithmetic expressions into the postfix notation, sometimes also |
71 called reverse Polish notation. |
71 called \textit{Reverse Polish Notation}. |
72 |
72 |
73 Why on Earth do people use the postfix notation? It is much more |
73 Why on Earth do people use the postfix notation? It is much more |
74 convenient to work with the usual infix notation for arithmetic |
74 convenient to work with the usual infix notation for arithmetic |
75 expressions. Most modern pocket calculators (as opposed to the ones used 20 |
75 expressions. Most modern pocket calculators (as opposed to the ones used 20 |
76 years ago) understand infix notation. So why on Earth? \ldots{}Well, |
76 years ago) understand infix notation. So why on Earth? \ldots{}Well, |
90 iadd |
90 iadd |
91 iadd |
91 iadd |
92 \end{lstlisting} |
92 \end{lstlisting} |
93 |
93 |
94 \noindent |
94 \noindent |
95 where the command \texttt{ldc} loads a constant onto the stack, and \texttt{imul}, |
95 where the command \texttt{ldc} loads a number onto the stack, and \texttt{imul}, |
96 \texttt{isub} and \texttt{iadd} are commands acting on the stack. Clearly this |
96 \texttt{isub} and \texttt{iadd} perform arithmetic operations on the stack. Clearly, this |
97 is the arithmetic expression in postfix notation.\bigskip |
97 is the arithmetic expression from above but in postfix notation.\bigskip |
98 |
98 |
99 \noindent |
99 \noindent |
100 The shunting yard algorithm processes an input token list using an |
100 The shunting yard algorithm processes an input token list using an |
101 operator stack and an output list. The input consists of numbers, |
101 operator stack and an output list. The input consists of numbers, |
102 operators ($+$, $-$, $*$, $/$) and parentheses, and for the purpose of |
102 operators ($+$, $-$, $*$, $/$) and parentheses, and for the purpose of |
121 from the stack to the output list until you reach the left-parenthesis. |
121 from the stack to the output list until you reach the left-parenthesis. |
122 Then you discharge the $($ and $)$ from the input and stack, and continue |
122 Then you discharge the $($ and $)$ from the input and stack, and continue |
123 processing the input list. |
123 processing the input list. |
124 \item If the input is empty, then you move all remaining operators |
124 \item If the input is empty, then you move all remaining operators |
125 from the stack to the output list. |
125 from the stack to the output list. |
126 \end{itemize} |
126 \end{itemize} |
|
127 |
|
128 \noindent |
|
129 BTW, the rules above are written ``If\ldots'', but this is because English does not |
|
130 include very sophisticated pattern matching. But clearly the rules above should be implemented |
|
131 in Scala using pattern matching. |
|
132 |
127 |
133 |
128 \subsubsection*{Tasks (file postfix.scala)} |
134 \subsubsection*{Tasks (file postfix.scala)} |
129 |
135 |
130 \begin{itemize} |
136 \begin{itemize} |
131 \item[(1)] Implement the shunting yard algorithm described above. The |
137 \item[(1)] Implement the shunting yard algorithm described above. The |