4

Название, может, криво написал, лучше опишу задание.

Написать программу, которая в качестве аргумента командной строки принимает имя текстового файла, содержащего элементы трёх видов:

+ <слово>
- <слово>
? <слово>

Элементы отделяются друг от друга одним или несколькими разделителями – пробелами, табуляциями, символами новой строки. Слово с предшествующим плюсом добавляется в упорядоченный динамический список, если его там ещё нет (в качестве функции сравнения слов использовать лексикографическое сравнение). Если числу предшествует минус, то это слово удаляется из списка (если оно было в нём). Если перед словом стоит вопрос, то оно печатается в выходной поток в отдельной строке вместе со словом Yes или No в зависимости от того, присутствует ли это слово в построенном на тот момент списке.

В общем, что мне удалось сделать.

#include <fstream>
#include <cstdlib>
#include <iostream>
#include <string>
#include <stdio.h>

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. Считываю слова из файла.
  2. Далее прописываю условия, что если считывается один из символов-флагов ("+", "-", "?"), то к следующему слову применяется соответствующая функция-метод класса.

Так вот, как мне обратиться к следующему после флага слову?

αλεχολυτ
  • 28,987
  • 13
  • 60
  • 119
dand1
  • 81
  • 2
    А зачем такие велосипеды? Чем вас std::set не устраивает? – VladD Nov 23 '14 at 13:05

4 Answers4

3

Или на Питоне:

#!/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 "<stdin>", line 1, in <module>
StopIteration
>>> next(it)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
StopIteration

Итератор можно пройти только один раз. Чтобы перезапустить обход, необходимо создать новый итератор. (x*x for x in iterable) выражение возвращает итератор.

jfs
  • 52,361
  • @jfs: Клёво! А как функционирует *[tokens]*2? Не нашёл в документации.

    (А не материализует ли код список чересчур рано? В моём примере pairs — это, по существу, генератор. А zip(*[tokens]*2)?)

    – VladD Nov 24 '14 at 09:29
  • @jfs: Кажется, разобрался до этого пункта: http://ideone.com/zPRPOV. Результаты разные, где почитать документацию?

    Ох. В Питоне генераторы одноразовые?

    – VladD Nov 24 '14 at 10:22
  • @VladD: обновил ответ. Кстати ссылка из первого комментария содержит описание типов итераторов, генераторов. – jfs Nov 24 '14 at 12:20
  • @jfs: Ага, понял, спасибо! Этот нюанс существенно отличается от поведения .NET. В C# итераторы можно использовать повторно, и различные, даже одновременные обходы итератора независимы. В Питоне, если я правильно понял, продвижение итератора в одной энумерации есть по существу продвижение его во всех энумерациях, и этот факт активно используется в упомянутом вами паттерне. – VladD Nov 24 '14 at 12:28
  • @VladD: вызов генератора-функции создаёт новый объект (который реализует Итератор протокол). Поэтому поведение здесь идентично c .NET. – jfs Nov 24 '14 at 12:47
  • @jfs: Интересно. В .NET таким поведением обладает внутренний тип IEnumerator<T> (пример) (с которым обычные библиотечные функции не работают). Ну или можно сконструировать IEnumerable<T> вручную, но это не считается ожидаемым поведением и не одобряется. – VladD Nov 24 '14 at 13:27
2

Доброго времени суток!
Вот код, который решает Вашу задачу:

#include <iostream>
#include <fstream>
#include <algorithm>
#include <iterator>

#include <set> #include <string>

#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<operation, std::string> op_node; typedef std::set<std::string> 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 &lt;&lt; "error: unable to read input..." &lt;&lt; endl;
    return 1;
}

string s;
while(input)
{ 
    input &gt;&gt; item.first;
    input &gt;&gt; item.second;

    if (!input) { // End-Of-Stream
        cout &lt;&lt; "EOS" &lt;&lt; endl;
        break;
    }

    execute_op(item, strings);
}
// print out all strings in string set

#ifdef _DEBUG_OPS copy(strings.begin(), strings.end(), ostream_iterator<string>(cout << endl, "\n")); #endif
return 0; }

Алгоритм следующий:

  1. Читаем из входного потока оператор.
  2. Читаем из входного потока строку.
  3. Выполняем действие над строкой в соответствии с оператором.
  4. Повторяем действия с 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

Надеюсь, я правильно понял, что Вы хотели сделать, и Вам помог!
Если есть вопросы по коду, пишите в комментариях, хотя, на мой взгляд, все очевидно. )
Успехов!

1

В качестве упорядоченного динамического контейнера можно использовать std::set, порекомендованный @VladD в комментарии к вопросу.

skipws флаг (установлен по умолчанию) позволяет удобно считывать поля, разделённые пробелом, c помощью operator>> (что такое пробел, может зависеть от локали, связанной с потоком):

#include <fstream>
#include <iostream>
#include <set>
#include <string>

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<string> 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(); }

Код достаточно краток и прямолинеен. Можно добавить ещё сообщения об ошибках, чтобы отличить ошибки ввода/вывода, например, ошибку открытия файла от ошибки чтения из файла.

jfs
  • 52,361
0

Вот полное решение на 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<string>();
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;
}
VladD
  • 206,799