PTIT123A - Sắp xếp 2

Link Sub: https://www.spoj.com/PTIT/problems/PTIT123A/
Người Gửi: Dương Lee

• Problem:

Cho một danh sách chứa cả các số và các từ. Yêu cầu bạn hãy sắp xếp danh sách này tăng dần sao cho các từ theo thứ tự từ điển, các số theo thứ tự số. Hơn nữa, nếu phần tử thứ n là số thì danh sách sau khi sắp xếp phần tử thứ n cũng phải là số, nếu là từ thì vẫn là từ.
Lưu ý: Các từ chỉ gồm các chữ in thuờng trong bảng chữ cái tiếng Anh.

Input

Gồm nhiều dòng, mỗi dòng là một danh sách. Mỗi phần tử của danh sách cách nhau bởi dấu phẩy (“,”) theo sau là dấu cách, và danh sách được kết thúc bằng dấu chấm (“.”).  
Dữ liệu kết thúc bởi dòng chỉ chứa một dấu chấm.

Output

Với mỗi danh sách trong dữ liệu, xuất ra danh sách đã sắp xếp thỏa mãn yêu cầu đề bài (có định dạng như trong dữ liệu).

Example:

Input

0.
banana, strawberry, orange.
banana, strawberry, orange.
10, 8, 6, 4, 2, 0.
x, 30, -20, z, 1000, 1, y.
50, 7, kitten, puppy, 2, orangutan, 52, -100, bird, worm, 7, beetle.
.

Output:

0.
banana, orange, strawberry.
banana, orange, strawberry.
0, 2, 4, 6, 8, 10.
x, -20, 1, y, 30, 1000, z.
-100, 2, beetle, bird, 7, kitten, 7, 50, orangutan, puppy, 52, worm.

• Solution:

- Bài này bạn cần phải lưu lại vị trí nào là số, vị trí nào là từ. Sau đó tách các từ, các số riêng biệt ra và sắp xếp chúng.
- Cuối cùng là chỉ việc in theo đúng thứ tự số và từ.
(code dưới đây dùng stack để tách từ và số)

• Code:

C++:

https://ideone.com/ZT55Xq

#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;

string str;
void read()
{
    getline (cin, str);
}

vector <int> isNumber;
vector <string> words;
vector <int> numbers;

void init()
{
    isNumber.clear();
    words.clear();
    numbers.clear();
}

int StringToNum (string x)
{
    int f = 0;
    if (x[0]=='-')
       f = 1;
    int S = 0;
    for (int i=f; i<x.length(); i++)
    {
        S=(S*10)+(x[i]-'0');
    }
    if (f==1) return 0-S;
    return S;
}

void separation()    //Tach string thanh cac thanh phan rieng biet
{
    stack<string> st;
    for (int i=str.length()-1; i>=0; i--)
    {
        if (str[i]==',' || str[i]=='.')
        {
            st.push("");
        }
        else if (str[i]!=' ')
        {
            string top = st.top();
            st.pop();
            top=str[i]+top;
            st.push(top);
        }
    }
    while (!st.empty())
    {
        string top = st.top();
        st.pop();
        if (top[0]=='-' || (top[0]>='0' && top[0]<='9'))
        {
            numbers.push_back(StringToNum(top));
            isNumber.push_back(1);
        }
        else
        {
            words.push_back(top);
            isNumber.push_back(0);
        }
    }
}

void Sort()
{
    sort(numbers.begin(), numbers.end());
    sort(words.begin(), words.end());
}

void Print()
{
    int vN = 0;
    int vW = 0;
    for (int i=0; i<isNumber.size()-1; i++)
    {
        if (isNumber[i]==1)
        {
            cout<<numbers[vN]<<", ";
            vN++;
        }
        else
        {
            cout<<words[vW]<<", ";
            vW++;
        }
    }
    if (isNumber[isNumber.size()-1]==1)
    {
        cout<<numbers[vN]<<".";
        vN++;
    }
    else
    {
        cout<<words[vW]<<".";
        vW++;
    }
    cout<<endl;
}

int main ()
{
    while (1)
    {
        read();
        if (str==".") break;
        init();
        separation();
        Sort();
        Print();
    }
    return 0;
}

JAVA:

...

Python:

...

Author : DL

Share this

Related Posts