Zadanie z C++

pytanie zadane 4 stycznia w C i C++ przez WirusTrojan Nowicjusz (130 p.)

Celem zadania jest napisanie programu który będzie potrafił wykonywać operacje matematyczne (dodawanie, odejmowanie, mnożenie i dzielenie) na bardzo dużych liczbach całkowitych. Bardzo dużych czyli takich które nie mieszczą się w zmiennej typu Int, np. 100 cyfrowych.
jako wejście podawane jest String zawierający conajmniej dwie liczby i conajmniej jedno działanie do wykonania. Należy tutaj również pamiętać o kolejności wykonywania działań gdyż nawiasy są dozwolone.
w wyniku operacji na obiekcie typu String oczekiwane jest wypisanie obiektu String który zawiera rezultat operacji.
Nie dozwolone jest używanie niczego spoza biblioteki iostream ktoś pomoże bo już troszke wymiękam przy biurku

2 odpowiedzi

odpowiedź 5 stycznia przez Gynvael Coldwind Nałogowiec (27,950 p.)

@WirusTrojan jeśli tego nigdy nie pisałeś, to to Ci zajmie kilka wieczorów, ale jest jednocześnie dobrze opisane na necie; zacznij na początku od zaimplementowania "pisemnego" dodawania/mnożenia/etc, tj. rozbij sobie każdą liczbę na tablice cyfr, i zaimplementuj algorytm, który wylicza wynik tak jak się w podstawówce na kartce uczyłeś.

Jak to będziesz miał i będzie dobrze działać, to kolejnym krokiem jest parsing/tokenizacja wyrażenia które dostajesz (tego "(1000+22222)*3+4567") na tokeny, tj. listę zrozumiałych dla programu obiektów, gdzie każdy obiekt reprezentuje jedną logiczną część wyrażenia. W przypadku przykładu to by było coś w stylu:

Notacja: typ tokenu, opcjonalny parametr (string)

TOKEN_PARENTHESIS_OPEN
TOKEN_NUMBER, "1000"
TOKEN_OP_ADD
TOKEN_NUMBER, "22222"
TOKEN_PARENTHESIS_CLOSE
TOKEN_OP_MUL
TOKEN_NUMBER, "3"
TOKEN_OP_ADD
TOKEN_NUMBER, "4567"

Mając taką listę tokenów, możesz programowo na nich operować.

I teraz, z uwagi na kolejność operacji, musisz:

1) albo przejść na odwrotną notację polską (RPN), a przynajmniej zbudować drzewo AST (Abstract Syntax Tree) – dowolne z tych pozwoli Ci zacząć w prosty sposób liczyć,

2) albo napisać kilka pętli, gdzie w każdej będziesz znajdować dany typ operacji z większym priorytetem, i podmieniać tokeny na wyniki do skutku, tj:

Przykład:

W pętli pierwszej szukasz wszystkich TOKEN_OP_MUL (oraz _DIV) które
mają TOKEN_NUMBER po obu stronach, np.:

TOKEN_NUMBER, "2"
TOKEN_OP_MUL
TOKEN_NUMBER, "6"

I je zamieniasz in-place na token z wynikiem (tj. zamieniasz 
pierwszy number i usuwasz dwa pozostałe tokeny):

TOKEN_NUMBER, "12"

W drugiej pętli robisz to samo dla TOKEN_OP_ADD i TOKEN_OP_SUB.

W trzeciej pętli szukasz wszystkich nawiasów z liczbą w środku, i usuwasz 
nawiasy, tj.

TOKEN_PARENTHESIS_OPEN
TOKEN_NUMBER, "1234"
TOKEN_PARENTHESIS_CLOSE
↓
TOKEN_NUMBER, "1234"

I te 3 pętle powtarzasz do póki wielkość listy tokenów != 1

Na końcu będziesz miał jeden token z wynikiem na liście.

Od razu mówię, że to jest trochę hack i jest wolniejsze niż AST/RPN, ale jest też dużo prostsze w implementacji.

komentarz 5 stycznia przez Gynvael Coldwind Nałogowiec (27,950 p.)

A, i uwaga na słowo "całkowite" – Twój kod MUSI też liczby ujemne ogarniać.

