Zadanie z C++

Question

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

Answer 1

@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.

Comments

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

---

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?

Answer 2

#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;

}

Comments

@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.

---

@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.

---

@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ć

---

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.

---

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.