2008级计算机 数据结构课堂教学笔记 内部资料,仅供课堂教学使用 Later. we shall use several further values of an error code Programming Precept: After a client uses a class method, it should decide whether to check the resulting error status. Classes should be designed to allow clients to decide how to respond to errors. P 59 C++ also provides more sophisticated error processing called exception handling. The standard library implementations of classes use exception handling, but we shall opt for the simplicity of returning error codes in all our implementations Specification for Methods P 59-60 Error code Stack: pop(): Error code Stack: push(const Stack entry &item) Error code Stack: top(Stack entry &item)const bool Stack: empty( )const 2.2.2 Class Specification, Contiguous stack We set up an array to hold the entries in the stack and a counter to indicate how many entries there are P60 Class Specification 2.2.4P63 The declaration of private visibility for the data makes it is impossible for a client to access the data stored in a Stack except by using the methods push( ) pop(), and top() Important result: A Stack can never contain illegal or corrupted data. In general, data is said to be encapsulated if it can only be accessed by a controlled set of functions Programming Precept: The public methods for a data structure should be implemented without preconditions. The data members should be kept private. P 63 Representation of Data in a Contiguous Stack P62 2.2.3 Stack Methods P61 Further stack methods p61-62 2.3 Application: A Desk Calculator Reverse Polish Calculator P66-67 In a Reverse Polish calculator, the operands(numbers, usually) are entered before an operation(like addition, subtraction, multiplication, or division) is specified. The operands are pushed onto a stack. When an operation is performed, it pops its operands from the stack and pushes its result back onto the stack Obtaining a command p67-68 The auxiliary function get command obtains a command from the user, checking that it is valid and converting it to lowercase by using the string function tolower()that is declared in the standard header file ectype 2. 4 Application: Bracket Matching P69-71 We develop a program to check that brackets are correctly matched in an input text file e We limit our attention to the brackets,i,(), and I e We read a single line of characters and ignore all input other than bracket characters e Algorithm: Read the file character by character. Each opening bracket i that is encountered is considered as unmatched and is stored until a matching bracket can be Any closing bracket ),I, or) must correspond, in bracket style, to the last unmatched opening bracket, which should now be retrieved and removed from storage. Finally, at the end of the program, we must check that no unmatched opening brackets are left over a program to test the matching of brackets needs to process its input file character by character, and, as it works its way through the input, it needs some way to remember any currently unmatched brackets These brackets must be retrieved in the exact reverse of their input order, and therefore a Stack provides an attractive option for their storage Our program need only loop over the input characters, until either a bracketing error is detected or the input file ends. Whenever a bracket is found an appropriate Stack operation is applied2008 级 计算机专业 数据结构 课堂教学笔记 内部资料，仅供课堂教学使用 Later, we shall use several further values of an Error code. Programming Precept: After a client uses a class method, it should decide whether to check the resulting error status. Classes should be designed to allow clients to decide how to respond to errors. P.59 C++ also provides more sophisticated error processing called exception handling. The standard library implementations of classes use exception handling, but we shall opt for the simplicity of returning error codes in all our implementations. Specification for Methods P.59-60 Error code Stack :: pop( ); Error code Stack :: push(const Stack entry &item); Error code Stack :: top(Stack entry &item) const; bool Stack :: empty( ) const; 2.2.2 Class Specification, Contiguous Stack We set up an array to hold the entries in the stack and a counter to indicate how many entries there are. P60 Class Specification 2.2.4 P.63 The declaration of private visibility for the data makes it is impossible for a client to access the data stored in a Stack except by using the methods push( ), pop( ), and top( ). Important result: A Stack can never contain illegal or corrupted data. In general, data is said to be encapsulated if it can only be accessed by a controlled set of functions. Programming Precept: The public methods for a data structure should be implemented without preconditions. The data members should be kept private. P.63 Representation of Data in a Contiguous Stack P.62 2.2.3 Stack Methods P.61 Further Stack Methods P.61-62 [2.3] Application: A Desk Calculator Reverse Polish Calculator P.66-67 In a Reverse Polish calculator, the operands (numbers, usually) are entered before an operation (like addition, subtraction, multiplication, or division) is specified. The operands are pushed onto a stack. When an operation is performed, it pops its operands from the stack and pushes its result back onto the stack. Obtaining a Command P.67-68 The auxiliary function get command obtains a command from the user, checking that it is valid and converting it to lowercase by using the string function tolower( ) that is declared in the standard header file cctype. [2.4] Application: Bracket Matching P.69-71 ⚫ We develop a program to check that brackets are correctly matched in an input text file. ⚫ We limit our attention to the brackets {, }, ( , ), [, and ]. ⚫ We read a single line of characters and ignore all input other than bracket characters. ⚫ Algorithm: Read the file character by character. Each opening bracket ( , [, or { that is encountered is considered as unmatched and is stored until a matching bracket can be found. Any closing bracket ), ], or } must correspond, in bracket style, to the last unmatched opening bracket, which should now be retrieved and removed from storage. Finally, at the end of the program, we must check that no unmatched opening brackets are left over. ⚫ A program to test the matching of brackets needs to process its input file character by character, and, as it works its way through the input, it needs some way to remember any currently unmatched brackets. ⚫ These brackets must be retrieved in the exact reverse of their input order, and therefore a Stack provides an attractive option for their storage. ⚫ Our program need only loop over the input characters, until either a bracketing error is detected or the input file ends. Whenever a bracket is found, an appropriate Stack operation is applied