Короткие примеры C++ кода-1 Кувшинов Д

break;

}

cin.unget(); // Не скобка -- возвращаем - или + обратно.

// "Полноценный калькулятор" должен поддерживать унарные операции непосредственно.

// Данный пример упрощён: поддерживаются только бинарные инфиксные операции.



case '.':

case '0': case '1': case '2': case '3': case '4':

case '5': case '6': case '7': case '8': case '9':

if (!(cin >> x))

{

error("number expected\n");

goto Finish;

}



xs.push(x);

awaiting_term = false;

break;
case '(':

cin.ignore(); // Убрать открывающую скобку из потока.

ops.push('(');

break;
case ')':

error("unmatched ')' found\n");

goto Finish;
default:

error("term expected, '");

cerr << peek() << "' found\n";

goto Finish;

}

}

else // Ожидается операция.

{

switch (char op = peek())

{

case '+': case '-': case '*': case '/': case '%': case '^':

// Основное отличие от предыдущего варианта калькулятора,

// позволяющее учитывать приоритеты операций, находится здесь.

{

cin.ignore(); // Убрать знак операции с потока.

const auto op_prec = precedence(op); // Приоритет считанной операции.

const auto op_ltr = is_left_associative(op); // Левоассоциирующая операция?
// Выполнить все предыдущие операции, имеющие приоритет выше op,

// либо равный приоритет при условии, что op -- левоассоциирующая.

while (!ops.empty() && ops.top() != '(')

{

const auto left_op_prec = precedence(ops.top());

// Отрицание условия, записанного в комментарии выше (условие выхода из цикла).

if ((op_ltr && left_op_prec < op_prec)

|| (!op_ltr && left_op_prec <= op_prec))

break;



if (!do_next_op())

goto Finish;

}
// Положить на стек операций следующую операцию.

ops.push(op);

// Теперь ожидаем терм.

awaiting_term = true;

}

break;
case ')':

// Убрать скобку с потока cin.

cin.ignore();

// Выполнять операции, пока не встретится открывающая скобка.

while (true)

{

if (ops.empty())

{

error("unmatched ')' found\n");

goto Finish;

}
if (ops.top() == '(')

{

ops.pop();

break;

}
if (!do_next_op())

goto Finish;

}

break;
case EOF:

// Выполнить все оставшиеся операции.

while (!ops.empty())

{

if (ops.top() == '(')

{

error("unmatched '(' found\n");

break;

}
if (!do_next_op())

break;

}

goto Finish;
default:

error("operation expected: '");

cerr << op << "'\n";

goto Finish;

}

}

}
Finish:

if (xs.empty())

{

error("not enough operands\n");

return 0.;

}
return xs.top();

}

int main()

{

cout.precision(16);

while (true)

{

double answer = infix();

cin.clear();

cin.ignore(cin.rdbuf()->in_avail());

cin.sync();

cout << "answer = " << answer << endl;

}

return EXIT_SUCCESS;

}

0840-merge_sort.cpp

// merge_sort.cpp

// Сортировка слияниями (рекурсивный вариант и вариант с явным стеком).

// Сортирует массивы целых.

#include

#include

using namespace std;
// Операция слияния двух упорядоченных массивов (a и b)

// в третий упорядоченный массив c.

// Предполагается, что c имеет размер не менее, чем an + bn.

// Функция возвращает индекс следующего элемента за последним записанным в c.

size_t merge(const int a[], size_t an, const int b[], size_t bn, int c[])

{

assert(an != 0 && bn != 0);

for (size_t i = 0, j = 0, k = 0;; ++k)

{

if (b[j] < a[i])

{

c[k] = b[j];

if (++j == bn)

{

while (i != an)

c[++k] = a[i++];

return k + 1;

}

}

else

{

c[k] = a[i];

if (++i == an)

{

while (j != bn)

c[++k] = b[j++];

return k + 1;

}

}

}

}

// Сортировка слияниями с внешнем буфером.

// Сортирует массив a на месте, используя buf для хранения промежуточных результатов.

// Размер buf должен быть не меньше an.

void merge_sort(int a[], size_t an, int buf[])

