About OOP

hw.06_task.02.cpp

// author: Roman Tereshin
// email: roman.tereshin@student.spbu.ru

// hw 06, task 02

// По дереву разбора арифметического выражения вычислить его значение. Дерево разбора хранится в файле в виде
// (<операция> <операнд1> <операнд2>), где <операнд1> и <операнд2> сами могут быть деревьями, либо числами.
// Например, выражение (1 + 1) * 2 представляется в виде (* (+ 1 1) 2). Должны поддерживаться операции +, -, *, /
// и целые числа в качестве аргументов. Требуется построить дерево в явном виде, распечатать его (не обязательно так
// же, как в файле), и посчитать значение выражения обходом дерева. Может быть полезна функция ungetc (если не '(',
// возвращаем символ в поток и читаем число fscanf-ом). Можно считать, что входной файл корректен. Пример - по
// входному файлу (* (+ 1 1) 2) может печататься ( * ( + 1 1 ) 2 ) и выводиться 4


#include <iostream>
#include <fstream>
#include <string>
#include <stdexcept>
#include "polish_tree.h"

using namespace std;

int main(void) try
{
    clog << "Enter a file name with integral syntax tree: ";
    string fname;
    cin >> fname;
    ifstream in(fname.c_str());
    if (!in)
    {
        cerr << "File " << fname << " not found" << endl;
        return 1; // 1 - это код ошибки. Куда он идет? После завершения программы наберите в консоли
                  // ... echo %ERRORLEVEL% в windows или echo $? в *nix - и все поймете.
    }

    OperationNode polishTree(in); // Заменой in на cin мы тут же переведем нашу программу на работу с консолью.
    cout << "(=" << polishTree << ' ' << polishTree.calculate() << ')' << endl; // Неплохо бы в качестве ответа
                                                                                // ... выдавать строку, верную
    return 0; // 0 - это все в полном порядке                                   // ... с позиций нашего же кода
}
catch (std::invalid_argument e)
{
    cerr << e.what() << endl; // Исключения из стандартной библиотеки имеют замечательный метод what,
                              // ... который позволяет вытащить строку, ранее переданную конструктору
    return 2;                 // ... этого исключения.
}

hw.06_task.02.pro

HEADERS += \
    polish_tree.h

SOURCES += \
    polish_tree.cpp \
    hw.06_task.02.cpp

polish_tree.cpp

#include "polish_tree.h"
#include <sstream>   // Здесь можно найти строковой поток - похожий на файловый или стандартный, но работающий
#include <stdexcept> // ... не с консолью или файлами - а со строками (оперативной памятью, иначе говоря) - еще
                     // ... один пример полиморфизма

TreeNode *OperationNode::getTreeNode(std::istream &in)
/* Используется в конструкторе OperationNode - см. ниже */
{
    char sym = '"';
    in >> sym;       // Для похожих целей есть замечательный метод peek в istream, но он
    in.putback(sym); // ... не пропускает пробелы :(

    TreeNode *tmp = 0;               // Указатель, во власти которого вся иерархия объектов
    if (sym == '(')                  // Открывающая скобочка говорит нам, что следом - операция и нужно
        tmp = new OperationNode(in); // ... создавать поддерево с операцией
    else
        tmp = new LeafNode(in);      // ... или лист с константой, раз это не так

    if (in)
        return tmp;  // <stdexcept> именно за этим - библиотечные исключения достаточно удобны и универсальны
    throw std::invalid_argument("TreeCreateTimeError: Invalid argument - must be integer");
}

OperationNode::OperationNode(std::istream &in)
{
    char bracket = '"';
    in >> bracket;             // Пропуск бесполезной совершенно открывающей скобки

    in >> m_operation;         // Сохраняем операцию и создаем правое и левое поддеревья -
    m_left = getTreeNode(in);  // ... окажутся они лишь листьями или именно поддеревьями уже не наша
    m_right = getTreeNode(in); // ... забота. Алгоритм рекурсивен и работает на стеке вызовов функций
                               // ... так же легко, как работал бы, скажем, на std::stack<T> от STL
    in >> bracket;
}

OperationNode::~OperationNode()
{
    delete m_left;   // Важный момент, если вам не нужны утечки памяти или проблемы при ее освобождении.
    delete m_right;  // ... То, что delete, примененный к поддереву с
                     // ... операцией вызовет рекурсивно такой же деструктор для его детей, то есть, вызовет именно
                     // ... ~OperationNode(), обеспечивается одновременным соблюдением двух вещей - существованием
                     // ... виртуального деструктора с реализацией у базового класса (пусть и пустой) и переопределе-
                     // ... нием его в OperationNode. Ясно, что здесь вызывается деструктор того типа, к которому
                     // ... принадлежат указатели - а это TreeNode с абсолютно ничего не делающим деструктором. Но он
                     // ... сцеплен (см. polish_tree.h) с деструктором поддерева с операцией.
}

