Purchase Solution

Data Structure and Algorithms

Not what you're looking for?

Ask Custom Question

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.

Purchase this Solution

Solution Preview

The Big o notation for both array based and linked list based stack is O(1).

COMMENT FROM STUDENT:
Please help wiht this error:

Exception in thread "main" ...

Purchase this Solution


Free BrainMass Quizzes
Javscript Basics

Quiz on basics of javascript programming language.

Word 2010: Table of Contents

Ever wondered where a Table of Contents in a Word document comes from? Maybe you need a refresher on the topic? This quiz will remind you of the keywords and options used when working with a T.O.C. in Word 2010.

Basic Computer Terms

We use many basic terms like bit, pixel in our usual conversations about computers. Are we aware of what these mean? This little quiz is an attempt towards discovering that.

Basic UNIX commands

Use this quiz to check your knowledge of a few common UNIX commands. The quiz covers some of the most essential UNIX commands and their basic usage. If you can pass this quiz then you are clearly on your way to becoming an effective UNIX command line user.

Java loops

This quiz checks your knowledge of for and while loops in Java. For and while loops are essential building blocks for all Java programs. Having a solid understanding of these constructs is critical for success in programming Java.