Code Listings Chapter 6

Listing 6-1 A C++ interface for stacks

/** @file StackInterface.h */
#ifndef _STACK_INTERFACE
#define _STACK_INTERFACE
template < class ItemType > class StackInterface
{
  public:

/** Sees whether this stack is empty.
@return True if the stack is empty, or false if not. */
    virtual bool isEmpty()const = 0;

/** Adds a new entry to the top of this stack.
@post If the operation was successful, newEntry is at the top of the stack.
@param newEntry The object to be added as a new entry.
@return True if the addition is successful or false if not. */
    virtual bool    push(const ItemType & newEntry) = 0;

/** Removes the top of this stack.
@post If the operation was successful, the top of the stack
has been removed.
@return True if the removal is successful or false if not. */
    virtual bool    pop() = 0;

/** Returns the top of this stack.
@pre The stack is not empty.
@post The top of the stack has been returned, and
the stack is unchanged.
@return The top of the stack. */
    virtual ItemType peek() const = 0;
};				// end StackInterface
#endif

Listing 6-A  Algorithm to Determine Validity of a String in a Language

// Checks the string aString to verify that it is in language L.
// Returns true if aString is in L, false otherwise.
recognizeString (aString:string):boolean 
    aStack =    a new empty stack
    // Push the characters that are before the $ (that is, the characters in s) onto the stack
    i = 0 
    ch = character at position i in aString 
    while (ch is not a '$')
    {
       aStack.push (ch) i++ch =
       character at position i in aString
    }
    // Skip the $
    i++
    // Match the reverse of s
    inLanguage = true     // Assume string is in language
    while (inLanguage and i < length of aString)
    {
    if (!aStack.isEmpty ())
        {
        stackTop = aStack.peek () aStack.pop () 
        ch = character at position i in aString
        if (stackTop equals ch) {
             i++   // Characters match
           else
             inLanguage = false    // Characters do not match (top of stack is not ch )
            }
          else
            inLanguage = false    // Stack is empty (first half of string is shorter                 // than second half)
        }
        if (inLanguage and aStack.isEmpty ())
            aString is in language
           else
             aString is not in language

Listing 6-B A Pseudocode Algorithm to Convert an Infix Expression to Postfix

for (each character ch in the infix expression)
{
    switch (ch)
    {
        case operand: // Append operand to end of postfix expressionstep 1
            postfixExp = postfixExp ch
                break
                case '(': // Save '(' on stackstep 2
                    aStack.push (ch)
                    break
                case operator: // Process stack operators of greater precedencestep 3
                    while (!aStack.isEmpty () and aStack.peek () is not a '(' and
                        precedence (ch) <= precedence (aStack.peek ()))
                    {
                        Append aStack.peek () to the end of postfixExp
                        aStack.pop ()
                    }
                    aStack.push (ch)  // Save the operator
                    break
                case ')': // Pop stack until matching '(' step 4
                    while (aStack.peek () is not a '(')
                    {
                        Append aStack.peek () to the end of postfixExp
                        aStack.pop ()
                    }
                    aStack.pop ()  // Remove the open parenthesis
                    break
    }
}
// Append to postfixExp the operators remaining in the stackstep 5
while (!aStack.isEmpty ())
{
    Append aStack.peek () to the end of postfixExp
        aStack.pop ()
}