Форум программистов «Весельчак У»
  *
Добро пожаловать, Гость. Пожалуйста, войдите или зарегистрируйтесь.
Вам не пришло письмо с кодом активации?

  • Рекомендуем проверить настройки временной зоны в вашем профиле (страница "Внешний вид форума", пункт "Часовой пояс:").
  • У нас больше нет рассылок. Если вам приходят письма от наших бывших рассылок mail.ru и subscribe.ru, то знайте, что это не мы рассылаем.
   Начало  
Наши сайты
Помощь Поиск Календарь Почта Войти Регистрация  
 
Страниц: [1]   Вниз
  Печать  
Автор Тема: Переполнение стека при перегрузке операторов  (Прочитано 6219 раз)
0 Пользователей и 1 Гость смотрят эту тему.
Ytsukene
Новенький

ru
Offline Offline

« : 23-05-2014 23:03 » 

Задача - создать класс рациональной дроби - Rational -, числитель и знаменатель которой - массивы типа unsigned char фиксированного размера. Определить операции сложения, вычитания, умножения, деления и сравнений (>,<,==). Я решил создать вспомогательный класс safeunschar и в нём определить сложение, вычитание и умножение массивов. Потом, на основе этих операций, я определил по заданию действия с дробями.
Проблема в том, что для удобства, операции с массивами могут вызываться из других операций - например, операция вычитания в моём исполнении вычитает только из большего меньшее, иначе вызывается операция вычитания, в которой они меняются местами. Или для сравнения используется операция вычитания между массивами, и по знаку операции возвращается значение. А так как при таких вызовах из операций создаются всё новые и новые объекты в стеке - стек полностью ими выжирается, и программа вылетает.
Пожалуйста, подскажите, как реорганизовать программу, чтобы сэкономит память.

Код:
#define _CRT_SECURE_NO_WARNINGS //отключает запрещение компиллятора использовать небезопасные функции по типу strcat(), strcpy, itoa() и т. д.
#include <iostream>
#include <string>
 
using namespace std;
 
void itounchar(int value, unsigned char* buf)
{
    int size = 0, b = value;
    do{ b /= 10; size++; } while (b != 0);  //подсчитывается размер числа
    buf[size] = '\0';   //на конец числа в массиве ставится нуль-символ
    for (size -= 1; size >= 0; size--)  //число "задом наперёд" записывается в массив
    {
        buf[size] = static_cast<char>(value % 10 + 48); //записывается последняя цифра числа (прибавляется 48, так как кодировки int и char различаются на 48)
        value /= 10;    //последняя цифра числа стирается
    }
}
 
