如何在C++中對以下字符串序列進行排序？

所以，我正在解決一個問題，它涉及到排序由開放和關閉括號組成的適當字符串的給定序列。 n個圓括號序列由n和n組成，其中n爲"("和n爲")"。如何在C++中對以下字符串序列進行排序？

有效的括號序列定義如下：

你可以找到一種方法來消除重複相鄰的一對括號"()"，直到它變空。

例如，"(())"是一個有效的括號，您可以在第二和第三個位置擦除該對，然後它變爲"()"，然後您可以將其設置爲空。 ")()("不是有效的括號。現在，我想知道如何對給定長度的括號生成的序列進行排序，以使那些具有最大開放括號的字符串開始出現，並且如果兩個字符串在開始時具有相同數量的開頭括號，則在遍歷首先打印帶有第一個開口支架的琴絃。例如，對於n=3，排序順序將是

((())) // 3 opening in a row and hence first 

(()()) // 2 opening (same as the one which is below this one) but has a opening bracket first 

(())() 

()(()) 

()()()

來源

2015-08-22 John Lui

做這些字符串包含括號比其他東西嗎？ – Galik

不。這些字符串只包含pamentalhesis。 –

我想你只需要定義一個順序並找出當前字符串的排列方式。然後使用該數字進行排序。 –

您可以使用標準的排序算法，std::sort

默認（辭書）訂貨會實現你想要什麼。

來源

2015-08-22 08:09:08

我可能會錯過一些東西，但我認爲直接排序會起作用。它有點像二進制數字，除了'('和')'而不是1 s和0 s。

#include <random> 
#include <string> 
#include <vector> 
#include <iostream> 
#include <algorithm> 

std::vector<std::string> tests = 
{ 
    "((()))", 
    "(()())", 
    "(())()", 
    "()(())", 
    "()()()" 
}; 

int main() 
{ 
    std::shuffle(tests.begin(), tests.end(), 
     std::default_random_engine(std::random_device{}())); 

    std::cout << "\nbefore:\n"; 
    for(auto const& s: tests) 
     std::cout << s << '\n'; 

    // normal sort 
    std::sort(tests.begin(), tests.end()); 

    std::cout << "\nafter:\n"; 
    for(auto const& s: tests) 
     std::cout << s << '\n'; 
}

輸出示例：

before: 
(()()) 
(())() 
()()() 
((())) 
()(()) 

after: 
((())) 
(()()) 
(())() 
()(()) 
()()()

來源

2015-08-22 08:25:48 Galik

如何在C++中對以下字符串序列進行排序？

回答

相關問題