Description

The task is to define the class ‘RleCodec’ for run-length encoding.

About implementing the virtual function:

We have the base class ‘Codec’ as an interface. The member functions in ‘Codec’ are pure virtual functions. Therefore we need to implement those virtual functions in the derived class ‘RleCodec’. The functions ‘decode’, ‘show’, ‘is_encoded’ are already done. The only function you need to complete is ‘RleCodec::encode’ in ‘function.cpp’.

In ‘main.cpp’, we see two functions having an argument of type ‘Codec&’:

std::ostream& operator<<(std::ostream& os, Codec& data);

void encode_decode(Codec& data);

Since ‘RleCodec’ is a derived class of ‘Codec’, we may pass an object of

‘RleCodec’ to the above two functions by reference as if it is an object of ‘Codec’. Calling ‘data.show(os);’ will invoke the virtual function of the corresponding derived class.

About run-length encoding:

The rule of run-length encoding is simple: Count the number of consecutive repeated characters in a string, and replace the repeated characters by the count and a single instance of the character. For example, if the input string is ‘AAADDDDDDDBBGGGGGCEEEE’, its run-length encoding will be ‘QCAQGDQBBQEGQACQDE’, where QCA means that there are 3 A’s and 3 can be encoded as C (the third character in alphabet), QGD means that there are 7 D’s and 7 can be encoded as G (the 7 th character in alphabet), and QBB means we have 2 B’s and 2 can be encoded as B (the second character in alphabet) … etc. Note that every encoding segment starts with a Q.

If there are 27 A’s in a string, it is separated into two segments ‘QZAQAA’, which means the first segment ‘QZA’ represents 26 A’s, and the second segment ‘QAA’ represents 1 A.

In ‘function.h’, we add the class ‘DummyCodec’ as a sample of implementing a derived class of the base class ‘Codec’. You do not need to change anything in ‘function.h’. The only function you need to write for this problem is the function ‘RleCodec::encode’ in ‘function.cpp’.

Hint: std::stringstream could be useful in solving this problem. Please refer to ‘RleCodec::decode’ for how to use std::stringstream.

You only need to submit ‘function.cpp’. OJ will compile it with ‘main.cpp’ and ‘function.h’.

We have already provided partial function.cpp belowed.

Note that if you can't use "auto".

For codeblock, go to the codeblock menu Settings --> Compiler ... --> Compiler flags and check Have g++ follow the C++11 ISO C++ language standard [-std=c++11]

For command line compiler, use g++ myprog.cpp -std=c++11 -o myprog

main.cpp

#include <iostream> #include "function.h" std::ostream& operator<<(std::ostream& os, Codec& data) { data.show(os); return os; } void encode_decode(Codec & data) { if (!data.is_encoded()) data.encode(); else data.decode(); } int main() { std::string input_string; std::cin >> input_string; DummyCodec dummy{input_string}; encode_decode(dummy); std::cout << "Dummy encoding: "; std::cout << dummy << std::endl; encode_decode(dummy); std::cout << "Dummy decoding: "; std::cout << dummy << std::endl; RleCodec rle{input_string}; encode_decode(rle); std::cout << "RLE encoding: "; std::cout << rle << std::endl; encode_decode(rle); std::cout << "RLE decoding: "; std::cout << rle << std::endl; }

function.h

#ifndef _FUNC_H #define _FUNC_H #include <iostream> #include <string> class Codec { public: virtual void encode() = 0; virtual void decode() = 0; virtual ~Codec() { } // Do nothing virtual void show(std::ostream& os) const = 0; virtual bool is_encoded() const = 0; }; class DummyCodec: public Codec { public: DummyCodec(std::string s): encoded{false}, code_str{s} { } void encode() { encoded = true; } void decode() { encoded = false; } void show(std::ostream& os) const { os << code_str; } bool is_encoded() const { return encoded; } private: bool encoded; std::string code_str; }; class RleCodec: public Codec { public: RleCodec(std::string s): encoded{false}, code_str{s} { } void encode(); void decode(); void show(std::ostream& os) const { os << code_str; } bool is_encoded() const { return encoded; } private: bool encoded; std::string code_str; }; #endif

function.cpp

#include <iostream> #include <string> #include <sstream> #include <cctype> #include "function.h" void RleCodec::encode() { } void RleCodec::decode() { std::stringstream os; std::string int_str; char q = 'A'; char number = ' '; int cnt = 0; for (auto c : code_str) { if (q=='A') { q = c; }else if(number == ' '){ number = c; } else { int_str.push_back(c); int cnt = 0; cnt = number - 'A' +1; for (int i=0; i<cnt; ++i) os << c; int_str.clear(); number = ' '; q = 'A'; } } code_str = os.str(); encoded = false; }

Input

A line contains of several characters .(n <= 100)

Output

There are four lines.

The first and second lines are dummy encoding and decoding. You don't need to implement it.

The third and forth lines are RLE encoding and decoding.

Each line is followed by a new line character.

Sample Input  Download

Sample Output  Download

Partial Judge Code

11021.cpp

Partial Judge Header

11021.h

Tags

Discuss

Description

A binary search tree (BST) is a binary tree, whose internal nodes each store a key and each have two sub-trees, commonly denoted left and right. The tree additionally satisfies the property: the key in each node must be greater than all keys stored in the left sub-tree, and smaller than all keys in the right sub-tree.

 

Let’s see how the BST data structure can be realized in C++ using a linked structure. We define three classes and use polymorphism as follows:

 

function.h