2	komentarz 5 stycznia przez adrian17 Ekspert (345,160 p.) 1. brzmi dla mnie trochę odwrotnie, bo RPN (w sensie przynajmniej shunting yard i na bieżąco liczenie, nie trzeba przechowywać całego wynikowego RPN) brzmi prościej niż budowanie AST?

odpowiedź 4 stycznia przez dia_Chann Nowicjusz (180 p.)
edycja 5 stycznia przez Arkadiusz Waluk

#include <iostream>

#include <string>

 

std::string add(const std::string& num1, const std::string& num2) {

    return std::to_string(stoll(num1) + stoll(num2));

}

 

std::string subtract(const std::string& num1, const std::string& num2) {

    return std::to_string(stoll(num1) - stoll(num2));

}

 

std::string multiply(const std::string& num1, const std::string& num2) {

    return std::to_string(stoll(num1) * stoll(num2));

}

 

std::string divide(const std::string& num1, const std::string& num2) {

    if (stoll(num2) == 0) {

        return "Error: Division by zero";

    }

    return std::to_string(stoll(num1) / stoll(num2));

}

 

int main() {

    std::string num1, num2;

 

    std::cout << "Podaj pierwszą liczbę: ";

    std::getline(std::cin, num1);

 

    std::cout << "Podaj drugą liczbę: ";

    std::getline(std::cin, num2);

 

    std::string sum = add(num1, num2);

    std::string difference = subtract(num1, num2);

    std::string product = multiply(num1, num2);

    std::string quotient = divide(num1, num2);

 

    std::cout << "Suma: " << sum << std::endl;

    std::cout << "Różnica: " << difference << std::endl;

    std::cout << "Iloczyn: " << product << std::endl;

    std::cout << "Iloraz: " <<

quotient << std::endl;

 

    return 0;

}

komentarz 4 stycznia przez TOWaD Mądrala (6,000 p.)

Myślę że bardziej chodzi o Dodawanie, mnożenie przez dodawanie , a tu też dodawanie i zamiast operacji dodawania funkcje w tym przykładzie

komentarz 4 stycznia przez WirusTrojan Nowicjusz (130 p.)

no też byłem tego pewien ale mi sie udało zrobić dodawanie i odejmowanie

komentarz 4 stycznia przez WirusTrojan Nowicjusz (130 p.)

no i dzięki z góry

komentarz 5 stycznia przez Arkadiusz Waluk Ekspert (287,950 p.)

Prośba, aby na przyszłość wstawiać kod w przeznaczony do tego bloczek. Ponadto warto jakby odpowiedź jednak była konkretną pomocą, a nie gotowcem. Staramy się naprowadzać na rozwiązanie dając wskazówki do konkretnego problemu, a nie podając wszystko na gotowo. Raczej dążymy do tego, aby się wspólnie czegoś nauczyć i pomóc komuś zrozumieć, a nie aby wkleić coś bez żadnego wyjaśnienia.

komentarz 5 stycznia przez WirusTrojan Nowicjusz (130 p.)

nie no też masz racje Arkadiusz Waluk nawet krótkie komentarze w kodzie, ale ja już sobie to przejrzałem ten kod i wiem oco chodzi. Nawet jeszcze nigdy w życiu nie robiłem liczby na stringach :)

komentarz 5 stycznia przez Oscar Nałogowiec (29,320 p.)

Nawet long long nie wystarczy na wartości 100 cyfrowe. W zadaniu raczej chodzi o zaimplementowanie dodawania i mnożenia pisemnego - tak jak to uczą w szkole, cyferka po cyferce, najwyżej mamy dodatkowo coś "w pamięci". Akurat komputery pamięć mają dużą i dobrą....

komentarz 5 stycznia przez WirusTrojan Nowicjusz (130 p.)

Oscar wydaje mi sie być możliwe że long double by wystarczyło :D, ale tu nie może być typ zmiennej int i zmiennej przecinkowej żadnej tylko na stringach, jeszcze pisze że ma być sama bibliotek #include <iostream> bez innych bibliotek tylko biblioteka wejścia wyjścia takie jest zadanie.

komentarz 5 stycznia przez adrian17 Ekspert (345,160 p.)
edycja 5 stycznia przez adrian17

