Question

Data Structure

17.

Given: (e + f) / a – b * c

Write out the postfix form

19. Make a prototype, including task, input and output, of compareLists that would take two lists of reference (ArrayList) and return a count of matching items (note, do NOT code the function)

20.Using the Stack operations, write a pseudocode routine, dupPos, that takes aStack for integers, checks to see if the top is positive. If positive, duplicate the top of the stack (i.e. pop a copy of that value onto the stack). If it is negative, pop it off.

21.Use the ListInterface operations only to create a makeEven routine in C++ that will take a list of integers (array or linked, your choice) as a reference. Use the list operations on the passed list to make all items that are odd into even values.

22.What is the main difference between an ADT List and the ADT Stack?

Answer 1

CONVERSION OF INFIX TO POSTFIX(reverse polish)

STEPS

STEP 1 : First Insert a opening parenthesis at the beginning and closing parenthesis
                at the end of the expression.

STEP 2 : Arrange the expression in the ARRAY.

STEP 3 : Scan every element from the array and if operand than store it in the
               POSTFIX and if operator than PUSH it into the STACK followed by
               STEP-4and STEP-5

STEP 4 : If the scanned operator having Less or Equal precedence than the existing operator than pop out the operators from the stack till a less precedence operator or opening parenthesis is found.

STEP 5 : If the scanned operator is a closing parenthesis than pop the operators from the STACK up to the Opening Parenthesis and omit them and poped operators will store in the POSTFIX.

STEP 6 : Repeat step-3, step-4, step-5 till all the elements are scanned from the array.

STEP 7 : Print the POSTFIX as the result.

    

Given the infix expression as : (e + f) / a – b * c

Array	Stack	Postfix
(	(
(	((
e	((	e
+	((+	e
f	((+	ef
)	(	ef+
/	(/	ef+
a	(/	ef+a
-	(-	ef+a/
b	(-	ef+a/b
*	(-*	ef+a/b
c	(-*	ef+a/bc
)		ef+a/bc*-

The Postfix expression will be : ef+a/bc*-