#ifndef function_h #define function_h #include <iostream> #include <math.h> using namespace std; class BST{ public: BST():Height(0){} virtual ~BST() {} virtual void insert(const int &) = 0; virtual void print() const = 0; int height() const { return Height; }// An empty tree has height of 0. A tree with only root node has height of 1. protected: int Height; }; class ListNode{ friend class List_BST; //make List_BST a friend public: ListNode(const int &info):key( info ),left( NULL ),right( NULL ) //constructor { }//end ListNode constructor private: int key; ListNode *left; ListNode *right; };//end class ListNode class List_BST : public BST{ public: List_BST() : BST(), root(NULL) { } virtual ~List_BST() {} virtual void insert(const int &) override; virtual void print() const override{ printIncOrder(root); } private: ListNode *root; // private member functions ListNode* createLeaf(int key) const; //new a ListNode and return its address void printIncOrder(ListNode* Ptr) const { if(Ptr!=NULL) { printIncOrder(Ptr->left); cout<<Ptr->key<<" "; printIncOrder(Ptr->right); } } }; #endif /* function_h */

main.cpp

#include <iostream> #include <string.h> #include "function.h" using namespace std; void BSTManipulator(BST& bstobj, char cmd ){ int n; if (cmd == 'I') { cin >> n; bstobj.insert(n); }else if (cmd == 'H'){ cout << bstobj.height() << endl;; }else if (cmd == 'P'){ bstobj.print(); cout << endl; } } int main(){ List_BST bst; char cmd; while (cin >> cmd) BSTManipulator(bst, cmd); return 0; }

 

where

1. Class BST serves as the abstract base class for realizing polymorphism
2. List_ BST provide an approach to implementing the BST data structure

 

REQUIREMENTS:

1. Implement the insert and createLeaf member functions of the List_ BST class.

Note:

1.      This problem involves three files.

• function.h: Class definitions.
• function.cpp: Member-function definitions.
• main.cpp: A driver program to test your class implementation.

You will be provided with main.cpp and function.h, and asked to implement function.cpp.

 

2.      For OJ submission:

       Step 1. Submit only your function.cpp into the submission block.

       Step 2. Check the results and debug your program if necessary.

 

Input

There are three kinds of commands:

• “I A”: insert a node with int value A(A>0) into the BST. If the key already exists, you simply do nothing.
• “P”: show the current content of the BST.
• “H”: print the BST’s height. Remember if the BST is empty, the height is 0 and you should print “0”.

Each command is followed by a new line character.

Input terminated by EOF.

Output

The output shows the result of each command.

Sample Input  Download

Sample Output  Download

Partial Judge Code

11022.cpp

Partial Judge Header

11022.h

Tags

Discuss

Description

Create a class Matrix to represent an N * N matrix.

 

Provide public member functions that perform or derive:

     1) Matrix &clockwise90();

Rotate a Matrix by 90° clockwise.

 

NOTE:

If a is a Matrix, the result of a.clockwise90() should be stored back into a. Remember to return the object itself for the use of operation concatenation, such as a.clockwise90().clockwise90(). (You can refer to member function “Matrix &operator=” in function.h.)

     2) Overload the stream extraction operator (>>) to read in the matrix elements.

     3) Overload the stream insertion operator (<<) to print the content of the matrix row by row. Note that

         all of the integers in the same line are separated by a space, and there is a new line character at the

         end of each line.

 

Note:

1.  This problem involves three files.

• function.h: Class definition of Matrix.
• function.cpp: Member-function definitions of Matrix.
• main.cpp: A driver program to test your class implementation.

You will be provided with function.h and main.cpp, and asked to implement 

 

function.h

#ifndef function_h #define function_h #include <iostream> class Matrix { friend std::ostream &operator<<(std::ostream &, const Matrix &); friend std::istream &operator>>(std::istream &, Matrix &); public: Matrix(int s = 5) //default constructor :size(s) { buf = new int[size*size]; matrix = new int* [size]; for(int i=0; i<size; i++) matrix[i] = &buf[i*size]; for(int i=0; i<size; i++) for(int j=0; j<size; j++) matrix[i][j] = 0; } Matrix(const Matrix &a) :size(a.size) { buf = new int[size*size]; matrix = new int* [size]; for(int i=0; i<size; i++) matrix[i] = &buf[i*size]; for(int i=0; i<size; i++) for(int j=0; j<size; j++) matrix[i][j] = a.matrix[i][j]; } ~Matrix() { delete [] matrix; delete [] buf; } Matrix &operator=(const Matrix &a) { if(a.size!=size) { delete [] matrix; delete [] buf; size = a.size; buf = new int[size*size]; matrix = new int* [size]; for(int i=0; i<size; i++) matrix[i] = &buf[i*size]; } for(int i=0; i<size; i++) for(int j=0; j<size; j++) matrix[i][j] = a.matrix[i][j]; return *this; } Matrix &clockwise90(); private: int **matrix; int *buf; // 2D matrix stored in 1D raster scan order int size; }; //end class Matrix #endif /* function_h */

main.cpp

#include <iostream> #include "function.h" using namespace std; int main() { int matrix_size; cin>>matrix_size; Matrix a(matrix_size); cin>>a; cout<<endl; cout<<a.clockwise90().clockwise90()<<endl; cout<<a<<endl; return 0; } // end main

 

2. For OJ submission:

       Step 1. Include function.h into function.cpp and then implement your function.cpp. (You don’t need to modify function.h and main.cpp)

       Step 2. Submit the code of function.cpp into submission block.

       Step 3. Check the results and debug your program if necessary.

 

Input

The first line has an integer N (1<=N<=50), which means the size of the matrix. The total number of elements in the matrix is thus N * N.

 

For the next N lines specify the elements of the matrix a. All of the integers in the same line are separated by a space.

Output

Your program should print the corresponding results followed by a new line character.

Sample Input  Download

Sample Output  Download

Partial Judge Code

11023.cpp

Partial Judge Header

11023.h

Tags

Discuss