tailieunhanh - CSE Faculty - Chapter 3: STACK (part b)

Reversing data items Ex.: Reverse a list. Convert Decimal to Binary. Brackets Parse. Infix to Postfix Transformation. Evaluate a Postfix Expression. Parsing Ex.: Ex.: Postponement of processing data items Backtracking Ex.: Goal Seeking Problem. Knight’s Tour. Exiting a Maze. Eight Queens Problem. .Reverse a list PROBLEM: Read n numbers, print the list in reverse order. Algorithm ReverseList Pre User supplies numbers. Post The numbers are printed in reverse order. Uses Stack ADT. 1. loop (stack is not full and there is more number) 1. read a number 2. push the number into the stack 2. loop (stack is not empty) 1. top the number from the stack 2. pop. | Stack Applications Reversing data items Ex. Reverse a list. Convert Decimal to Binary. Parsing Ex. Brackets Parse. Postponement of processing data items Ex. Infix to Postfix Transformation. Evaluate a Postfix Expression. Backtracking Ex. Goal Seeking Problem. Knight s Tour. Exiting a Maze. Eight Queens Problem. Reverse a list PROBLEM Read n numbers print the list in reverse order. Algorithm ReverseList Pre User supplies numbers. Post The numbers are printed in reverse order. Uses Stack ADT. 1. loop stack is not full and there is more number 1. read a number 2. push the number into the stack 2. loop stack is not empty 1. top the number from the stack 2. pop stack 3. write the number end ReverseList 2 Reverse a list Algorithm ReverseList 1. stackObj Stack 2. 3. loop not and there is more number 1. read number 2. number 4. loop not 1. number 2. 3. write number 5. end ReverseList