class safeunschar
{
    int minus;
    static const int fixsize = 100; //static - в любом объекте этого класса size будет равно 100
    unsigned char *arr;
    int size;
    void check()
    {
        int begzero = 0;
        bool check = true;
        for (int i = 0; i < size; i++)
        {
            if (arr[i] != '0')
                check = false;
            if (check) begzero++;
        }
        if (check)
        {
            size = 1;
            minus = 1;
        }
        else if (begzero > 0)
        {
            for (int a = 0, b = begzero; b < size; b++, a++)
                arr[a] = arr[b];
            size -= begzero;
        }
 
    }
    void reverse()
    {
        unsigned char buf;
        for (int a = 0, b = size - 1; a < b; a++, b--)
        {
            buf = arr[a];
            arr[a] = arr[b];
            arr[b] = buf;
        }
    }
public:
    safeunschar()
    {
        minus = 1;
        arr = new unsigned char[fixsize];
        arr[0] = '0';
        size = 1;
    }
    safeunschar(safeunschar& ob)
    {
        //cout << "COPY!" << endl;
        minus = ob.minus;
        arr = new unsigned char[fixsize];
        for (int i = 0; i < ob.size; i++)
            arr[i] = ob.arr[i];
        //cout << arr << endl;
        size = ob.size;
    }
    safeunschar operator*(int a)
    {
        safeunschar buf;
        if (a < 0)
        {
            buf.minus = -1;
            a *= (-1);
        }
 
        int high = 0, b;
 
        //cout << "\t\t\t" << endl;//Отладка!
        //cout << "\t\t\t" << "Считаем "; this->show(); cout << "\t\t\t      * "<<a<<endl;
 
        for (int i = 0, th = this->size - 1; th >= 0; i++, th--)
        {
            //cout << "\t\t\tДействие " << i << endl;//Отладка!
            b = static_cast<int>(this->arr[th] - 48) * a + high;
            //cout << "\t\t\t" << "b = " << b << endl;//Отладка!
            if (b >= 10)
            {
                buf.arr[i] = static_cast<char>(b % 10 + 48);
                high = b / 10;
            }
            else
            {
                buf.arr[i] = static_cast<char>(b + 48);
                high = 0;
            }
            //cout << "\t\t\t" << arr[th] << " * " << a << " = " << buf.arr[i] << endl;//Отладка!
            //cout << "\t\t\t" << "high = " << high << endl;//Отладка!
            if (i > 0) buf.size++;
        }
        if (high > 0)
        {
            /*cout << "\t\t\tВдобавок:" << endl;*/
            for (int i = buf.size; high > 0; i++, high /= 10)
            {
                buf.arr[i] = static_cast<char>(high % 10 + 48);
                /*cout << "\t\t\t" << arr[i] << endl;
                cout << "\t\t\thigh = " << high / 10 << endl;*/
                buf.size++;
            }
        }
        //cout << "неповёрнутый: "; buf.show();
        buf.reverse();
        //cout << "повёрнутый: "; buf.show();
        buf.check();
        //cout << "отредактированный: "; buf.show();
 
        return buf;
    }
    safeunschar operator+(safeunschar& op)
    {
        safeunschar buf;
        int high = 0, b;
 
        if (this->minus == -1 && op.minus == -1) buf.minus = -1;
        else if (this->minus == -1)
        {
            buf = (op - *this*(-1));
            return buf;
        }
        else if (op.minus == -1)
        {
            buf = (*this - op*(-1));
            return buf;
        }
 
        //  cout << '\t' << endl;//Отладка!
        //  cout << "\t\t" << "Считаем "; this->show(); cout << "\t\t      + "; op.show();
        if (this->size < op.size)
        {
            buf = (op + (*this));   //предполагается, что первый операнд больше, в противном случае они меняются местами
            return buf;
        }
 
        for (int i = 0, th = this->size - 1, o = op.size - 1; th >= 0; i++, th--, o--)
        {
            //  cout << "\t\tДействие " << i << endl;//Отладка!
            if (o < 0)
                b = static_cast<int>(this->arr[th]) - 48 + high;
            else
                b = static_cast<int>(this->arr[th]) - 48 + static_cast<int>(op.arr[o]) - 48 + high;
            //cout << "\t\t" << "b = " << b << endl;//Отладка!
            if (b >= 10)
            {
                buf.arr[i] = static_cast<char>(b % 10 + 48);
                high = b / 10;
            }
            else
            {
                buf.arr[i] = static_cast<char>(b + 48);
                high = 0;
            }
            //cout << "\t\t" << arr[th] << " + " << op.arr[o] << " = " << buf.arr[i] << endl;//Отладка!
            //cout << "\t\t" << "high = " << high << endl;//Отладка!
            if (i > 0) buf.size++;
        }
 
        if (high > 0)
        {
            //cout << "\t\t\tВдобавок:" << endl;
            for (int i = buf.size; high > 0; i++, high /= 10)
            {
                buf.arr[i] = static_cast<char>(high % 10 + 48);
                //cout << "\t\tновый  = " << buf.arr[i] << endl;
                //cout << "\t\t\thigh = " << high / 10 << endl;
                buf.size++;
            }
        }
 
        //cout << "неповёрнутый: "; buf.show();
        buf.reverse();
        //cout << "повёрнутый: "; buf.show();
        buf.check();
        //cout << "отредактированный: "; buf.show();
        return buf;
    }
    safeunschar operator-(safeunschar& op)
    {
        safeunschar buf;
        int c, d, c_next;
 
        if (this->minus == -1 && op.minus == -1)
        {
            buf = (op*(-1) - *this*(-1));
            return buf;
        }
        else if (this->minus == -1)
        {
            buf = ((op + *this*(-1))*(-1));
            return buf;
        }
        else if (op.minus == -1)
        {
            buf = (*this + op*(-1));
            return buf;
        }
 
        if (this->size < op.size || this->size == op.size)
        {
            bool flag = false;
            for (int i = 0; i < size; i++)
            {
                if (this->arr[i] < op.arr[i])
                    flag = true;
            }
            if (flag)
            {
                buf = (op - *this);
                buf = buf*(-1);
                return buf;
            }
        }
 
        //  cout << '\t' << endl;//Отладка!
        //  cout << "\t" << "Считаем "; this->show(); cout << " - "; op.show();  cout << endl;//Отладка!
 
        c = static_cast<int>(this->arr[this->size - 1]) - 48;
 
        for (int i = 0, th = this->size - 1, o = op.size - 1; th >= 0; i++, th--, o--)
        {
            if (th != 0)
                c_next = static_cast<int>(this->arr[th - 1]) - 48;
            if (o >= 0)
                d = static_cast<int>(op.arr[o]) - 48;
            else
                d = 0;
            //cout << "Действие " << i << endl;//Отладка!
 
 
            if (c < d)
            {
                c_next--;
                c += 10;
            }
            //cout << "\t" << "c = " << c << endl;//Отладка!
            //cout << "\t" << "d = " << d << endl;//Отладка!
            buf.arr[i] = static_cast<char>(c - d) + 48;
 
            c = c_next;
            //  cout << "\t" << arr[th] << " - " << op.arr[o] << " = " << buf.arr[i] << endl;//Отладка!
            if (i > 0) buf.size++;
        }
        //cout << "неповёрнутый: "; buf.show();
        buf.reverse();
        //cout << "повёрнутый: "; buf.show();
        buf.check();
        //cout << "отредактированный: "; buf.show();
        return buf;
    }
    safeunschar operator*(safeunschar& op)
    {
        safeunschar buf, sum;
        int index = this->minus;
 
        if (this->size < op.size)
            return buf = (op*(*this));
 
        //cout << "\tПереданы параметры:" << "\n\ta = "; this->show(); cout << "\n\tb = "; op.show();
        for (int o = op.size - 1, th = this->size, i = 0; o >= 0 && th >= 0; o--, th--, i++)
        {
            //cout << "\tдействие " << i << ". buf = "; buf.show();
            //cout << "\tУмножаем " << static_cast<int>(op.arr[o] - 48) * static_cast<int>(pow(10,i)) << " на "; this->show();
            //buf = buf + (*this*(index)) * (static_cast<int>(op.arr[o] - 48) * static_cast<int>(pow(10, i)));
            sum = (*this*(index)) * (static_cast<int>(op.arr[o] - 48));
            for (int j = 0, k = sum.size; j < i; j++, k++)
            {
                sum.arr[k] = '0';
                sum.size++;
            }
            buf = buf + sum;
        }
        if (this->minus == -1 && op.minus == -1)
            buf.minus = 1;
        else if (this->minus == -1 || op.minus == -1)
            buf.minus = -1;
        else
            buf.minus = 1;
        buf.check();
        return buf;
    }
 
