A stack is a LIFO storage structure. This makes it deal for a range of applications. Let us look at two such examples. We use a stack to create a string that represents a decimal number in a base between 2 and 16. In this way, a programmer can view a number base-10(decimal) or in other base such as a base-2 (binary) or base-16(hexadecimal). This application is a stack version of the recursive algorithm in Section 6.1.
A second application uses a stack to test whether program source code correctly matches left-right parentheses, brackets and braces ("()", "[]" and "{}"). The technique is used by compilers to verify the balancing of symbol pairs.
Multibase Numbers :
Most programming languages display integer values in decimal as the default format. For some applications, particularly systems programming, you may want to display a number in binary, octal or hexadecimal. A hexadecimal (hex) number consists of digits choose from 0,1...,9,A,B,C,D,E, where the letters represent the values 10 to 15. The letters can be upper or lower case. To provide this ability, we design a method baseString(), which takes an integer value and a base in the range 2-16 as arguments and returns a string with the digits in the specified base. The implementation uses a stack to store the digits. For instance, the number n=75 has the following representations in base 2, 8 and 16 :
An algorithm uses repeated division by the base to describe a nonnegative integer N as a base B number. At each step, the remainder N%B identifies the next digit and the quotient N/B contains the remaining digits that are used for the next step. The process terminates when the quotient is 0. Below figure demonstrates the algorithm process :
The baseString() Algorithm :
The method baseString() takes a positive integer num and a integer b in the range 2<=b<=16. The return value is a string representing the value of num in the specified base b. A stack with Character objects stores the digit characters that are created by repeated divisions. Below is the implementation of the method :
Balancing Symbol Pairs :
A syntactically correct Java program must properly match and nest the symbol pairs "()", "[]" and "{}". You have experience with using matching parentheses for type casting and for creating subexpressions within a larger arithmetic expression. For discussion, we use the term left-symbol to describe a character in the set "(" , "[" and "{". A right-symbol is a character in the set ")", "]" and "}".
A program properly matches and nests the symbol pairs if each right-symbol matches the last unmatched left-symbol and all of the symbols are part of a matching pair. We use a stack to create an algorithm that checks for valid symbol-pair matching. For simplicity, assume the source code is a string. A scan of the string processes only left-symbol and right-symbol characters. In the case of a left-symbol, we store the character on a stack, awaiting the appearance of its right-symbol.
The method checkForBalance() implements the algorithm that determines whether an expression properly nests the symbol pairs. The method is passed a string as an argument and returns a string indicating that the expression is balanced or with an error message indicating an offending symbol. The algorithm scans successive characters in the string and builds the corresponding return string, called msgStr. If the character at the scan location is valid (maintains balance), a blank space is appended to msgStr and the scan continues. If the character is invalid, the algorithm appends the character "^" to the msgStrwhich lines up with the offending character in the expression. It pinpoints the error. After scanning an invalid character, we return from the method withmsgStr as the error message. The process may involve a complete scan of the expression, at which point a final test checks whether the stack is empty and returns with a message indicating a balanced string or an error condition.
In the implementation of checkForBalance(), we catch the expression that occurs when attempting to pop an empty stack. In this case, we have identified a missing left-symbol and can create a return error message. Throughout the method gives only generic error messages such as "Missing left symbol". This allows us to focus on the design of the algorithm. A compiler would generate specific error messages that indicate which type of symbol is missing.
沒有留言:
張貼留言