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 ‘3A7DBB5GC4E’, because there are three A’s, seven D’s, … etc. Note that we do not need to encode runs of length one or two, since ‘2B’ and ‘1C’ are not shorter than ‘BB’ and ‘C’.

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

void RleCodec::encode() { // Your code here encoded = true; } void RleCodec::decode() { //No cheating : ) }

 

 

Input

A line contains of several characters .

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

11014.cpp

Partial Judge Header

11014.h

Tags

Discuss

Description

If you are not familiar with partial judge , please check this handout

---

A. Definition of Binary Search Trees

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.

Based on the above property of BSTs, when a node is to be inserted into an existing BST, the location for the node can be uniquely determined. For example, if a node with key 6 needs to be inserted into the following BST

the BST will become

 

B. Implementation of the BST Data Structure

There are two approaches to BST implementation: array and linked list.

1. Array:

An approach to storing a BST is to use a single, contiguous block of memory cells, i.e., an array, for the entire tree. We store the tree’s root node in the first cell of the array. (Note that, for ease of implementation, we ignore the 0th cell and start from the 1st cell.) Then we store the left child of the root in the second cell, store the right child of the root in the third cell, and in general, continue to store the left and right children of the node found in cell n in the cells 2n and 2n+1, respectively. Using this technique, the tree below

would be stored as follows

 

2. Linked list:

We set a special memory location, call a root pointer, where we store the address of the root node. Then each node in the tree must be set to point to the left or right child of the pertinent node or assigned the NULL value if there are no more nodes in that direction of the tree.

 

C. Detailed C++ Implementation for BST

Let’s see how the BST data structure can be realized in C++.We have two different approaches to BST implementation: array and linked list. Thus, we define four 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 bool search(const int &) const = 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 Array_BST : public BST{ public: Array_BST(); virtual ~Array_BST() {} virtual void insert(const int &) override; //root node is stored at index 1. virtual bool search(const int &) const override; virtual void print() const override{ int k = pow(2, height()); for (int i = 1; i <= k-1; i++) { if (array[i] != 0) cout << array[i] << " "; } } private: int array[1025]; }; 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(); virtual ~List_BST() { deleteTree(root); } virtual void insert(const int &) override; virtual bool search(const int &) const override; virtual void print() const override{ int i; for(i = 1; i <= Height; i++){ printGivenLevel(root, i); } } private: ListNode *root; // private member functions ListNode* createLeaf(int key) const; //new a ListNode and return its address /* clean a tree.*/ void deleteTree(ListNode *root); void printGivenLevel(ListNode* Ptr, int level) const { if (Ptr == NULL) return; if (level == 1) cout << Ptr->key << " "; else if (level > 1) { printGivenLevel(Ptr->left, level-1); printGivenLevel(Ptr->right, level-1); } } }; #endif /* function_h */

main.cpp

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

REQUIREMENTS:

Implement the constructor, insert(), search() member functions of both the Array_ BST and List_ BST classes and createLeaf(), deleteTree() of 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 four kinds of commands:

• “I A”: insert a node with int value A into the BST
• “S A”: if the integer A exists in the BST, print “yes”; otherwise, print “no”.
• “P”: show the current content of the BST.
• “H”: print the BST’s height.

Each command is followed by a new line character.

Input terminated by EOF.

Output

The output shows the result of each command.

When the BST is empty, you don’t need to print anything except a new line character.

Sample Input  Download

Sample Output  Download

Partial Judge Code

11020.cpp

Partial Judge Header

11020.h

Tags

Discuss

Description

If you are not familiar with partial judge , please check this handout

 

 

Implement a Vector class that support n-dimensional vector add, subtract and dot product.

Your task is to complete

• const int size() const;
• Vector operator+(const Vector& a);
• Vector operator-(const Vector& a);
• const int operator[](int index) const;
• int operator*(const Vector& a);

inside the Vector class, and std::ostream& operator<<(std::ostream& os, const Vector& v);

Remember to #include "function.h"!

Input

First line of input is an integer m, where m is the number of testcases.There are m testcases following.

A testcases consists of three lines:

• In the first line of each testcase, there are a string OP and an integer n, where OP is the operation and n is the vector size.
• In the second line of each testcase, there are n integers, representing all the elements inside the first vector, A.
• In the third line of each testcase, there are n integers, representing all the elements inside the second vector, B.

It is guaranteed that:

• 1 ≤ m ≤ 100, 1 ≤ n ≤ 300
• For all the elements x in vector A and B, |x| ≤ 100

Output

For each testcase, according to its operation, output the result of A+B, A-B or A*B. There is a space after every number.

Sample Input  Download

Sample Output  Download

Partial Judge Code

11915.cpp

Partial Judge Header

11915.h

Tags

Discuss

Description

Maintain a doubly linked list, which supports the following operations:

(1) IH i : Insert a new integer i to the head of the list.

(2) IT i : Insert a new integer i to the tail of the list.

(3) RH : Print and remove the element in the head of the list. If the list is empty, print a blank line.

(4) RT : Print and remove the element in the tail of the list. If the list is empty, print a blank line.

(5) S : Swap the first floor(k/2) elements and the last k - floor(k/2) elements, where k is the total number of elements in the list. For example, if k = 5, the result of swapping a1, a2, a3, a4, a5 will be a3, a4, a5, a1, a2.

To improve the performance, it is suggested that three pointers be maintained in case4: head, tail and middle, where middle points to the floor(k/2) + 1-th element. With the help of these pointers, all of the operations can be done in constant time.

Input

There is only a single set of input and each operation will occupy a line. There will be a space between “IH” and “i”, and “IT” and “i”. The input contains OP operations, and it is terminated by end-of-file (EOF). You may assume that i is a nonnegative integer not greater then 100000. The list is initially empty.
For case1 and case2, 1<=OP<=1000
For case3, 1<=OP<=10000, For each S operation, O(n) is also accepted.
For case4 and case5, 1<=OP<=500000, each operation should be done in O(1).

Output

For each “RH” or “RT” operation, print a line containing the removed integer as commanded by the operation.
For RH and RT operation: if the list is empty, print a blank line.

Sample Input  Download

Sample Output  Download

Partial Judge Code

12224.cpp

Partial Judge Header

12224.h

Tags

Discuss

Description

A teacher creates a list to store students' information. Inside this list, each student's name and ID are recorded.

Please write a program to help the teacher.

The program are required to support following features:

1. Show all the names in the list.
2. Show all the IDs in the list.
3. Add a student to the end of the list.
4. Duplicate a student's info, and append to the end of list.
5. Delete an entry from list.

Note that there could be multiple same records in the list.

*To this program works normally, please use C++11 or above for compilation.

Input

First line of input contains an integer K (K < 100).

Each of the following K lines is an operation. Operations will be one of the following form:

1. "0": show all names in the list
2. "1": show all IDs in the list
3. "2 <name> <id>": add a student with name=<name> and id=<id> to the end of the list. The length of name is less than 100, and the length of id is less than 10.
4. "3 <idx>": duplicate the information of idx-th entry in the list (append the duplicated information to the end of the list).
5. "4 <idx>": remove the information of idx-th entry in the list.

*All the input processing have been handled by the provided code.

Output

For operation 0 and 1, print out the corresponding information.

Sample Input  Download

Sample Output  Download

Partial Judge Code

12255.cpp

Partial Judge Header

12255.h

Tags

Discuss

Description

"Cat or Dog? that's a good question. " Shakespeare never said, 2019.

In this questions there are three types of animals class have to be implemented. (Cat , Dog and Caog)
Coag is a kind of special animal mixed in Cat and Dog.

Dog can only throwball
Cat can only play with carton.
Caog do those things both.

when Dog / Caog playing throwball output "it looks happy!\n"

when Cat  / Caog playing with carton output "it looks so happy!\n"

and also there's a zoo can count how many animals are in the zoo.

In this questions you have to implement 3 class (cat , dog and caog) based on the sample code.

Input

All input data would be finish in given main functions.

First number N would be N animals ( N < 10)

the following Ai numbers would types of animals.

And the T would be T instructions ( T < 30) 

the following Ti would be index and instructions

 

Output

 

When Animals born Zoo will auto output which kind of animal is born and how many animals in the zoo.

When Animals dead Zoo will auto output which kind of animal isdeadand how many animals in the zoo.

when Dog / Caog playing throwball output "it looks happy!\n"

when Cat  / Caog playing with carton output "it looks so happy!\n"

when Barking:

Cat would "meow!\n"

Dog would "woof!\n"

Caog would "woof!woof!meow!\n"

Sample Input  Download

Sample Output  Download

Partial Judge Code

12257.cpp

Partial Judge Header

12257.h

Tags

Discuss

Description

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

 

Provide public member functions that perform or derive:

     1) Matrix(const Matrix &);  // copy constructor

 

     2) 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.)

 

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

 

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

 

     5)  Default constructor

 

    6)  Destructor

 

    7)  Overload the operator (=) to assign value to matrix.

         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 

 

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

12273.cpp

Partial Judge Header

12273.h

Tags

Discuss