Description

Caesar’s cipher is a substitution cipher. Given an integer (shift), each letter in the plaintext is replaced by a letter some fixed number of positions down the alphabet. For example, given shift = -3, C would be replaced by Z, D would be replaced by A, and so on. 

Example:

encoding for shift = -3

​

decoding for shift = -3

 

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 ‘CaesarCodec’. You are asked to implement the functions ‘encode’, ‘decode’ of ‘CaesarCodec’ in ‘function.cpp’.

 

 

 

Input

An uppercase string and a shift

Note:

1. The shift may be positive or negative.
2. The absolute value |shift| may be larger than 26.

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 fourth lines are Caesar encoding and decoding.

Each line is followed by a new line character.

 

 

Sample Input  Download

Sample Output  Download

Partial Judge Code

11449.cpp

Partial Judge Header

11449.h

Tags

Discuss

Description

In this problem, you are asked to implement a linked list based binary search tree. In addition, you are also asked to implement a linked list based stack, so that the program can use a stack to print its corresponding binary search tree in the depth-first manner.

 

A. Implementation of the BST Data Structure using a 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.

For example, 

The linked list will be 

 

B. The relationship between a BST and its corresponding Stack

For printing the tree in the depth-first manner, the ListBST::printDFS needs to push and pop the tree nodes to/from a stack.

 

Example:

initially,

after push(root),

 

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. You are asked to implement

• void ListBST::insert(const int &key)
• bool ListBST::search(const int &key) const
• void Stack::push(ListNode *p)
• ListNode *Stack::pop()

 

3. ListNode is a ListBST’s node and Element is a Stack’s node whose data is a pointer to ListNode.

 

4. 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(A>0) 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.
• “D”: show the current content of the BST by DFS.
• “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

11451.cpp

Partial Judge Header

11451.h

Tags

Discuss

Description

In this problem, we define a custom string that is a list linking some nodes.

The involved classes are explained as follows.

 

A. Definition of class Node

• An abstract base class that declares pure virtual func() and clone() methods
• clone() will return a new object according to its derived class
• Has a pointer (next)

B. Definition of class CharNode

• A derived class of Node
• Contains a char (text)
• func() outputs “text”

C. Definition of class RepeatNode

• A derived class of Node
• Contains an integer (times)
• If next != NULL, func() will call next->func() “times” times.

​D. Definition of class Str

• Maintain a list of some Nodes
• Can access the Node by index
• Can attach a Node
• Can return how many Nodes it contains by length()

​

Note:

You are asked to implement

• void CharNode::func()
• void RepeatNode::func()
• Str::Str(const Str &s)
• void Str::attach(Node *ptr)
  • Attach the input Node to the end of Str
  • Note: you can simply assign ptr to tail->next if the Str is not empty
• int Str::length()
• Node *Str::operator[](int idx)
  • Return the address of the idx-th Node

 

 

Input

First part

An integer n that means the number of Strs.

And then, n lines that are the inputs of Strs.

 

Second part

Four kinds of commands.

• c n m: delete m-th Str and copy n-th Str to position m
• a n l m: duplicate the l-th Node of n-th Str and attach it to the end of m-th Str
• s m: show m-th Str
• l m: output the length of m-th Str

 

 

Output

The output depends on the commands.

 

 

Sample Input  Download

Sample Output  Download

Partial Judge Code

11452.cpp

Partial Judge Header

11452.h

Tags

Discuss

Description

In this problem, students can use accounts to take online courses.

The program architecture is explained as follows.

 

A. Definition of class Student

• An abstract base class that declares pure virtual learn() method
• Has a string (note) used to record what the student learns
• Derived classes
  • InterestedStudent
    • Just note the latest thing
  • StrivingStudent
    • Note everything learned

 

B. Definition of class Account

• A node of doubly linked list

 

C. Definition of class OnlineCourse

• An abstract base class that declares pure virtual material() method
• Operator+= means login
  • A student can use an account to login an online course.
• Operator-= means logout
  • If a student has been taking an online course, he/she can logouts the online course.
• Derived classes
  • Math
    • The input will be a pre-order expression with +, -, *, /
    • material() method has to return the answer of the expression
  • English
    • The input will be a string
    • material() method has to separate the characters of the input string by new lines if a next character is uppercase

 

You are asked to implement

• void InterestedStudent::learn(const string &str)
  • The Student learns the material by saving the input str to the note.

• void StrivingStudent::learn(const string &str)

  • Note: if he/she learns something, you need to attach a new line and then the new material to the “note”.

• void OnlineCourse::operator+=(Student *s)

  • create an Account for the Student and insert the Account to the doubly linked list.

  • Note:

    • A student cannot login a same course for more than one time.

    • But a student can logout a course, and then login again.

• void OnlineCourse::operator-=(Student *s)

  • remove the Account for the Student from the doubly linked list and then delete the Account.

• string Math::material(istream &input)

• string English::material(istream &input)

  • Note: you don’t need to insert a new line before the first character, even if it’s uppercase.

 

 

Input

First line contains an integer n and n types from {m, e}

• Integer n means n online courses
• type m means Math
• type e means English

Second line contains an integer m and m types from {i, s}

• integer m means m students
• type i means InterestedStudent
• type s means StrivingStudent

and then, there are 4 kinds of commands

• i n m:

m-th student logins n-th course

• o n m:

m-th student logouts n-th course

• u n:

there are new input for n-th course

• s m:

show the note of m-th student

 

 

Output

