CIS-610 Data Structures and Algorithms

Home Work								Due:	09/23/1999

1. Use the operations push, pop, stacktop, and empty to construct operations which do each of the following:
a. set i to the second element from the top of the stack; leaving the stack without its top two elements.
b. set i to the second element from the top of the stack; leaving the stack unchanged.
c. Given an integer n, set i to the nth element from the top of the stack; leaving stack without its top n elements.
d. Given an integer n, set i to the nth element from the top of the stack; leaving stack unchanged.
e. Set i to the bottom element of the stack; leaving the stack empty.
f. Set i to the bottom element of the stack; leaving the stack unchanged (Hint: use another, auxiliary stack)
g. Set i to third element from the bottom of the stack.

2. Simulate the action of the algorithm for each of the following strings by showing the contents of the stack at each point.
a. ( A + B})
b.  (A + B) - {C + D} - {F + G]
c. ( (H ) * { ( { J + K] ) } )

3. Write a routine pushandtest similar to popandtest.

4. Show how to implement a stack of integers using an array int s[STACKSIZE], where s[0] is used to to contain the index of
 the top element of the stack, and where s[1] through s[STACKSIZE - 1] contain the elements of the stack. Write routines pop,
 push, empty, popandtest, stacktop and pushandtest. Use any programming language that supports array. 

5. Transform each of the following expressions to prefix and postfix:
a.  ( A + B) * ( C - D ) $ E * F
b. A + (((B - C ) * ( D - E) + F) / G) $ (H - J)

6. Transform each of the following prefix expressions to infix:
a. + A - BC
b. + - $ ABC * D ** EFG

7. Transform each of the following postfix expressions to infix:
a. AB + C -
b. ABCDE - + $ * EF * -

8. Apply the evaluation algorithm to evaluate the following postfix expressions. Assume A=1, B=2, C=3.
a. AB + C - BA + C $ -
b. ABC + * CBA - + *

9. Write a program to convert:
a. a prefix to infix
b. a postfix to prefix

10. Write a routine, reduce that accepts an infix string and forms an equivalent infix string with all superfluous parentheses 
removed.