Chapter 7,Stack,Overview,The stack data structure uses an underlying linear storage organization. The stack is one of the most ubiquitous data structures in computing.,Learning Objectives,Describe the behavior of a stack. Enumerate the primary operations supported by the stack. Examine several applications of the stack, including parentheses matching, evaluating postfix expressions, and the conversion of an infix expression to postfix form.（括号匹配，后缀表达式求值，中缀转成后缀） Understand the public interface of a stack class in Java and the running times of its methods.（栈类接口）,Learning Objectives,Develop a postfix package in Java to implement postfix expression evaluation.（对后缀表达式进行求值） Study the implementation of a stack class in Java, and the trade-offs involved in choosing between candidate reusable components.,7.1 Stack Properties,A stack is a list in which all insertions and deletions of entries are made at one end, called the top of the stack（栈顶）.,Example and sketch map,7.1 Stack Properties,An entry is removed, or popped from the top of stack. An entry added or pushes onto the top of a stack. The last entry which is inserted is the first one that will be removed （后进先出）. Empty stack means the stack has no item.,7.1 Stack Properties,Surfing the Web on a browser: The sequence of back clicks loads the browser with Web pages in reverse order of visit.（用“后退”按钮会以反序装载刚才访问过的网页） The last visited page is the first loaded when going back. plates sitting on the counter in a busy cafeteria. Customers take trays off the top of stack. Employees returned trays back on top of the stack.,A Problem :,Suppose we have five items which were pushed into a stack in turn, the order of the push is “abcde”, and the pop turn is “dceba”, please decide the minimum size of the stack.假设有个元素abcde顺序进栈（进栈过程中可以出栈），出栈序列为dceba，则该栈容量必定不小于多少。,7.1 Stack Properties,7.2.1 Parentheses Matching,A compiler checks expressions in a program to ensure that all parentheses are matched. Good text editors match parentheses on-the-fly. On typing a closing parenthesis, the user is shown the companion opening parenthesis. A closing parenthesis matches the latest opening parenthesis. In implementing the matching, opening parenthesis need to be stored when encountered, and recalled in reverse order whenever closing parentheses are encountered.,7.2.1 Parentheses Matching,The location of the opening parenthesis needs to be stored. When the user types an opening parenthesis, the text editor could push its location on stack. When a closing parenthesis is typed, the location of the top of the stack is popped and used to address the matching opening parenthesis in the text.,3*A+(b*cd)3*A+(b*cd3*A+(b*cd)3*A+(b*cd)dfg,public static void main(String args) Stack open=new Stack(); Scanner sc=new Scanner(System.in); String s=sc.next(); char symbol; boolean is_matched=true; int i=0;,while (is_matched ,if (!open.isEmpty( ) System.out.println( “Unmatched opening bracket(s) detected.“ ); else if (is_matched) System.out.println( “all bracket(s) are matched .“ ); /该程序只给出了是否配对的信息， /如果要提示在哪里不配对，可以在栈中存储开括号的位置。 /即在输出时可做相应不匹配位置的提示,7.2.2 Postfix Expression Evaluation,We write arithmetic expressions like this:Consider the expression:It cannot simply be scan left to right.,7.2.2 Postfix Expression Evaluation,Postfix, does not need parentheses. An operator always follows the operands or sub-expressions on which it operates.,7.2.2 Postfix Expression Evaluation,7.2.2 Postfix Expression Evaluation,7.2.2 Postfix Expression Evaluation,7.2.2 Postfix Expression Evaluation,Two conditions that must be met for the evaluation process to terminate successfully: When an operator is encountered, there must exist a most recent pair of operands or temporary results for application. When the scanning of the expression is complete, there must be exactly one value on the stack.,7.2.2 Postfix Expression Evaluation,7.2.2 Postfix Expression Evaluation,Two possible errors that may be encountered by the algorithm: One is that of insufficient operands. The other is that of too many operands.Insufficient operands case is detected when the token is an operator, but the stack has less than the two operands on which the operator must be applied. Too many operands case is detected after the while loop, when the stack has more than one entry in it.,7.2.3 Infix to Postfix Conversion,Convert an infix expression to postfix form. Algorithm does one simple scan of the input. Algorithm takes O(n) time. Example 5+6 (1+2)- 9/3,5+6* (1+4*2)/3-9#,A . 5+6* (1+2)- 9/3#,1、初始化一个空栈s,并入栈一个界限符“#”，“#”的优先权在所有算符中最小。 2、依次读入整个中缀表达式，在其最后添加“#”； 3、在中缀表达式未到达尾部时，重复（1）分离出中缀表达式中的当前逻辑单元b；（2）如b为操作数，则直接输出至后缀表达式；否则，若b为算符，设为2，将2与栈顶的运算符1进行优先权比较；a.若12，则说明1是已扫描的运算符中优先级最高者，则将1出栈，并将1输出至后缀表达式；2继续与新栈顶1比较，直至12不成立，根据是上述a还是b的不同情况进行处理。,while (exprTok.hasMoreTokens() String token=exprTok.nextToken();if (!isOperator(token)postExprStatus.update(token);elseCharacter a=OpStack.first();Character b=token.charAt(0);int j=priority(a,b);while (j0)/栈顶优先权高时，出栈栈顶并依次加入到后缀表达式中a=OpStack.pop();postExprStatus.update(a.toString();a=OpStack.first();j=priority(a,b);/当前算符优先权高时，将该算符入栈if (j0) OpStack.push(b);/当前算符与栈顶算符优先权相等时，栈顶出栈if (j=0) OpStack.pop(); ,