the output depends on the input commands.

 

 

Sample Input  Download

Sample Output  Download

Partial Judge Code

11453.cpp

Partial Judge Header

11453.h

Tags

Discuss

Description

Array.cpp
// overloaded assignment operator;
// const return avoids: ( a1 = a2 ) = a3
const Array &Array::operator=( const Array &right )
{
   if ( &right != this ) // avoid self-assignment
   {
      // for Arrays of different sizes, deallocate original
      // left-side Array, then allocate new left-side Array
      if ( size != right.size )
      {
         delete [] ptr; // release space
         size = right.size; // resize this object
         ptr = new int[ size ]; // create space for Array copy
      } // end inner if

      for ( size_t i = 0; i < size; ++i )
         ptr[ i ] = right.ptr[ i ]; // copy array into object
   } // end outer if

   return *this; // enables x = y = z, for example
} // end function operator=

// determine if two Arrays are equal and
// return true, otherwise return false
bool Array::operator==( const Array &right ) const
{
   if ( size != right.size )
      return false; // arrays of different number of elements

   for ( size_t i = 0; i < size; ++i )
      if ( ptr[ i ] != right.ptr[ i ] )
         return false; // Array contents are not equal

   return true; // Arrays are equal
} // end function operator==

// overloaded subscript operator for non-const Arrays;
// reference return creates a modifiable lvalue
int &Array::operator[]( int subscript )
{
   // check for subscript out-of-range error
   if ( subscript < 0 || subscript >= size )
      throw out_of_range( "Subscript out of range" );

   return ptr[ subscript ]; // reference return
} // end function operator[]

// overloaded subscript operator for const Arrays
// const reference return creates an rvalue
int Array::operator[]( int subscript ) const
{
   // check for subscript out-of-range error
   if ( subscript < 0 || subscript >= size )
      throw out_of_range( "Subscript out of range" );

   return ptr[ subscript ]; // returns copy of this element
} // end function operator[]

// overloaded input operator for class Array;
// inputs values for entire Array
istream &operator>>( istream &input, Array &a )
{
   for ( size_t i = 0; i < a.size; ++i )
      input >> a.ptr[ i ];

   return input; // enables cin >> x >> y;
} // end function

// overloaded output operator for class Array
ostream &operator<<( ostream &output, const Array &a )
{
   // output private ptr-based array
   for ( size_t i = 0; i < a.size; ++i )
   {
      output << setw( 12 ) << a.ptr[ i ];

      if ( ( i + 1 ) % 4 == 0 ) // 4 numbers per row of output
         output << endl;
   } // end for

   if ( a.size % 4 != 0 ) // end last line of output
      output << endl;

   return output; // enables cout << x << y;
} // end function operator<<

Inheritance type	Public	Protected	Private
Public data/ functions in the base class	Public in the derived class	Protected in the derived class	Private in the derived class
Protected data/ functions in the base class	Protected in the derived class	Protected in the derived class	Private in the derived class
Private data/fun in the base class	Not accessible in the derived class	Not accessible in the derived class	Not accessible in the derived clas

 
 
 
 
 
 

 

 

 

 

 

Polymorphism
  In the base class
  virtual void foo();
  In the derived class
  virtual void foo() override;

Abstract class and pure virtual function
  virtual void foo() =0;

Prefix/postfix operators
  complex &operator++();  // prefix
  complex operator++(int); // postfix

Operator overloading
  Binary operators
  /*1.non-static member function */
     complex operator+ (const complex&);
  /* 2. non-member function */
     friend complex operator* (const
                      complex&, const complex&);
  Unitary operators
  /*1.non-static member function */
      complex operator-();
  /*2. non-member function */
      friend complex operator~(const complex&);

Inheritance
  class A {
  // A is a base class }
  class B: public A {
  // B inherits A.
  // B is a derived class}

Dynamic allocation
  int *ptr = new int;
  delete ptr;
  int *ptr = new int[100];
  delete [] ptr;

String object
  #include<string>
  using namespace std;
  ...
  string str1 = "Hello";
  string str2 = "World";

Standard C++ Library - <string>

operator[]	For string a, a[pos]: Return a reference to the character at position pos in the string a.
operator+=	Append additional characters at the end of current string.
operator+	Concatenate strings.
operator<	Compare string values. For string a and b, a < b: if a is in front of b in dictionary order, return 1, else return 0.
operator>	Compare string values. For string a and b, a > b: if a is in back of b in dictionary order, return 1, else return 0.
operator==	Compare string values. For string a and b, a == b: if equal, return 1, else return 0;
operator!=	Compare string values. For string a and string b, a != b: if not equal, return 1, else return 0;
compare()	Compare string. For string a and b, a.compare(b): if equal, return 0. If string a is in front of string b in dictionary order, return -1. If string a is in back of string b in dictionary order, return 1.
length()	Return length of string.
swap()	Swap string values.
push_back()	For string a, a.push_back(c): append character c to the end of the string a, increasing its length by one.

 

Standard C++ Library - <sstream>

operator<<	Retrieves as many characters as possible into the stream.
operator>>	Extracts as many characters as possible from the stream.
str	Returns a string object with a copy of the current contents of the stream.

For example(1):
stringstream ss{“Hello”};    // constructor
string str = ss.str();    // a = “Hello”

For example(2):
stringstream ss;
ss<<”75”;
ss<<”76”;
int num;
ss>>num;    // num = 7576

Input

Output

Sample Input  Download

Sample Output  Download

Tags

Discuss