Description

A stack is an abstract data type that serves as a collection of elements, where a node can be added to a stack and removed from a stack only at its top. Two principal operations can be used to manipulate a stack: push, which adds an element at the top, and pop, which removes the element at the top of the collection.

Let’s see how the stack data structure can be realized in C++.We have an approach to implement stack: linked list. Thus, we define a class as follows:

class List_stack {

    public:

        List_stack();

        ~List_stack();

        void push(const int &);

        void pop();

        void print();

    private:

        ListNode *head;

        ListNode *tail;

};

where List_stack implements the stack data structure

 

REQUIREMENTS:

Implement the constructor, destructor, push(), pop() and print() member functions of List_stack classes.

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.

function.h

#ifndef FUNCTION_H #define FUNCTION_H #include <iostream> class ListNode { friend class List_stack; //make List_stack a friend public: ListNode( const int &info ) //constructor : data( info ), nextPtr( NULL ), prevPtr( NULL ) { } //end ListNode constructor private: int data; //data ListNode *nextPtr; // next node in list ListNode *prevPtr; }; //end class ListNode class List_stack { public: List_stack(); ~List_stack(); void push(const int &); void pop(); void print(); private: ListNode *head; ListNode *tail; }; #endif // FUNCTION_H

main.cpp

#include<iostream> #include<string.h> #include "function.h" using namespace std; int main(){ List_stack L_stack; char command[10]; int n; while(cin>>command){ if(strcmp(command,"pop")==0){ L_stack.pop(); }else if(strcmp(command,"push")==0){ cin >> n; L_stack.push(n); }else if(strcmp(command, "print") == 0){ L_stack.print(); cout << endl; } } return 0; }

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:

• “push integerA” represents adding an element with int value A at the top of the stack.
• “pop “ represents removing the element at the top of the stack.
• “print” represents showing the current content of the stack.

Each command is followed by a new line character.

Input terminated by EOF.

Output

The output should consist of the current state of the stack.

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

Sample Input  Download

Sample Output  Download

Partial Judge Code

10998.cpp

Partial Judge Header

10998.h

Tags

Discuss

Description

Warning: You are not allowed to use malloc and free

Giving a bass-class Shape3D and 4 derived class : Sphere （球體）, Cone （圓錐）, Cuboid （長方體）, Cube （立方體）

You need to calculate the volume of each shape.

PS:

V of Sphere: V = 4/3 π r³

V of Cone: V = 1/3 π r² h

 

note : Remember to do some basic check, if the input is illegal (e.g.  length < 0, pi < 0 .....)  then the volume should be 0.

You don't need to consider the scenario like Cuboid -1 -2 3, volume would be 0 instead of 6.

Hint1: Be careful the type of volume is double.  4/3=1 (int),  so it should be 4.0/3.0

Hint2: You only need to implement the constructors.

Hint3: Note that Cube inherited Cuboid not Shape3D.

 

 

Input

There are only 4 shapes in this problem :

• Sphere, following by its radius and pi. (e.g. Sphere 30 3.14)
• Cone, following by its radius of bottom plane, height and pi. (e.g. Cone 3 100 3.14)
• Cuboid, following by its length, width and height. (e.g. Cuboid 2 3 7)
• Cube, following by its length. (e.g. Cube 2)

Output

Ouput the total volume of all the shapes.

Sample Input  Download

Sample Output  Download

Partial Judge Code

11443.cpp

Partial Judge Header

11443.h

Tags

Discuss

Description

Array vs. Linked List

Array is a basic and fundamental concept in C/C++. It is a series of data which is arranged continiously in the memory space and can be accessed by index. Array is fast for indexing (using the given index to access the certain data), because the memory address of the destination can be calculated quickly. However, the capacity of the array is fixed after the declaration.

In I2PI (introduction of programming 1), we introduce a data structure called "linked list" which supports appending and deleting elements dynamically. The elements are stored in a series of "nodes", where each node points to the address of the next node. It is fast at appending elements but slow at indexing. To access the item of index i, you need to move i steps from head to obtain it.

Dynamic Array

In this problem, we will introduce a new data structure called "dynamic array" (abbreviated to "Darray" in the following statement) which supports dynamic capacity and indexing. We targeted to a simple Darray which has the following three variables

1. size : the number of elements stored in the array
2. capacity : the maximum number of elements which can be stored in the array
3. *data : the pointer which stores the address of the array

and two operations

1. pushback: append an element to the back
2. indexing : access the data by the given index.

To understand the concept of size and capacity, consider an array declaration:

 At first, the capacity is 5, but the size is 0 because no data is stored inside the array. Next, we push 5 elements to the array:

