Data Structure and Algorithms

Question 1
Implement an array-based abstract data type ‘stack’ specified in class and do the following:

Write a procedure called read_and_evaluate_expression that reads in and evaluates a postfix expression (defined below) and writes out its value. (JAVA)
Your procedure must follow the algorithm sketched below, and it must use your implementation of abstract `stacks’. But the procedure should not depend on the details of your particular implementation -the procedure should depend only on the specification of abstract `stacks’ and therefore should work with any implementation of the specification (The TAs might check this by using their own stack implementation instead of yours).
The main program is a loop that calls read_and_evaluate_expression repeatedly. After evaluating an expression, it should ask the user if he want to quit (YES) or not (NO, to continue to evaluate a new expression).
3. Postfix Expressions
A postfix expression has the form X1 X2 X3 … Xn where each of the Xi is either a single digit (0…9) or one of the following binary operators: +, -, *, / (the operator / means integer division).
We adopt the convention that a postfix expression fits entirely on 1 line of input. In other words, the newline character, written ‘n’ in Java, indicates the end of the expression.
Should you find it convenient, you may also assume that X1 is the first character on the line, and that each Xi is separated from the next by exactly one space (i.e. ‘ ‘ in Java).
The expression is postfix because an operator is written after its two operands. For example, the normal (infix) expression 2+3 would be written 2 3 + in postfix. Postfix has the advantage that parentheses are never needed. In infix, one expression (e.g. 2+3*4) can have several possible meanings (e.g. (2+3) *4 and 2+(3*4)) and parentheses (or precedence conventions) are needed in order to distinguish among the possible meanings. In postfix, each expression has a unique meaning. For example, (2+3) *4 would be 2 3 + 4 * in postfix, whereas 2+(3*4) would be 2 3 4 * +.

4. Algorithm for evaluating postfix expressions (Sketch)
There is one stack for holding operands, called NumStk, which is initially empty.
● Read in the next digit or operator.
● Whenever you read a digit, push it onto the NumStk stack.
● When you read in an operator – let’s call it op – since it is a binary operator, it requires two arguments:
❍ Remove the first two numbers from NumStk; call the first one removed R and the second one L.
❍ Evaluate L op R and push the result onto NumStk.
● Ignore any blank space. If in fact we find a newline character, then we have reached the end of the expression. It should now be fully evaluated, and the resulting value must be on top of numbers. We write it out and return.

Example: input line is 2 3 4 * + 5 ¬
● read ‘2’, push it onto NumStk.
● read following space.
● read ‘3’, push it onto NumStk.
● read following space.
● read ‘4’, push it onto NumStk.
● read following space.
● read ‘*’. Pop NumStk: R=4. Pop NumStk: L=3. L op R = 3 * 4 evaluates to 12. Push 12 onto NumStk.
● read following space.
● read ‘+’. Pop NumStk: R=12. Pop NumStk: L=2. L op R = 2 + 12 evaluates to 14. Push 14 onto NumStk.
● read following space.
● read ‘5’. Push it onto NumStk.
● read following space.
● read ‘-‘. Pop NumStk: R=5. Pop NumStk: L=14. L op R = 14 – 5 evaluates to 9. Push 9 onto NumStk.
● read newline character. Pop NumStk to get final answer 9 and write it out.

4. Question 2
Analyze your read_and_evaluate_expression algorithm and give its running time in Big-Oh notation.

5. Question 3

Repeat question 1 using a linked list implementation of the abstract data ‘stack’.

6. Question 4

Analyze your algorithm in question 3 and give the Big-Oh notation.