long double

Nie ma gwarancji że long double będzie większe od double, w szczególności w MSVC nie jest. W każdym razie precyzji na pewno nie wystarczy na 100-cyfrowe liczby.

Ogólnie zadanie trochę sprzecznie zdefiniowane, niby nie można używać nic poza <iostream> ale dostajesz na wejsciu stringi które są w <string>...? (i czemu wielka litera String?)

W każdym razie zgadzam się że na intuicję zadanie prosi o zaimplementowanie dodawania na stringach "pisemnego". W dodatku część o nawiasach sugeruje że to ma parsować całe wyrażenia typu "(1+6)*(8-3)"? Ale to dziwne że nie jest opisane jakkolwiek bardziej szczegółowo, w dodatku takie parsowanie wyrażeń brzmi jak osobne nietrywialne zadanie samo z siebie. W każdym razie na pewno nie brzmi jak coś co bez jakiegokolwiek przygotowania by można było napisać z ręki jako praca domowa, chyba że zajęcia akurat omawiały te tematy i autor pytania na nich nie był ;)

komentarz 5 stycznia przez WirusTrojan Nowicjusz (130 p.)

to jest też prawda że MSVC nie jest. Być możliwe ktoś też nie był na zajęciach i może ktoś zaimplementował żle pytanie :)

komentarz 5 stycznia przez Gynvael Coldwind Nałogowiec (27,950 p.)

@adrian17, jeśli mnie pamięć nie myli, u nas na studiach dali VLI/biginty po prostu na liście zadań ćwiczeniowych ze Wstępu do Programowania, bez tłumaczenia :D (tłumaczenie było pół roku później na Algorytmach i Strukturach Danych). Ale in all fairness nie było tam żadnych wyrażeń jak tutaj.

komentarz 5 stycznia przez Oscar Nałogowiec (29,320 p.)

@WirusTrojan, To akurat jest prosto oszacować - 3 cyfry dziesiętne (1000) odpowiada dość dokładnie 10 bitom (1024) czyli 100 cyfr dziesiętnych to ok 330 bitów.

komentarz 16 stycznia przez WirusTrojan Nowicjusz (130 p.)
edycja 17 stycznia przez WirusTrojan

@dia_Chann, chciałym sie zapytać czemu dwie dodatnie liczby na suma wychodzi ujemna?? tak samo jak na mnożeniu

Próbuje coś jakoś to rozwiązać

komentarz 18 stycznia przez TOWaD Mądrala (6,000 p.)
edycja 20 stycznia przez TOWaD

Może to jest spowodowanie przekroczeniem zakresu. Np:

#include <iostream>
using namespace std;
int main()
{
    //INT_MAX 	Maksymalna wartość zmiennej typu int. 	2147483647
    cout<<"INT_MAX="<<static_cast<int>(2147483647)<<'\n'; //2147483647
    cout<<"INT_MAX+1= "<<static_cast<int>(2147483648)<<'\n'; //-2147483648
    //UINT_MAX 	Maksymalna wartość zmiennej typu unsigned int. 	4294967295
    cout<<"UINT_MAX = "<<static_cast<unsigned int>(4294967295)<<'\n'; //4294967295
    cout<<"rzutowanie na INT= "<<static_cast<int>(4294967295)<<endl; //-1
    return 0;
}

to samo [online]

edit:: oczywiście nalezys się zapoznać co najmniej z tym lub z tym. Przypisanie wartości większej niż zarezerwowana do zmiennej to poważny błąd.

komentarz 18 stycznia przez TOWaD Mądrala (6,000 p.)

A tutaj moja taka propozycja (na razie dodawanie liczb dodatnich i niekoniecznie poprawnie : ) ): tylko: nie nie umiem c++ i używam go rzadko i tylko hobbistycznie, wiec:

1) Projekt nie ma wartości merytorycznych.

2) Będzie miał może wartości edukacyjne jak dodam opisy. I jak będę miał czas i natchnienie by skończyć.

3) Myślę trochę inny pomysł niż ogólnie na forach. Polega na trzymaniu wartości w tablicach char cyfry w odwrotnej kolejności i używanie char jako liczby.