the capacity is still 5 but the size changes from 0 to 5. Therefore, no element can be appended to the array.

If we still want to append additional elements, we'll allocate a new array space with the double capacity and copy the data from old array to the new one. Note that the old array should be freed to avoid memory leak.

In this case, the capacity becomes 10 and the size is 6.

Implementation

You should implement the following functions based on the description above:

1. int& operator[](int): access data like using array. Users and main.cpp should/will not access the index which is greater or equal to size.
2. void pushback(int x): append the element x
3. void clear(void): clear the array (set size to 0) so that the next pushbacks will place elements in data[0],data[1] and so on.
4. int length(void): return the current size.
5. void resize(void): double the capacity and copy the data.
6. ~Darray(): destructor

Note that main.cpp acts like a functional tester for your Darray. There's no need to understand it. You should test your Darray by yourself.

More Notes: Time Complexity of Dynamic Array

Although it seems that copying the whole array will make dynamic array slow, we will analyze the time complexity to show that dynamic array is fast. Recall what Big-O Notation is where we introduced it in "The Josephus problem". O(2n+100)=O(2n)=O(n) means that the operation takes about n steps while O(2)=O(1) takes "constant" time. For array operations, we wish to have O(1) of indexing and pushback. In the following analysis, we will evaluate the amortized time complexity, which can be comprehended as calculating the average time complexity instead of the complexity of total operations.  Amortized time complexity = (complexity of total operations) / (number of operations).

Suppose that C₀ is the initial capacity and n is the number of operation of pushback. We discuss the time complexity in several cases:

1. Expand 0 time, n <= C₀.
   Since there's no expand operation, the total time complexity is O(1)*n=O(n). The amortized time complexity is O(n)/n=O(1).
2. Expand 1 time, C₀ < n <= C₁, C₁ = 2*C₀.
   Push C₀ items to array: O(C₀)
   Expand and copy: O(C₀), since there're C₀ elements to be copied.
   Push n-C₀ items to array: O(n-C₀)
   The total time complexity is O(C₀)+O(C₀)+O(n-C₀) = O(n+C₀). Since C₀ < n <= C₁, O(2C₀) < total time complexity <= O(3C₀). The amortized time complexity ranges in [O(3/2), O(2)). We identify it by the upper bound : O(2).
3. Expand 2 times, C1 < n <= C2, C2 = 2*C1.
   The amortized time complexity should be O(3). You can verify it by your own.

From the above analysis, if it expand i times, the amortized time complexity for appending an element is O(i+1). However, i won't be very large because the capacity grows exponentially so that we often regard the complexity as O(1), or, constant time. For instance, C₀=100, after expanding 20 times, the capacity will be 100*2²⁰≈10⁸.

---

 

Input

This is handled by the main function.

Output

This is handled by the main function.

Sample Input  Download

Sample Output  Download

Partial Judge Code

13520.cpp

Partial Judge Header

13520.h

Tags

Discuss

Description

Your task is to create a basic fraction calculator that can handle both addition and multiplication of fractions.

Since you should perform multiplication operations before addition, in the provided code, you are advised to use a structure called "FractionList", which functions similarly to a linked list. When performing an addition, add the new fraction to the end of the list. For multiplication, simply multiply the new fraction with the last one already in the list.

This is a partial judge problem. You need to implement 11 class methods. Please review the provided code and refer to the sections labeled "TODO" in the function.h file for further details.

Important: Please select C++17 to submit your solution.

 

Input

The input consists of multiple lines, where each line represents a test case.
Each test case contains a sequence of fractions and operations formatted as follows:

<fraction_1> +/* <fraction_2> +/* ... +/* <fraction_n> = ?  (1 < n ≤ 10)

Each fraction is written in the format <numerator>/<denominator>, where both numerator and denominator, as well as all numbers involved in calculations, fit within the range of a long long data type. The operations between fractions are either addition (+) or multiplication (*).

>>> Notice. Please note that the number of test cases in this problem is not specified. The program should continue reading input until no more input is available. When implementing the extraction operator (>>) for Fraction class, handle the situation where there is no input by simply returning the "istream".

Output

(This part is already implemented) For each test case, you should provide the result in two formats. First, output the result as a simplified fraction, where the fraction is reduced to its lowest terms. Second, present the result as a decimal number, cutting off the output after 20 decimal places without rounding up or down.

Special conditions for output formatting:

• If the result is 0, output should be formatted as: 0/1 0.00000000000000000000
• If the result is an integer (e.g., 3), output should be formatted as: 3/1 3.00000000000000000000

 

Sample Input  Download

Sample Output  Download

Partial Judge Code

14279.cpp

Partial Judge Header

14279.h

Tags

Discuss