int OperationNode::calculate() const
/* Если попросить поддерево посчитаться, то все, что ему нужно сделать - это в свою очередь попросить посчитаться
своих сыновей (а каждый из них - будь это лист или поддерево - сделает это по-своему (полиморфизм), да только
просить их надо одинаково и ответ они дают одинаково) и применить свою операцию к полученным ответам - и, конечно,
сообщить результат нам. */
{
    switch (m_operation)
    { // ООП в своей красе - в самом ядре программы и
    case '+': // ... комментировать нечего - все и так ясно.
        return m_left->calculate() + m_right->calculate();
    case '-':
        return m_left->calculate() - m_right->calculate();
    case '*':
        return m_left->calculate() * m_right->calculate();
    case '/':
        return m_left->calculate() / m_right->calculate();
    case '%':
        return m_left->calculate() % m_right->calculate();
    case '=':
        return m_left->calculate() == m_right->calculate();
    default:
        throw std::invalid_argument("TreeCalculateTimeError: Invalid operation symbol: must be +, -, *, /, % or =");
    }
}

void OperationNode::print(std::ostream &out) const
{
    out << " (" << m_operation;
    m_left->print(out);
    m_right->print(out);
    out << ')';
}

std::ostream &operator <<(std::ostream &out, const OperationNode &self)
/* Учим наше дерево печататься по запросу типа cout << polishTree; */
{
    std::stringstream sout;
    self.print(sout);  // Коли мы умеем печаться только в поток - давайте подсунем наивному print поток в память
    out << sout.str(); // ... и потом из нее уже выпишем все накопленное в наш cout. Или ofstream... Смотря что
                       // ... подсунет нам пользователь класса

    return out;
}

polish_tree.h

#pragma once
#include <iostream>

/* Класс, имеющий хотя бы одну чистую (зануленную) виртуальную функцию является абстрактным - невозможно создать его
экземпляры. Абстрактный класс, будучи базовым для наследников, реализует один из принципов ООП - полиморфизм,
кратко который можно определить как возможность существования объектов, которые выглядят похоже, делают что-то
похожее - но делают это каждый по-своему */

class TreeNode
/**
* Абстрактный базовый класс-интерфейс узлов дерева - обеспечивает необходимую иерархию классов. Объективно необходим
* 1. для введения в систему типа унифицированного указателя и на листья дерева, содержащего целочисленные константы,
* и на иные его узлы (поддеревья), содержащие знаки операций.
* 2. для обеспечения единого интерфейса вышеописанных классов, значит - неразличимого для клиента классов поведения
* разнородных по своему содержанию узлов дерева.
* 3. для создания иерархии деструкторов и обеспечения удаления дерева из динамической памяти по типу цепной реакции.
*/
{
public:
    virtual int calculate() const = 0;               // Зануленный виртуальный метод вынуждает всякого наследника
    virtual void print(std::ostream &out) const = 0; // ... переопределить такой метод
    virtual ~TreeNode() {} // Обычный виртуальный метод позволяет наследнику по желанию
                                                     // ... переопределить его реализацию, в данном случае inline'-
// Ситуация с виртуальным деструктором не совсем     // ... овую (обратите внимание на {})
// ... типичная - он не столько переопределяется
// ... наследниками, сколько входит в сцепку с
// ... их деструкторами, образуя иерархию - при
// ... вызове дестуктора базового класса реально
// ... будет вызван и он, и деструктор именно того
// ... класса, к которому принадлежит объект.
};

/* Чтобы расширить свой класс можно унаследоваться от другого класса, позаимствовав его интерфейс и/или реализацию.
Существует три режима наследования:
public - сохраняет содержимое секций public и protected базового класса как есть (напомню, что секция private
не доступна для наследования) Только такое наследование (!) разрешает неявное преобразование указателя
на объект класса-потомка в указатель на базовый класс.
protected - наследует содержимое public и protected в protected
private - -//- в private */

class LeafNode : public TreeNode
/**
* Класс-лист дерева. Его задача - хранить целочисленную константу-аргумент и при этом выглядеть точно так же, как и
* любое более сложное поддерево - уметь отвечать на запрос .calculate() так, будто он и правда что-то считает.
*/
{
public:
    LeafNode(std::istream &in) { in >> m_value; } // Конструктор считывает в лист int
    int calculate() const { return m_value; }     // Все расчеты заключаются в выдаче хранимого int
    void print(std::ostream &out) const { out << ' ' << m_value; }

private:                                          // Обратите внимание - удалять тут нечего, потому
    int m_value;                                  // ... и деструктор базового класса не переопределен
};

class OperationNode : public TreeNode
/**
* Класс-поддерево с операцией. Является формообразующим элементом дерева, поскольку хранит указатели на левого и
* правого сына. Также, по сути, является конструктором всего итогового арифметического дерева.
*/
{
public:
    OperationNode(std::istream &in);
    ~OperationNode();

    int calculate() const;
    void print(std::ostream &out) const;

protected:
    TreeNode *getTreeNode(std::istream &in); // Внутренние, служебные методы лучше спрятать в
                                             // ... наследуемую protected-секцию
private:
    char m_operation;
    const TreeNode *m_left;  // На деле такие указатели могут хранить адреса объектов любых классов, являющихся
    const TreeNode *m_right; // ... public-наследниками класса TreeNode - что нам и нужно, так как одним из сыновей
                             // ... может оказаться лист с константой, а другим - поддерево с операцией

/* Подробные комментарии по поводу друзей см. здесь: https://gist.github.com/1322950 */
friend std::ostream &operator <<(std::ostream &out, const OperationNode &self);
};

Реализация паттернов проектирования "Интерпретатор" и "Компоновщик"