    bool operator==(char* s)
    {
        int sis;
        for (sis = 0; s[sis] != '\0'; sis++);
        if (sis != size)
            return false;
        else
        {
            for (int i = 0; i < size; i++)
            {
                if (arr[i] != (char)s[i])
                    return false;
                else
                    return true;
            }
        }
    }
    bool operator<(safeunschar& op)
    {
        safeunschar buf = *this - op;
        if (buf.minus > 0 || buf == "0")
            return false;
        else
            return true;
    }
    bool operator>(safeunschar& op)
    {
        safeunschar buf = op - *this;
        if (buf.minus > 0 || buf == "0")
            return false;
        else
            return true;
    }
 
    bool read(string s) //Чтение с клавиатуры
    {
        //cout << "/tstring: " << s << endl;
        if (s.at(0) == '0' && s.length() > 1) return false;
        for (int i = 0; i < s.length(); i++)
        {
            if (((s.at(i)<'0') || (s.at(i)>'9')) && s.at(i) != '-')
                return false;
        }
 
        if (s.at(0) == '-')
        {
            minus = -1;
            s.erase(0, 1);
        }
        else
            minus = 1;
        int n = 0;
        for (int i = 0; i < s.length(); i++)
        {
            arr[n] = (int)s.at(i);
            n++;
        }
        size = n;
        return true;
    }
    void show()
    {
        //cout << "\n\t size = " << size << "\n";
        if (minus == -1)cout << '-';
        for (int i = 0; i < size; i++)
            cout << arr[i];
    }
};
 
 
class Rational
{
    safeunschar numerator;
    safeunschar denomenator;
 
    //void reduce()
    //{
    //  if (!strcmp((char*)numerator, "0")) return;
    //  int first, second, reduce;
    //  first = atoi((char*)numerator); //присвоение числителя
    //  second = atoi((char*)denominator);//присвоениее знаменателя
 
    //  while (first != 0 && second != 0)   //цикл вычисления наименьшего общего кратного
    //  {
    //      if (first >= second) first %= second;
    //      else second %= first;
    //  }
    //  reduce = first + second;    //reduce - итоговое наименьшее общее кратное
    // 
    //  itounchar(atoi((char*)numerator) / reduce, numerator);
    //  itounchar(atoi((char*)denominator) / reduce, denominator);
    //}
public :
   
    Rational()
    {
        //числитель и знаменатель инициализируются автоматически
    }
    void read ()    //Чтение с клавиатуры
    {
        string s1,s2;
        do {
        cout << "Введите числитель: " << endl;
        getline(cin,s1);
        cout << "Введите знаменатель: " << endl;
        getline(cin,s2);
        } while ((!numerator.read(s1) || !denomenator.read(s2)) && cout << "Неправильный ввод!" << endl);
    }
 
    bool read(string s1,string s2)
    {
        if (!numerator.read(s1) || !denomenator.read(s2))
            return false;
        else
            return true;
    }
   
