// This class enables larger numbers than what is defined by INT_MAX in c++ // // To use: (PC for actual results) // 1. Enter a Large Integer (ie 123456789012345678901234567890123456789) // 2. Enter an operator (ie + - / * ) // 3. Enter another number // 4. Enter = to quit // // source: https://secure-media.collegeboard.org/apc/ap01.pdf.lr_7928.pdf // author: Owen Astrachan // 8/23/95, modified 7/5/96 // modified 1/5/97 // // implements an arbitrary precision integer class // // constructors: // // BigInt() — default constructor, value of integers is 0 // BigInt(int n) — initialize to value of n (C++ int) // BigInt(const string & s) — initialize to value specified by s // it is an error if s is an invalid integer, e.g., // "1234abc567". In this case the bigint value is garbage // // NOTE: Line 193 ( abort() ) Must be uncommented on PC to catch malformed numbers i.e 1234fsdfgb34455425 // // // ***** arithmetic operators: // // all arithmetic operators +, -, * are overloaded both // in form +=, -=, *= and as binary operators // // multiplication also overloaded for *= int // e.g., BigInt a *= 3 (mostly to facilitate implementation) // // ***** logical operators: // // bool operator == (const BigInt & lhs, const BigInt & rhs) // bool operator != (const BigInt & lhs, const BitInt & rhs) // bool operator < (const BigInt & lhs, const BigInt & rhs) // bool operator <= (const BigInt & lhs, const BigInt & rhs) // bool operator > (const BigInt & lhs, const BigInt & rhs) // bool operator >= (const BigInt & lhs, const BigInt & rhs) // // ***** I/O operators: // // void Print() // prints value of BigInt (member function) // ostream & operator << (ostream & os, const BigInt & b) // stream operator to print value // // istream & operator >> (istream & in, const BigInt & b) // reads whitespace delimited BigInt from input stream in //TODO: ** ToInt, ** ToDouble conversions, ** Add Power Function to calculator //BigInt.h #include #include #include #include const int BASE = 10; // for base 10 numbering system class BigInt { public: BigInt(); // default constructor, value = 0; BigInt(int); // assign an integer value BigInt(const std::string &); // assign a string //operators: arithmetic, relational const BigInt & operator +=(const BigInt &); const BigInt & operator -= (const BigInt &); const BigInt & operator *= (const BigInt &); const BigInt & operator *= (int num); BigInt & operator++(); BigInt & operator--(); std::string ToString() const; //convert to string int ToInt() const; //convert to int double ToDouble() const; //convert to double // facilitate operators ==, <, << without friends bool Equal(const BigInt & rhs) const; bool LessThan(const BigInt & rhs) const; void Print(std::ostream & os) const; private: //other helper functions bool IsNegative() const; // return true if number is negative bool IsPositive() const; // return true if number is positive int NumDigits() const; // returns the number of digits in the number int GetDigit(int k) const; // Returns digit at k-th position void AddSigDigit(int value); // Add number as most significant digit to BigInt void ChangeDigit(int k, int value); // Changes Digit at k-th position to value void Normalize(); // remove all leading zeros // state/instance variables enum Sign{positive, negative}; Sign mSign; // is the number positive or negative std::vector mDigits; //stores all the digits of the number int mNumDigits; //stores the number of digits of the number }; //free functions std::ostream & operator <<(std::ostream &, const BigInt &); std::istream & operator >>(std::istream &, BigInt &); BigInt operator +(const BigInt & lhs, const BigInt & rhs); BigInt operator -(const BigInt & lhs, const BigInt & rhs); BigInt operator *(const BigInt & lhs, const BigInt & rhs); BigInt operator *(const BigInt & lhs, int num); BigInt operator *(int num, const BigInt & rhs); bool operator == (const BigInt & lhs, const BigInt rhs); bool operator != (const BigInt & lhs, const BigInt rhs); bool operator > (const BigInt & lhs, const BigInt rhs); bool operator < (const BigInt & lhs, const BigInt rhs); bool operator >= (const BigInt & lhs, const BigInt rhs); bool operator <= (const BigInt & lhs, const BigInt rhs); //BigInt.cpp BigInt::BigInt() //postcondition: BigInt initialized to 0 : mSign(positive), mDigits(1,'0'), mNumDigits(1) { //all fields initialized in the initializer list } BigInt::BigInt(int num) //postcondition: BigInt initialized to num : mSign(positive), mDigits(1,'0'), mNumDigits(1) { //check if num is negative, chage state and num accordingly if(num < 0){ mSign = negative; num = -1 * num; } //handle least significant digit of number (handles num == 0) AddSigDigit(num % BASE); num = num / BASE; //handle remaining digits of num while (num != 0) { AddSigDigit(num % BASE); num = num / BASE; } } BigInt::BigInt(const std::string &s) // precondition: s consists of digits only, optionally preceded by + or - // postcondition: BigInt initialized to integer represented by s // if s is not a well formed BigInt (e.g contains non-digit // characters) then an error message is printed and abort called : mSign(positive), mDigits(s.length(), '0'), mNumDigits(0) { int limit = 0; if (s.length() == 0) { mDigits.resize(1); AddSigDigit(0); return; } if(s[0] == '-') { mSign = negative; limit = 1; } if (s[0] == '+') { limit = 1; } //start at least significant digit (from right) for (int k = s.length() - 1; k >= limit; --k) { if (!std::isdigit(s[k])) { std::cerr << "badly formed BigInt value = " << s << std::endl; //abort(); //UNCOMMENT THIS WHEN ON PC } AddSigDigit(s[k] - '0'); } Normalize(); } const BigInt & BigInt::operator+=(const BigInt & rhs) //postcondition: returns value of BigInt + rhs after addition { int sum; int carry = 0; int len = NumDigits(); if (IsPositive() != rhs.IsPositive()) //signs not the same, subtract { *this -= (-1 * rhs); return *this; } //process both numbers until one is exhausted if (len < rhs.NumDigits()) { //biggest number on top len = rhs.NumDigits(); } for (int k = 0; k < len; ++k) { sum = GetDigit(k) + rhs.GetDigit(k) + carry; carry = sum / BASE; sum = sum % BASE; if (k < mNumDigits) { ChangeDigit(k, sum); } else { AddSigDigit(sum); } } if (carry != 0) { AddSigDigit(carry); } return *this; } const BigInt & BigInt::operator-=(const BigInt & rhs) { int diff; int borrow = 0; int len = NumDigits(); if (this == &rhs) //subtracting self { *this = 0; return *this; } //signs opposite? then lhs - (-rhs) = lhs + rhs if (IsNegative() != rhs.IsNegative()) { *this += (-1 * rhs); return *this; } // signs are the same, check which number is larger // and switch to get the larger number "on top" if necessary // since sign can change when subtracting // examples: // 7 - 3 no sign changes // 3 - 7 sign chages // -7 - (-3) no sign change // -3 - (-7) sign change if (IsPositive() && (*this) < rhs || IsNegative() && (*this) > rhs) { *this = rhs - *this; if (IsPositive()) mSign = negative; else mSign = positive; //toggle sign return *this; } //same sign and larger number on top for (int k = 0; k < len; ++k) { diff = GetDigit(k) - rhs.GetDigit(k) - borrow; borrow = 0; if (diff < 0) { diff += 10; borrow = 1; } ChangeDigit(k, diff); } Normalize(); return *this; } const BigInt & BigInt::operator*=(const BigInt & rhs) //postcondition: returns the value of BigInt * rhs after multiplication { //uses standard method for multiplying if (IsNegative() != rhs.IsNegative()) { mSign = negative; } else { mSign = positive; } BigInt self(*this); //copy of self BigInt sum(0); // to accumulate sum int len = rhs.NumDigits(); //# digits in multiplier for (int k = 0; k < len; ++k) { sum += self * rhs.GetDigit(k); //k-th digit * self; self *= 10; //add a zero } *this = sum; return *this; } const BigInt & BigInt::operator*=(int num) //precondition: 0 <= num <= BASE //postcondition: returns num * value of BigInt after multiplication { int carry = 0; int product; int len = NumDigits(); if (0 == num) // treat zero as a special case and stop { *this = 0; return *this; } if (BASE < num || num < 0) // handle pre-condition failure { *this *= BigInt(num); return *this; } if (1 == num) // treat one as special case, no work (num * 1 = num) { return *this; } for (int k = 0; k < len; ++k) //once for each digit { product = num * GetDigit(k) + carry; carry = product / BASE; ChangeDigit(k, product % BASE); } while (carry != 0) { AddSigDigit(carry % BASE); carry /= BASE; } return *this; } std::ostream & operator<<(std::ostream & out, const BigInt &big) //postcondition: BigInt inserted onto stream out { big.Print(out); return out; } std::istream & operator>>(std::istream & in, BigInt & big) // postcondition: big extracted from in, must be whitespace delimted { std::string s; in >> s; big = BigInt(s); return in; } BigInt operator+(const BigInt & lhs, const BigInt & rhs) //postcondition: returns a bigint whose value is lhs+rhs { BigInt result(lhs); result += rhs; return result; } BigInt operator-(const BigInt & lhs, const BigInt & rhs) //postcondition: returns a BigInt whose value is lhs - rhs { BigInt result(lhs); result -= rhs; return result; } BigInt operator*(const BigInt & lhs, const BigInt & rhs) //postcondition: returns a BigInt whose value is lhs * rhs { BigInt result(lhs); result *= rhs; return result; } BigInt & BigInt::operator++() //precondition: BigInt = a; //postcondition: BigInt = a + 1, returns a + 1 { *this += 1; return *this; } BigInt & BigInt::operator--() //precondition: BigInt = a //postcondition: BigInt = a - 1, return a - 1 { *this -= 1; return *this; } std::string BigInt::ToString() const //postcondition: returns string equivalent of BigInt { int len = NumDigits(); std::string s = ""; if (IsNegative()) { s = "-"; } for (int k = len - 1; k >= 0; --k) { s += char('0' + GetDigit(k)); } return s; } int BigInt::ToInt() const { return 0; } double BigInt::ToDouble() const { return 0.0; } bool BigInt::Equal(const BigInt & rhs) const //postcondition: returns true if self == rhs, ekse returns false { if (NumDigits() != rhs.NumDigits() || IsNegative() != rhs.IsNegative()) { return false; } //assert: same sign, same number of digits int len = NumDigits(); for (int k = 0; k < len; ++k) { if (GetDigit(k) != rhs.GetDigit(k)) return false; } return true; } bool BigInt::LessThan(const BigInt & rhs) const //postcondition: return true if self < rhs, else return false { //if signs are not equal, self < rhs only if self is negative if (IsNegative() != rhs.IsNegative()) { return IsNegative(); } // if #digits are not the same must check digits and sign if (NumDigits() != rhs.NumDigits()) { return (NumDigits() < rhs.NumDigits() && IsPositive()) || (NumDigits() > rhs.NumDigits() && IsNegative()); } //assert: #number of digits the same, signs the same int len = NumDigits(); for (int k = len - 1; k >= 0; --k) { if (GetDigit(k) < rhs.GetDigit(k)) return IsPositive(); if (GetDigit(k) > rhs.GetDigit(k)) return IsNegative(); } return false; // self == rhs } void BigInt::Print(std::ostream & os) const { os << ToString(); } bool BigInt::IsNegative() const { return mSign == negative; } bool BigInt::IsPositive() const { return mSign == positive; } int BigInt::NumDigits() const { return mNumDigits; } int BigInt::GetDigit(int k) const //precondition: 0 <=k < NumDigits() //postcondition: returns k-th digit // (0 if precondition is false) // Note: 0th digit is least significant digit { if (0 <= k && k < NumDigits()) { return mDigits[k] - '0'; } return 0; } void BigInt::AddSigDigit(int value) //postcondition: value added to BigInt as most significant digit // Note: 0th digit is least significant digit { if(mNumDigits >= int(mDigits.size())) { mDigits.resize(mDigits.size() * 2); } mDigits[mNumDigits] = char('0' + value); mNumDigits++; } void BigInt::ChangeDigit(int k, int value) //precondition: 0 <= k < NumDigits() //postcondition: k-th digit chaged to value // Note: 0th digit is least significant digit { if (0 <= k && k < NumDigits()) { mDigits[k] = char('0' + value); } else { std::cerr << "error ChangeDigit " << k << " " << mNumDigits << std::endl; } } void BigInt::Normalize() //postcondition: all leading zeros removed { int k; int len = NumDigits(); for (k = len - 1; k >= 0; --k) { if (GetDigit(k) != 0) break; mNumDigits--; } if (k < 0) //all zeros { mNumDigits = 1; mSign = positive; } } BigInt operator*(const BigInt & lhs, int num) //postcondition: returns lhs * num { BigInt result(lhs); result *= num; return result; } BigInt operator*(int num, const BigInt & rhs) //postcondition: return num * rhs { BigInt result(rhs); result *= num; return result; } bool operator==(const BigInt & lhs, const BigInt rhs) //postcondition: returns true if lhs == rhs, else return false { return lhs.Equal(rhs); } bool operator!=(const BigInt & lhs, const BigInt rhs) { return !(lhs == rhs); } bool operator>(const BigInt & lhs, const BigInt rhs) { return rhs < lhs; } bool operator<(const BigInt & lhs, const BigInt rhs) //postcondition: returns true if lhs < rhs, else return false; { return lhs.LessThan(rhs); } bool operator>=(const BigInt & lhs, const BigInt rhs) { return lhs == rhs || lhs > rhs; } bool operator<=(const BigInt & lhs, const BigInt rhs) //postcondition: return true if lhs <= rhs, else return false { return lhs == rhs || lhs < rhs; } BigInt power(const BigInt & a, int n) { if (n == 0) return 1; if (n == 1) return a; BigInt semi = power(a, n / 2); semi *= semi; // this is semi^2 if (n % 2 == 0) return semi; else return semi * a; } // A three function calculator enum OpType { add, subtract, multiply, stop, illegal_op}; OpType StringToOp(const std::string &s); //String to Operator Function Definition OpType GetOperator(); // get Operator Function Definition int main() { BigInt accumulator = 0; // accumulate in this object BigInt current; //value to be operated with OpType op = add; //so first value is added to zero while (op != stop) { std::cout << "Enter Value:"; std::cin >> current; std::cout << std::endl; switch (op) { case add: accumulator += current; break; case subtract: accumulator -= current; break; case multiply: accumulator *= current; break; default: std::cerr << "error with operator" << std::endl; } std::cout << "----> " << accumulator << std::endl; op = GetOperator(); } return 0; } OpType StringToOp(const std::string &s) // precondition: s is a valid operator // postcondition: returns OpType equivalent e.g add for +; { //define array of strings to facilitate lookup std::string OPSTRINGS[] = { "+", "-", "*", "=" }; const int NUMOPS = 4; //number of valid operations for (int k = 0; k < NUMOPS; ++k) { if (s == OPSTRINGS[k]) return OpType(k); } return illegal_op; // not found, return illegal op } OpType GetOperator() // postconsition: reads a whitespace delimited operator from cin and returns the operator { std::string s; OpType returnValue; do { std::cout << "enter + - * (= to quit): "; std::cin >> s; std::cout << std::endl; } while ((returnValue = StringToOp(s)) == illegal_op); return returnValue; }

Large Integer Calculator