All of the assignment submissions may be classified into the following
categories.

(1) REPEATED REFINEMENT: 
(Most popular approach -- 7 submissions in all)

Repeatedly refine the expression by finding "subexpressions" of the
form <op num1 num2> and replacing this subexpression by its value.  If
the final list, obtained at the point when this refinement is no
longer possible, is of size 1 and is a number, then return the number
as the final value; otherwise, the input expression is invalid.

One problem with this approach is that you may be repeatedly scanning
large portions of the expression to search for the subexpressions of
the desired form.  The worst-case running time could be proportional
to quadratic in the length of the expression; that is, proportional to
n^2, where n is the length of the expression.  (I will let you folks
think about this.)

(2) PARSING:

Parse the expression according to the grammar given and then evaluate
it.  That is, if the expression is a number, simply return the number.
Otherwise, the first element is an operator.  In this case, find the
first subexpression by a recursive call; this recursive call should
return the first subexpression and the remainder of the expression.
The remainder of the list will form the second subexpression.

This strategy, while somewhat difficult to code, will give linear time
program; that is, the worst-case running time of the program is
proportional to n, where n is the length of the expression.  Whether,
multiple passes on the expression are made depends on the particular
implementation of the parsing.  Three different subapproaches were
suggested.

(2a) Compute the parse tree. (4 submissions)

The parse tree approach constructs the tree using the above parsing
strategy.  The parse tree encodes the order of operations.  The tree
is passed as input to an evaluator which computes the value by a
simple recursive procedure for evaluating the parse tree.  So, in a
sense, two passes are made on the expression.  First, when
constructing the parse tree.  Second, when computing the value from
the parse tree.

(2b) Directly evaluate the expression. (2 submissions)

Another option is to directly evaluate the expression while parsing
it.  This would only make one pass over the expression.

(2c) Compute the parse tree according to operator/operand counts. (2
submissions)

The parse tree can also constructed by looking at the count of
operands and operations.  Note that in a valid expression, the number
of operands is 1 more than the number of operators.  So one way to
parse the expression is the following.  The base case is if it is a
number.  Otherwise, the first element is an operator.  Now, we need to
extract the first subexpression from the remainder.  We can scan the
list from the next element, start counting the operands and operators,
and stop at the first point when the number of operands is 1 plus the
number of operators.  The portion we have scanned gives us the first
subexpression and the remainder the second subexpression.  We can thus
construct the root node of the parse tree with two children, one
corresponding to each subexpression.  We still need to check for the
validity of the two subexpressions, which we can do by a recursive
call.

This strategy also makes two passes over the expression.  First, to
count the number of operators and operands, to determine where a
subexpression ends.  The second, to calculate the value of the
subexpression.

(3) THE ACCUMULATOR TECHNIQUE:

The accumulator technique is, perhaps, the easiest of the different
approaches for this problem.  The idea is to maintain a stack into
which elements of the expression are put.  Whenever you see a
3-element term of the form <op num1 num2> you replace it by the value
obtained by applying op on num1 and num2.  The idea is similar to (1),
but more efficient, since you scan the expression only once.  So the
running-time of this approach is proportional to n, where n is the
length of the expression.

There are two ways in which you can scan the expression.

(3a) Scan the expression in forward direction. (3 submissions)

Keep putting elements into the stack.  If you ever see the top 3
elements of the stack being <op num1 num2> in that order, where num2
is the topmost element of the stack, remove the 3 elements from the
stack and replace it by the value of the relevant calculation.  Repeat
until you have scanned all of the expression.  If at the end, you have
one number on the stack, return that as the answer.  Otherwise, the
given expression is invalid.

(3b) Scan the expression in reverse direction. (2 submissions)

Reverse the given expression.  Keep putting the elements into the
stack.  Whenever you insert an operator, check if the top three
elements of the stack are <op num1 num2> in that order, where op is
the topmost element of the stack.  If so, remove the 3 elements and
replace by the value.  Repeat until you have scanned all of the
expression.  If at the end, you have one number on the stack, return
that as the answer.  Otherwise, the given expression is invalid.