#cpp #алгоритм
Название, может, криво написал, лучше опишу задание.
Написать программу, которая в качестве аргумента командной строки принимает имя текстового
файла, содержащего элементы трёх видов:
+ <слово>
- <слово>
? <слово>
Элементы отделяются друг от друга одним или несколькими разделителями – пробелами,
табуляциями, символами новой строки. Слово с предшествующим плюсом добавляется в упорядоченный
динамический список, если его там ещё нет (в качестве функции сравнения слов использовать
лексикографическое сравнение). Если числу предшествует минус, то это слово удаляется
из списка (если оно было в нём). Если перед словом стоит вопрос, то оно печатается
в выходной поток в отдельной строке вместе со словом Yes или No в зависимости от того,
присутствует ли это слово в построенном на тот момент списке.
В общем, что мне удалось сделать.
#include
#include
#include
#include
#include
class Node
{
public:
char* data;
Node *next;
Node()
{
char* data = new char[30];
}
Node(char* element)
{
strcpy_s(data, 20, element);
next = NULL;
}
char *getdata()
{
return data;
}
};
class DynList
{
Node *head;
public:
DynList()
{
head = NULL;
}
~DynList()
{
Node *temp;
while (head != NULL)
{
head = head->next;
delete temp;
temp = head;
}
}
void AddFirst(DynList &l, char* element);
Node* Search(DynList &l, char* element);
void Delete(DynList &l, Node *temp);
};
void DynList::AddFirst(DynList &l, char* element)
{
Node *NewNode = new Node;
NewNode->data = element;
NewNode->next = NULL;
NewNode->next = l.head;
l.head = NewNode;
}
Node* DynList::Search(DynList &l, char* element)
{
while (head != NULL)
{
if (head->data = element)
return l.head;
l.head = l.head->next;
}
return l.head;
}
void DynList::Delete(DynList &l, Node *temp)
{
if (temp == l.head)
{
l.head = temp->next;
}
//рабоча¤ переменна¤-узел дл¤ движени¤ по списку
Node *r = new Node;
r = head;
while (r->next != temp)
{
r = r->next;
}
r->next = temp->next;
delete(temp);
}
int main()
{
char* element = new char[30];
DynList vars;
std::ifstream file("3.txt");
if (file.is_open() )
{
while (!file.eof() )
{
getline(file, element);
}
}
return 0;
}
Во-первых, компилятор (работаю в VS) ругается на getline. Можете помочь? Текстовые
данные у меня хранятся в таком виде:
+ The + donation + will + go + toward + the ? CDC - Global + Disaster + Response
Я хочу применить такой алгоритм:
Считываю слова из файла.
Далее прописываю условия, что если считывается один из символов-флагов ("+", "-",
"?"), то к следующему слову применяется соответствующая функция-метод класса.
Так вот, как мне обратиться к следующему после флага слову?
Ответы
Ответ 1
Или на Питоне:
#!/usr/bin/env python3
import fileinput
words = set() #NOTE: it is unordered but it doesn't affect the result
tokens = (token for line in fileinput.input() for token in line.split())
for op, word in zip(*[tokens]*2):
if op == '+':
words.add(word)
elif op == '-':
words.discard(word)
elif op == '?':
print(word, "Yes" if word in words else "No")
@VladD спросил:
А как функционирует *[tokens]*2
zip(*[iterator]*n) -- это (довольно непрозрачная, что необычно) идиома по обходу
итератора n элементов за раз. В официальной документации это itertools' grouper рецепт.
Смотри
What is the most “pythonic” way to iterate over a list in chunks? и Что значит *
(звёздочка) и ** двойная звёздочка в Питоне?
Основная идея в том, что zip() на каждом шаге вызывает next() функцию n раз на одном
и том же итераторе:
>>> from itertools import zip_longest
>>> for a, b, c in zip_longest(*[iter(range(10))]*3, fillvalue='default'):
... print(a, b, c)
...
0 1 2
3 4 5
6 7 8
9 default default
zip_longest() необходим только если кол-во элементов в итераторе не кратно n.
Итератор это простой объект, который генерирует элементы, если next() вызыван:
>>> it = iter(range(2))
>>> next(it)
0
>>> next(it)
1
>>> next(it)
Traceback (most recent call last):
File "", line 1, in
StopIteration
>>> next(it)
Traceback (most recent call last):
File "", line 1, in
StopIteration
Итератор можно пройти только один раз. Чтобы перезапустить обход, необходимо создать
новый итератор. (x*x for x in iterable) выражение возвращает итератор.
Ответ 2
Доброго времени суток!
Вот код, который решает Вашу задачу:
#include
#include
#include
#include
#include
#include
#define _DEBUG_OPS
enum operation
{
op_unknown = 0,
op_push = 1,
op_pop = 2,
op_show = 3
};
inline std::istream& operator>> (std::istream& stream, operation& op)
{
std::string s;
stream >> s;
if (s == "+") {
op = op_push;
return stream;
}
if (s == "-") {
op = op_pop;
return stream;
}
if (s == "?") {
op = op_show;
return stream;
}
op = op_unknown;
return stream;
}
typedef std::pair op_node;
typedef std::set string_set;
void execute_op(const op_node& n, string_set& s)
{
using std::cout;
using std::endl;
std::string str = n.second;
string_set::const_iterator it = s.find(str);
switch(n.first)
{
case op_push:
#ifdef _DEBUG_OPS
cout << "PUSH " << str << endl;
#endif
s.insert(str);
break;
case op_pop:
#ifdef _DEBUG_OPS
cout << "POP " << str << endl;
#endif
if (it != s.end()) {
s.erase(it);
}
break;
case op_show:
#ifdef _DEBUG_OPS
cout << "SHOW ";
#endif
cout << str << " "
<< (it != s.end() ? "YES" : "NO")
<< endl;
break;
case op_unknown:
default:
cout << "error: unknnown operation..." << endl;
exit(1);
}
}
int main()
{
using namespace std;
string_set strings;
op_node item;
ifstream input("input.txt");
if (!input) {
cout << "error: unable to read input..." << endl;
return 1;
}
string s;
while(input)
{
input >> item.first;
input >> item.second;
if (!input) { // End-Of-Stream
cout << "EOS" << endl;
break;
}
execute_op(item, strings);
}
// print out all strings in string set
#ifdef _DEBUG_OPS
copy(strings.begin(), strings.end(),
ostream_iterator(cout << endl, "\n"));
#endif
return 0;
}
Алгоритм следующий:
Читаем из входного потока оператор.
Читаем из входного потока строку.
Выполняем действие над строкой в соответствии с оператором.
Повторяем действия с 1-3, пока не конец потока.
Файл input.txt в моем случае имел такой вид:
+ The + donation + will + go + toward + the ? CDC - Global + Disaster + Response
- The
? The
? will
На выходе получился такой результат:
PUSH The
PUSH donation
PUSH will
PUSH go
PUSH toward
PUSH the
SHOW CDC NO
POP Global
PUSH Disaster
PUSH Response
POP The
SHOW The NO
SHOW will YES
EOS
Disaster
Response
donation
go
the
toward
will
Здесь для наглядности напечатано действие, производимое со строкой, а в конце напечатан
весь получившийся список слов. Чтобы отключить вывод на печать этой отладочной информации,
закомментируйте:
#define _DEBUG_OPS
Надеюсь, я правильно понял, что Вы хотели сделать, и Вам помог!
Если есть вопросы по коду, пишите в комментариях, хотя, на мой взгляд, все очевидно. )
Успехов!
Ответ 3
В качестве упорядоченного динамического контейнера можно использовать std::set, порекомендованный
@VladD в комментарии к вопросу.
skipws флаг (установлен по умолчанию) позволяет удобно считывать поля, разделённые
пробелом, c помощью operator>> (что такое пробел, может зависеть от локали, связанной
с потоком):
#include
#include
#include
#include
int main(int argc, char* argv[]) {
using namespace std;
if (argc != 2) {
cerr << "Usage: " << (argc > 0 ? argv[0] : "set-words") << " FILE\n";
return 2;
}
set words; // ordered set
ifstream file(argv[argc-1]);
for (string op, word; file >> op >> word; ) {
if (op == "+")
words.insert(word);
else if (op == "-")
words.erase(word);
else if (op == "?")
cout << word << " " << (words.count(word) ? "Yes": "No") << endl;
else {
cerr << "error: unexpected operator, got '" << op << "'\n";
return 1;
}
}
return !file.eof();
}
Код достаточно краток и прямолинеен. Можно добавить ещё сообщения об ошибках, чтобы
отличить ошибки ввода/вывода, например, ошибку открытия файла от ошибки чтения из файла.
Ответ 4
Вот полное решение на C#, для сравнения:
var pairs =
File.ReadLines(f)
.SelectMany(s => s.Split(null, StringSplitOptions.RemoveEmptyEntries))
.Batch(2, strings => new { op = string.First(), arg = strings.Last() });
var curr = new HashSet();
foreach (var pair in pairs)
switch (pair.op)
{
case "+": curr.Add(pair.arg); break;
case "-": curr.Remove(pair.arg); break;
case "?": Console.WriteLine(pair.arg + ": " + curr.Contains(pair.arg) ? "Yes" : "No");
break;
}
