Fundamentals of Python: From First Programs Through Data StructuresObjectivesObjectives (continued)Overview of StacksUsing a StackThe Stack InterfaceInstantiating a StackExample Application: Matching ParenthesesExample Application: Matching Parentheses (continued)Three Applications of StacksEvaluating Arithmetic ExpressionsEvaluating Postfix ExpressionsEvaluating Postfix Expressions (continued)Slide 14Converting Infix to PostfixConverting Infix to Postfix (continued)BacktrackingBacktracking (continued)Slide 19Memory ManagementSlide 21Memory Management (continued)Slide 23Implementations of StacksTest DriverTest Driver (continued)Array ImplementationLinked ImplementationLinked Implementation (continued)Slide 30Slide 31Time and Space Analysis of the Two ImplementationsCase Study: Evaluating Postfix ExpressionsCase Study: Evaluating Postfix Expressions (continued)Slide 35Slide 36Slide 37Slide 38Slide 39SummaryFundamentals of Python:From First Programs Through Data Structures Chapter 14Linear Collections: StacksFundamentals of Python: From First Programs Through Data Structures 2ObjectivesAfter completing this chapter, you will be able to:•Describe the behavior of a stack from a user’s perspective•Explain how a stack can be used to support a backtracking algorithm•Describe the use of a stack in evaluating postfix expressionsFundamentals of Python: From First Programs Through Data Structures 3Objectives (continued)•Explain how the Python virtual machine uses a stack to support function and method calls•Analyze the performance trade-offs between an array-based implementation of a stack and a linked implementation of a stackFundamentals of Python: From First Programs Through Data Structures 4Overview of Stacks•Stack: LIFO structure in which access is completely restricted to just one end, called the top–Basic operations: push and popFundamentals of Python: From First Programs Through Data Structures 5Using a Stack•A stack type is not built into Python•Can use a Python list to emulate a stack–Use append to push and pop to pop–Drawback: stack can be manipulated by all of the other list operations as well•Extra operations violate the spirit of a stack as an ADT•We define a more restricted interface or set of operations for any authentic stack implementation and show how these operations are used in a brief exampleFundamentals of Python: From First Programs Through Data Structures 6The Stack InterfaceFundamentals of Python: From First Programs Through Data Structures 7Instantiating a Stack•We assume that any stack class that implements this interface will also have a constructor that allows its user to create a new stack instance•Later, we’ll consider two different implementations: –ArrayStack and LinkedStack•With different performance trade-offs•For now, assume that someone has coded these so we can use them:s1 = ArrayStack()s2 = LinkedStack()Fundamentals of Python: From First Programs Through Data Structures 8Example Application: Matching Parentheses•Compilers need to determine if the bracketing symbols in expressions are balanced correctlyFundamentals of Python: From First Programs Through Data Structures 9Example Application: Matching Parentheses (continued)•Approach 1: Count left and right parentheses–Does not work•Approach 2:–Scan expression; push left brackets onto a stack–On encountering a closing bracket, if stack is empty or if item on top of stack is not an opening bracket of the same type, we know the brackets do not balance–Pop an item off the top of the stack and, if it is the right type, continue scanning the expression–When we reach the end of the expression, stack should be empty; if not, brackets do not balanceFundamentals of Python: From First Programs Through Data Structures 10Three Applications of Stacks•We now discuss three other applications of stacks:–First, we present algorithms for evaluating arithmetic expressions–Second, we describe a general technique for using stacks to solve backtracking problems–Third, we examine the role of stacks in computer memory managementFundamentals of Python: From First Programs Through Data Structures 11Evaluating Arithmetic Expressions•In the infix form of an arithmetic expression, each operator is located between its operands•In the postfix form of an arithmetic expression, an operator immediately follows its operandsFundamentals of Python: From First Programs Through Data Structures 12Evaluating Postfix Expressions•Steps:–Scan across the expression from left to right–On encountering an operator, apply it to the two preceding operands; replace all three by the result–Continue scanning until you reach expression’s end, at which point only the expression’s value remains•To express this procedure as a computer algorithm, you use a stack of operands–The time complexity of the algorithm is O(n), where n is the number of tokens in the expressionFundamentals of Python: From First Programs Through Data Structures 13Evaluating Postfix Expressions (continued)•In the algorithm, token refers to an operand or an operator:Create a new stackWhile there are more tokens in the expressionGet the next tokenIf the token is an operandPush the operand onto the stackElse if the token is an operatorPop the top-two operands from the stackApply the operator to the two operands just poppedPush the resulting value onto the stackReturn the value at the top of the stackFundamentals of Python: From First Programs Through Data Structures 14Evaluating Postfix Expressions (continued)Fundamentals of Python: From First Programs Through Data Structures 15Converting Infix to Postfix•Start with an empty postfix expression and an empty stack–Stack will hold operators and left parentheses•Scan across infix expression from left to right•On encountering an operand, append it to postfix expression•On encountering a (, push it onto the stackFundamentals of Python: From First Programs Through Data Structures 16Converting Infix to Postfix (continued)•On encountering an operator–Pop operators with equal or higher precedence–Append them to postfix expression–Push scanned operator onto stack•On encountering a ), shift operators from stack to postfix expression until meeting matching (, which is discarded•On encountering the end of the infix expression, transfer remaining operators from the stack to the postfix expressionFundamentals of Python: From First Programs Through