Expression interpreter. Develop a TOY implementation of Dijkstra’s algorithm (Program 4.3.5), omitting the square root function. Assume that the input expression is on standard input, using the convention that all operands are nonnegative 15-bit unsigned numbers, and use negative numbers to encode operators and delimiters: 8001 for +, 8002 for -, 8003 for *, 8004 for /, 8005 for (, and 8006 for ). Use your stack implementation from Exercise 6.3.25 and the multiplication implementation from Exercise 6.3.35.
Exercise 6.3.35
Efficient multiplication. Implement the algorithm that you learned in grade school to multiply two integers. Specifically, let b
i
denote the ith bit of b, so that
Now, to compute a × b, use the distributive law:
Naively, this appears to reduce the problem of performing one multiplication to 32 multiplications, two for each of the 16 terms. Fortunately, each of these 32 multi plications is of a very special type, because a × 2i is the same as left-shifting a by i bits. Since bi is either 0 or 1, the ith term is either a <>
Exercise 6.3.25
Develop a pair of TOY functions that implement a pushdown stack, passing the values to push and pop in R[B] and the address of the stack in R[A].
Program 4.3.5