回分類題庫
d168: OOP Lab Exercise: charStack Class Enhancement
出處:

Difficulity : N/A
Accepted : 69 Times | Submit :148 Times | Clicks : 1860
Accepted : 61 Users | Submit : 63 Users | Accepted rate : 97%
Time Limit :10000 ms | Memory Limit : 64000 KBytes
題目加入時間 : 2010-05-04 13:57

Content :

Recall the charStack class used in previous assignment, we use vector to control the elements storagement. It is because your status was an user before, however, time flies, you are now a developer. You are now asked to implement the char Stack without using vector. You have to do the memory management yourself !

Given a charStack header file as following:

class charStack {
    public:
        charStack();
        ~charStack();
    bool isempty() const;
        char pop();
        void push(char c);
        char peek() const;
    private:
        char* elements;
        int size;
        int capacity;
};

We now change the data member elements's type to a char pointer (vector<char> before). And we add a new data member "capacity" which represent the capacity of the charStack. This is different to size. Size is the number of elements in charStack and capacity is the limit number of elements that charStack can hold. Let's take a bottle for instance, a bottle say can contain 5 liters of water. That is the capacity of the bottle. But we can only pour a liter of water into the bottle which is the "size" of water.

Now your task is an extensible char array. Say we set the initial capacity of charStack is 1. As we try to push new elements into the stack. The capacity is not enough when we push the second char to the stack, of course. To deal with this situation, we can reallocate a new memory space which size is 2*capacity, and we copy the elements in the array to this new space and let the elements pointer point to this space. Hence we gain a larger capacity of charStack. That is exatly what a vector do. It will automatically gain more space from system so that you can push as many elements as you want.

To simplify, the requirements of the exercise today is below.

1.  push: 
You have to dynamically rellocate more space when size is equal to capacity. And we always reallocate new memory space with size of 2*capacity.(capacity *= 2 )
If fai to allocate the space output a line: "Cannot reallocate memory space." Other failure output a line: "Error"
Notice that you have to do the memory management, that is, you have to delete all excess memory space.

2. pop:
return the top element of charStack and remove it from it. However, you have to output a line: "Empty Stack" if necessary.

3. peek:
Similar to pop, however, just return the top of the stack without removing it. A line:"Empty Stack" is necessary, too.

4. Constructor / Destructor:
You have to new a memory space with size of initial capacity in constructor and delete the memory you allocated in destructor.

5. main:
Here is a line with syntax error code segment. You have to fix it.

To get pass, you have to:

1.  Using the given source code below. You cannot add more data member to the charStack class and modify the written code in constructor.

2.  Except fixing the wrong line in main function, you should not modify other part of main function.

3.  Complete push, pop, peek member functions of charStack with the specification above.

4.  Submit with your oop account and gain AC.

======================================================

Code here:  http://www.cs.nccu.edu.tw/~g9803/oop/charStack_ex.cpp

#include <iostream>
 
using namespace std;
 
class charStack {
    public:
        charStack();
    ~charStack();
    bool isempty() const;
        char pop();
        void push(char c);
        char peek() const;
    private:
        char* elements;
        int size;
    int capacity;
};
 
/*Initialize size = 0, capacity = 1, elements = new char array of size capacity*/
charStack::charStack(){
    size = 0;
    capacity = 1;
    /*Initialize elements*/
}
 
/*Destructor, delete elements array*/
charStack::~charStack(){
    /*Delete elements*/
}
 
bool charStack::isempty()const{
    return size == 0;
}
 
 
/*Pop the toppest elements of stack and return it. If stack is empty output "Empty Stack"*/
char charStack::pop(){
 
}
 
 
/*Push a char to stack, if capacity is not fit, reallocate new array with capacity *= 2, 
if reallocate fail, output: "Cannot reallocate memory space.", other errors, output: "Error" */
void charStack::push(char c){
 
}
 
 
/*Return top element of the stack, output "Empty Stack" if necessarry*/
char charStack::peek()const{
 
}
 
 
/*Here are some declaration missing, fix it.*/
int main(){
     
    string input;
 
    while(getline(cin, input)){
        charStack *cs = some thing is missing here;
 
        for(int i = 0; i < input.length(); i++){
            cs -> push(input.at(i));
        }
 
        while(!cs -> isempty()){
            cout << cs -> peek();
            cout << cs -> pop();
        }
 
        cout << endl;
 
        (*cs).pop();
        (*cs).peek();
    }
 
    return 0;
}

 

Input :

Each line is a set of input.

Output :

Reverse and double the input string, see example IO and main function given above for details.

Sample Input :

chenk
NCCUCS5thProgrammingContest20100515

Sample Output :

kknneehhcc
Empty Stack
Empty Stack
5511550000110022ttsseettnnooCCggnniimmmmaarrggoorrPPhhtt55SSCCUUCCCCNN
Empty Stack
Empty Stack

Hint :


  

Author :


  Solve it!   Status Forum (0)

C++
C
JAVA
21498. oop97306016 (10 ms , 456KB)
21490. oop97306016 (12 ms , 458KB)
21041. oop98703033 (12 ms , 458KB)
20969. Assassincross (16 ms , 464KB)
34595. QQ (18 ms , 462KB)
沒有解題記錄 沒有解題記錄

執行時間會受很多因素影響因此僅供參考,主機等級請看這裡