StacksWhat is a stack?Abstract Data TypesStack operationsSome uses of stacksA balancing actExpression evaluationPerforming calculationsExample: 1+2*3+4Handling parenthesesHandling variablesHandling the = operatorAssociativityEvaluating associative operatorsSome things that can go wrongStacks in JavaSupporting recursionFactorial (animation 1)Factorial (animation 2)Factorial (animation 3)Factorial (animation 4)Factorial (animation 5)Factorial (animation 6)SummaryThe EndStacksWhat is a stack?•A stack is a Last In, First Out (LIFO) data structure•Anything added to the stack goes on the “top” of the stack•Anything removed from the stack is taken from the “top” of the stack•Things are removed in the reverse order from that in which they were insertedAbstract Data Types•An Abstract Data Type (ADT) is a “thing” consisting of:–Some kind of data–All the operations defined for working with that data•An ADT is abstract in the sense that nothing is said about how the ADT is implemented•The advantages of using an ADT are:–Simplicity: The user does not know, and does not need to know, how the ADT is implemented–Flexibility: The author of the ADT is free to improve the implementation, so long as existing operations are unchanged–Efficiency: By not providing certain operations, the ADT may be made much more efficient•What if the ADT doesn’t have the operations you need?–Maybe you are using the wrong ADT–Maybe the definition of the ADT should be expandedStack operations•Create an empty stack•stack.push(object)–Adds the object to the top of the stack; the item pushed is also returned as the value of push•object = stack.pop();–Removes the object at the top of the stack and returns it•object = stack.peek();–Returns the top object of the stack but does not remove it from the stack•stack.empty() –Returns true if there is nothing in the stackSome uses of stacks•Stacks are used for:–Any sort of nesting (such as parentheses)–Evaluating arithmetic expressions (and other sorts of expression)–Implementing function or method calls–Keeping track of previous choices (as in backtracking)–Keeping track of choices yet to be madeA balancing act•( [ ] ( { ( ) } [ ( ) ] ) ) is balanced;( [ ] ( { ( ) } [ ( ) ) ] ) is not•Simple counting is not enough to check balance•You can do it with a stack: going left to right,–If you see a (, [, or {, push it on the stack–If you see a ), ], or }, pop the stack and check whether you popped the corresponding (, [, or {–When you reach the end, check that the stack is emptyExpression evaluation•Almost all higher-level languages let you evaluate expressions, such as 3*x+y or m=m+1•The simplest case of an expression is one number (such as 3) or one variable name (such as x)–These are expressions•In many languages (including Java), = is considered to be an operator–Its value is (typically) the value of the left-hand side, after the assignment has occurred–Hence, statements such as if((x = a + b) > 0)... are legal•You may occasionally need to evaluate expressions in your own program, without benefit of a compilerPerforming calculations•To evaluate an expression, such as 1+2*3+4, you need two stacks: one for operands (numbers), the other for operators: going left to right,–If you see a number, push it on the number stack–If you see an operator,•While the top of the operator stack holds an operator of equal or higher precedence:–pop the old operator–pop the top two values from the number stack and apply the old operator to them–push the result on the number stack•push the new operator on the operator stack–At the end, perform any remaining operationsExample: 1+2*3+4•1 : push 1 on number stack•+ : push + on op stack•2 : push 2 on number stack•* : because * has higher precedence than +, push * onto op stack•3 : push 3 onto number stack•+ : because + has lower precedence than *:– pop 3, 2, and *–compute 2*3=6, and push 6 onto number stack–push + onto op stack•4 : push 4 onto number stack•end : pop 4, 6 and +, compute 6+4=10, push 10; pop 10, 1, and +, compute 1+10=11, push 11•11 (at the top of the stack) is the answerHandling parentheses•When you see a left parenthesis, (, treat it as a low-priority operator, and just put it on the operator stack•When you see a right parenthesis , ), perform all the operations on the operator stack until you reach the corresponding left parenthesis; then remove the left parenthesisHandling variables•There are two ways to handle variables in an expression:–When you encounter the variable, look up its value, and put its value on the operand (number) stack•This simplifies working with the stack, since everything on it is a number–When you encounter a variable, put the variable itself on the stack; only look up its value later, when you need it•This allows you to have embedded assignments, such as 12 + (x = 5) * xHandling the = operator•The assignment operator is just another operator–It has a lower precedence than the arithmetic operators–It should have a higher precedence than (•To evaluate the = operator:–Evaluate the right-hand side (this will already have been done, if = has a low precedence)–Store the value of the right-hand side into the variable on the left-hand side•You can only do this if your stack contains variables as well as numbers–Push the value onto the stackAssociativity•Most operators, including arithmetic +, -, *, and / are left-associative: leftmost operators are done first–For example, 10-5-2 means (10-5)-2, not 10-(5-2)•Some operators, including = and exponentiation, are right-associative: rightmost operators are done first–For example, x=y=z+1 means x=(y=z+1), not (x=y)=z+1Evaluating associative operators•Left-associative operators, such as + and / :–Don’t stack a left associative operator on top of an operator with the same precedence–For example, don’t push a + on top of a -–Instead, pop and apply the old operator before putting the new operator on the stack •Right-associative operators, such as = :–Put the new operator on the stack, if the current top-of-stack operator has the same or lower precedence•As always, never push an operator on top of a higher-precedence operatorSome things that can go wrong•The expression may be ill-formed: 2 + 3 +•When you go to evaluate the second +, there won’t be two numbers on the stack 1 2 + 3•When