pex5_4.cpp

数据结构C++代码,经典代码,受益多多,希望大家多多支持

#include <iostream.h>
#include <stdlib.h>

typedef char DataType;  // stack elements are characters

const int MaxStackSize = 50;

class Stack
{
    private:
        // private data members. stack array, and top
        DataType stacklist[MaxStackSize];
        int top;
    public:
        // constructor; initialize the top
        Stack (void);
        
        // stack modification operations
        void Push (const DataType& item);
        DataType Pop (void);
        void ClearStack(void);
        
        // stack access
        DataType Peek (void) const;
        
        // stack test methods
        int StackEmpty(void) const;
        int StackFull(void) const;      // array implementation
};

// initialize stack top.
Stack::Stack (void) : top(MaxStackSize)
{}

// push item on the the stack
void Stack::Push (const DataType& item)
{
    // if stacklist is full, terminate the program
    if (top == 0)
    {
        cerr << "Stack overflow!" << endl;
        exit(1);
    }
    
    // decrement top and copy item to stacklist
    top--;
    stacklist[top] = item;
}

// pop the stack and return the top element
DataType Stack::Pop (void)
{
    DataType temp;

    // if stack is empty, terminate the program
    if (top == MaxStackSize)
    {
        cerr << "Attempt to pop an empty stack!" << endl;
        exit(1);
    }
    
    // record the top element
    temp = stacklist[top];
    
    // increment top and return former top element
    top++;
    return temp;
}

// return the value at the top of the stack
DataType Stack::Peek (void) const
{
    // if the stack is empty, terminate the program
    if (top == MaxStackSize)
    {
        cerr << "Attempt to peek at an empty stack!" << endl;
        exit(1);
    }
    return stacklist[top];
}


// test for an empty stack
int Stack::StackEmpty(void) const
{
    // return the logical value top == MaxStackSize
   return top == MaxStackSize;
}

// test for a full stack
int Stack::StackFull(void) const
{
   // test the position of top
   return top == 0;
}

// clear all items from the stack
void Stack::ClearStack(void) 
{
    top = MaxStackSize;
}


// creates a new string with all blank characters removed
void Deblank(char *s, char *t)
{
    // loop through expression until NULL character is found
    while(*s != NULL)
    {
        // if character is a non-blank, copy to new string
        if (*s != ' ')
            *t++ = *s;
        s++;            // move to next character
    }
    *t = NULL;          // append NULL to new string
}

void main(void)
{
    const int True = 1, False = 0;
    
    // stack S holds chars in reverse order
    Stack S;
    
    char palstring[80], deblankstring[80], c;
    int i = 0;
    int ispalindrome = True;    // assume string is a palindrome

    // read in the full-line string
    cin.getline(palstring,80,'\n');

    // remove blanks from string and put result in deblankstring
    Deblank(palstring,deblankstring);

    // push the chars of deblanked expression on the stack
    i = 0;
    while(deblankstring[i] != 0)
    {
        S.Push(deblankstring[i]);
        i++;
    }

    // now pop stack, comparing characters with original string
    i = 0;
    while (!S.StackEmpty())
    {
        c = S.Pop();    // get next character from  stack
        // if chars don't match, break out of the loop
        if (c != deblankstring[i])
        {
            ispalindrome = False;   // not a palindrome
            break;
        }
        i++;
    }

    if (ispalindrome)
        cout << '\"' << palstring << '\"' 
             << " is a palindrome" << endl;
    else
        cout << '\"' << palstring << '\"' 
             << " is not a palindrome" << endl;
}

/*
<Run>

a man a plan a canal panama
"a man a plan a canal panama" is a palindrome
*/