    void show()
    {
        numerator.show(); cout << " / "; denomenator.show(); cout << endl;
    }
 
    Rational(Rational& ob)
    {
        this->numerator = ob.numerator;
        this->denomenator = ob.denomenator;
    }
    Rational operator+(Rational op) // op - второй операнд сложения (первый передаётся неявно)
    {
        Rational buf;
 
        buf.numerator = this->numerator*op.denomenator + op.numerator*this->denomenator;
        buf.denomenator = this->numerator*op.denomenator;
       
        return buf;
    }
    Rational operator-(Rational op)
    {
        Rational buf;
 
        buf.numerator = this->numerator*op.denomenator - op.numerator*this->denomenator;
        buf.denomenator = this->numerator*op.denomenator;
 
        return buf;
    }
    Rational operator*(Rational op)
    {
        Rational buf;
 
        buf.numerator = this->numerator*op.numerator;
        buf.denomenator = this->numerator*op.denomenator;
 
        return buf;
    }
    Rational operator/(Rational op)
    {
        Rational buf;   //Результат сложения
        if (op.numerator == "0")
        {
            cout << "Деление на ноль!";
            return *this;
        }
 
        buf.numerator = this->numerator*op.denomenator;
        buf.denomenator = op.numerator*this->denomenator;
 
        return buf;
    }
    bool operator>(Rational op)
    {
        if (this->numerator*op.denomenator > op.numerator*this->denomenator)
            return true;
        else
            return false;
    }
    bool operator<(Rational op)
    {
        if (this->numerator*op.denomenator < op.numerator*this->denomenator)
            return true;
        else
            return false;
    }
    /*bool operator==(Rational op)
    {
        if (this->minus*atoi((char*)this->numerator)*atoi((char*)op.denominator) == op.minus*atoi((char*)op.numerator)*atoi((char*)this->denominator))
            return true;
        else
            return false;
    }*/
 
};
 
int main()
{
    setlocale(0,"rus");
    Rational a,b;
 
    string s1, s2;
    s1 = "732195927564";
    s2 = "151784321267";
    a.read(s1,s2);
    cout << "a = "; a.show();
    s1 = "562736912";
    s2 = "115921101";
    b.read(s1,s2);
    cout << "b = "; b.show();
 
 
    cout << "a+b = "; (a + b).show();
    cout << "a-b = "; (a - b).show();
    cout << "a*b = "; (a*b).show();
    cout << "a/b = "; (a / b).show();
    if (a > b) cout << "a>b" << endl;
    else if (a < b) cout << "a<b" << endl;
    else cout << "a=b" << endl;
 
    system("pause");
    return 0;
}
Записан
Dimka
Деятель
Команда клуба

ru
Offline Offline
Пол: Мужской

« Ответ #1 : 24-05-2014 09:50 » new

Ytsukene, насчёт переполнения стека не верю - какой-то косяк в рекурсивных вызовах и бесконечная рекурсия. Вот с этой точки зрения проверяй.

1) Советую хранить не цифры в ASCII кодах, а цифры в 10-ичном виде и добавить операции strtounch, unchtostr преобразования чисел в строки и обратно. Ещё лучше хранить в двоичном виде, тогда каждый байт массива можно рассматривать как цифру числа в 256-ричном виде. Это, понятное дело, экономит память (если уж так вопрос стоит). Цифры в ASCII коде тебе бесполезны хотя бы потому, что ты минус хранишь не в строковом представлении, а отдельным полем структуры.

2) Советую использовать динамические массивы переменной длинны. Чтобы не писать их самому, можно использовать из STL тип std::vector<unsigned char>.

3) Советую добавить класс "арифмометр", определив на нём операции сложения, вычитания, умножения и деления для отдельных цифр по аналогии с тем, как это реализовано в микропроцессоре. Т.е. для сложения и вычитания к цифр добавить флаг переполнения (как при операциях в столбик на бумажке точки ставят для запоминания переноса единицы в старший разряд или заимствования единицы из старшего разряда). Для умножения и деления иметь двухцифровые блоки: произведение из двух одноциферных множителей может быть двухциферным. Делимое может быть двухциферным. Результат деления имеет целую часть и остаток.

4) Закомментированный НОК - это здравая идея. Но чтобы дроби не распухали, после каждой операции целесообразно искать НОД и сокращать числитель и знаменатель дроби на него.

На беглый взгляд у тебя в коде ничего бросающегося в глаза криминального нет. Так что переполнение стека - это не столько неправильный подход, сколько банальный баг, который надо найти.
Записан

Программировать - значит понимать (К. Нюгард)
Невывернутое лучше, чем вправленное (М. Аврелий)
Многие готовы скорее умереть, чем подумать (Б. Рассел)
Страниц: [1]   Вверх
  Печать  
 

Powered by SMF 1.1.21 | SMF © 2015, Simple Machines