{

if (1 < an)

{

// Размеры сортируемых "половин": p1 -- левая, p2 -- правая.

const auto p1 = an / 2, p2 = an - p1;

// Отсортировать левую половину.

merge_sort(a, p1, buf);

// Отсортировать правую половину.

merge_sort(a + p1, p2, buf);

// Выполнить слияние отсортированных половин в буфер.

merge(a, p1, a + p1, p2, buf);

// Скопировать содержимое буфера в исходный массив.

for (size_t i = 0; i < an; ++i)

a[i] = buf[i];

}

}
// Сортировка слияниями, создающая свой буфер.

// Использует предыдущий алгоритм.

void merge_sort(int a[], size_t an)

{

int *buf = new int[an];

merge_sort(a, an, buf);

delete[] buf;

}

// Сортировка слияниями на основе цикла и стека.

// Представляет собой модификацию рекурсивного варианта.

// Использует буфер того же размера, что и исходный массив (создаёт и удаляет буфер динамически).

void merge_sort_s(int a[], size_t an)

{

// Стек отложенных задач реализован в виде статического массива размера 64.

// Предполагается, что адреса не более, чем 64-битные.

struct {

int *a; // Указатель на начало сортируемого диапазона.

size_t an; // Размер сортируемого диапазона.

int stage; // Стадия сортировки диапазона (0, 1, 2, 3).

} ds[64];
size_t sp = 0; // Индекс текущей вершины стека.

int *buf = new int[an];
// Положить в стек первоначальную задачу -- весь исходный массив.

ds[0].a = a;

ds[0].an = an;

ds[0].stage = 0;

while (true)

{

// На каждой стадии выполняется своё действие.

switch (ds[sp].stage++)

{

case 0: // Создать задачу для сортировки левой половины.

if (1 < an)

{

an /= 2;
auto &t = ds[++sp];

t.a = a;

t.an = an;

t.stage = 0;

}

break;
case 1: // Создать задачу для сортировки правой половины.

if (1 < an)

{

const auto p = an / 2;

a += p;

an -= p;
auto &t = ds[++sp];

t.a = a;

t.an = an;

t.stage = 0;

}

break;
case 2: // Выполнить слияние отсортированных половин.

if (1 < an)

{

const auto p = an / 2;

merge(a, p, a + p, an - p, buf);

for (size_t i = 0; i < an; ++i)

a[i] = buf[i];

}

break;
default: // Убрать задачу из стека.

if (sp-- == 0)

{

// Все задачи выполнены, завершить работу.

delete[] buf;

return;

}

else

{

auto &t = ds[sp];

a = t.a;

an = t.an;

}

}

}

}

0845-sll_merge_sort.cpp

// sll_merge.cpp

// Односвязный список (singly-linked list, SLL) и сортировка слияниями.

#include

#include
///////////////////////////////////////////////////////////////////////////////

// Односвязный список
// Тип значений, хранимый в списке.

typedef long Value;
// Звено односвязного списка.

struct Link

{

Link *next; // указатель на следующее звено

Value value; // значение, хранящееся в звене
// Элементарные конструкторы

Link(): next(nullptr) {}

explicit Link(Value value, Link *next = nullptr)

: next(next), value(value) {}

};

// Добавить значение в начало списка.

Link* push_front(Link *list, Value value)

{

return new Link(value, list);

}
// Создать список из массива.

Link* list_from_array(const Value a[], std::size_t n)

{

Link *head = nullptr;

while (n != 0)

head = push_front(head, a[--n]);

return head;

}

// Удалить начальное звено списка.

// Если removed_value != nullptr, то по этому адресу будет записано значение удалённого узла.

Link* pop_front(Link *list, Value *removed_value = nullptr)

{

assert(list);

const auto next = list->next;

if (removed_value)

*removed_value = list->value;

delete list;

return next;

}
// Удалить список целиком.

void delete_list(Link *list)

{

while (list)

list = pop_front(list);

}

// Проверить, является ли список закольцованным.

// Данная функция приводится как пример, далее она не используется (только тестируется).

bool has_loop(Link *list)

{

auto slow = list;

while (true)

{

// Два шага по list.

if (!list)

return false;

list = list->next;

if (!list)

return false;

if (list == slow)

return true;

list = list->next;