Działania na stringach

Question

Cześć, potrzebuję dokonać działania(dodawnie i odejmowanie) na liczbach w stringach

string a = "10";

string b = "20";

b - a => "10";

Z góry dzięki za pomoc ;)

Uwaga: Jeśli chcecie odpowiedzieć, "Lepiej zrób to w intach", "Po co Ci w stringach, jak możesz w intach", etc to się nie wysilajcie i wyjdźcie z pytanka ;)

Comments

Zamieniasz na inty i wykonujesz dzialanie, potem mozesz znowu zamienic na stringa. Inaczej sie nie da

---

"Uwaga: Jeśli chcecie odpowiedzieć, "Lepiej zrób to w intach", "Po co Ci w stringach, jak możesz w intach", etc to się nie wysilajcie i wyjdźcie z pytanka ;)"

---

"Uwaga: Jeśli chcecie odpowiedzieć, "Lepiej zrób to w intach", "Po co Ci w stringach, jak możesz w intach", etc to się nie wysilajcie i wyjdźcie z pytanka ;)"

Nie powiedziałeś czemu podejście string->int->string Ci nie pasuje - warto się interesować, bo może to pomóc w znalezieniu roziwązania.

---

Robię odejmowanie na liczbach 10^1000, trochę ciężko na intach ;)

Answer 1

Najłatwiej to chyba zrobić jako dodawanie/odejmowanie pisemne jak w podstawówce uczyli.

Answer 2

Robię odejmowanie na liczbach 10^1000, trochę ciężko na intach ;)

O, tego się spodziewałem :)

No to idealnie byłoby żeby, zamiast używać atrapy w postaci std::stringa, użyć dedykowanej biblioteki do operacji na dowolnie dużych liczbach, np boost::multiprecision:

#include <boost/multiprecision/cpp_int.hpp>
#include <iostream>

using boost::multiprecision::cpp_int;
using boost::multiprecision::pow;

int main()
{
	cpp_int liczba = 10;
	liczba = pow(liczba, 1000);
	liczba += 1234;

	std::cout << liczba;
}

Albo, już wychodząc na boczny tor, użyć języka który coś takiego ma wbudowane :P

liczba = 10**1000
liczba += 1234

print(liczba)

 

Comments

Ogólnie racja. Przy którymś zadaniu ze SPOJ'a naklepałem sobie kod w tym wątku. Ale nikt normalny nie będzie używał takich konstrukcji w projektach :-)

Answer 3

std::string to tablica zmiennych typu char, które można zamienić na cyfrę (zgodnie z tablicą ASCII). Czyli używając odpowiednich zmian możesz zrobić funkcję dodającą dwie tablice cyfr - zwyczajnie "jak w podstawówce uczyli.". Czyli dodajesz dwie liczby i i reszte z dzielenia przez 10 zapisujesz na i-tej pozycji w tablicy wynikowej, a tą część liczby która się nie mieści musisz dodać następnym razem na i+1 pozycji itd. Takie dodawanie będzie wolniejsze niż na intach, będzie zajmować więcej pamięci, ale ograniczenie jej wielkości liczby będzie znacznie znacznie większe. Mam nadzieję, że o to chodziło.

Możesz się pokusić też o zrobienie tego w formie klasy BigInt z przeciążonymi operatorami (tak dla walorów estetycznych):

class BigInt
{
    std::string number;
public
	friend std::string operator+ (BigInt a, BigInt b)
//...
};

Answer 4

#include <string>
#include <stdexcept>
#include <iostream>
#include <cctype>
#include <cassert>

class NumericString {
public:

    NumericString(): data{"0"} {}

    NumericString(const std::string& data_): data{data_} {
        NumericString::not_digit_throw(data);
    }

    NumericString(const char * data_): data(data_) {
        NumericString::not_digit_throw(data);
    }

    NumericString(const NumericString& src) {
        NumericString::not_digit_throw(src.data);
        data = src.data;
    }

    NumericString& operator=(const std::string& data_) {
        NumericString::not_digit_throw(data_);
        data = data_;
        return *this;
    }

    NumericString& operator=(const char * data_) {
        return operator=(std::string(data_));
    }

    NumericString& operator+(const std::string& data_) {
        NumericString::not_digit_throw(data_);
        add_string(data_);
        return *this;
    }

    NumericString& operator+(const NumericString& src) {
        return operator+(src.data);
    }

    NumericString& operator+(const char * data_) {
        return operator+(std::string(data_));
    }

    NumericString& operator+=(const NumericString& src) {
        return operator+(src.data);
    }

    NumericString& operator+=(const std::string& data_) {
        return operator+(data_);
    }

    NumericString& operator+=(const char * data_) {
        return operator+(std::string(data_));
    }

    const std::string& to_string() const {
        return data;
    }

    const char * c_str() const {
        return data.c_str();
    }


private:
    static bool not_digit_throw(const std::string& data_) {
        return not_digit_throw(data_.c_str());
    }

    static bool not_digit_throw(const char * data_) {
        char * ptr = const_cast<char *>(data_);
        while(*ptr != 0) {
            if(! std::isdigit(*ptr)) {
                throw std::invalid_argument("NumericString illegal char. Only digit allowed.");
            }
            ++ptr;
        }
        if(*data_ == 0) {
            throw std::invalid_argument("Empty string not allowed.");
        }
        return true;
    }

    void add_string(const std::string& value) {
        auto& longer_string = choice_longer_string(data, value);
        auto result = "0" + longer_string;
        auto& added_string = longer_string == data ? value : data;
        auto added_index = added_string.size();
        auto result_index = result.size() - 1;
        auto carry = 0U;

        while(added_index--) {
            unsigned value = result[result_index] + added_string[added_index] + carry;
            if(value > ('0' + '9')) {
                value -= 10;
                carry = 1; 
            } else {
                carry = 0;
            }
            result[result_index--] = value - '0';
        }

        carry_propagation(result, result_index, carry);

        data = remove_leading_zeros(result);
    }

    const std::string& choice_longer_string(const std::string& s1, const std::string& s2) {
        return s1.size() > s2.size() ? s1: s2;
    }

    void carry_propagation(std::string& result, size_t result_index, unsigned carry) {
        while(carry) {
            auto value = result[result_index] + carry;
            if(value > '9') {
                result[result_index] = value - 10;
                carry = 1;
            } else {
                result[result_index] = value;
                carry = 0;
            }
            --result_index;
        }
    }

    std::string remove_leading_zeros(std::string& value) {
        auto const pos = value.find_first_not_of('0');
        value.erase(0, pos);

        return value.size() ? value: "0";
    }

    std::string data;
};

int main() {
    NumericString number1{"1410"};
    NumericString number2{"1919"};
    NumericString number3 = "9999";
    number3 += "9999";
    NumericString number4 = "0";
    number4 += "0";
    NumericString number5 = "8788936827674961256837936320935798358762176805849872";
    number5 +="8989254213765729837187205937498218778687350304912821464";
    assert(number5.to_string() == "8998043150593404798444043873819154577046112481718671336");
    std::cout << number3.c_str() << std::endl;
    std::cout << (number1 + number2).to_string() << std::endl;
    std::cout << number4.c_str() << std::endl;
    std::cout << number5.c_str() << std::endl;
}