Integral syntax tree

main.cpp

/* Это второй листинг из серии. Первый смотрите здесь: https://gist.github.com/1322950 */

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

using namespace std;

int main(void)
{
    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 - и все поймете.
    }

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

polish_tree.cpp

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

TreeNode *OperationNode::getTreeNode(std::istream &in)
/* Используется в конструкторе OperationNode - см. ниже */
{
    char sym = '\0';
    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 = '\0';
    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 применим (это точно указатели, созданные new) гарантируется тем, что создаются они
                     // ... внутри конструктора класса, а не передаются в тот же конструктор извне. То, что этот
                     // ... delete, будучи примененным к листу ничего лишнего не сделает - тем, что лист не переопре-
                     // ... делял деструктор базового класса - а он пуст. То, что 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'-
// Ситуация с виртуальным деструктором не совсем      // ... овую (обратите внимание на {}), что без спецификатора
// ... типичная - он не столько переопределяется      // ... virtual, вообще говоря, невозможно - язык запрещает
// ... наследниками, сколько входит в сцепку с        // ... определять функцию дважды (не путать с "объявлять")
// ... их деструкторами, образуя иерархию - при
// ... вызове дестуктора базового класса реально
// ... будет вызван и он, и деструктор именно того
// ... класса, к которому принадлежит объект.
};

/* Чтобы внести в свое пространство имен поля и методы другого класса от него нужно унаследоваться. Существует три
   режима наследования:
   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;

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

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

polish_tree.pro

HEADERS += \
    polish_tree.h

SOURCES += \
    polish_tree.cpp \
    main.cpp