# C++: Balanced Ternary

Balanced ternary is a way of representing numbers. Unlike the prevailing binary representation, a balanced ternary integer is in base 3, and each digit can have the values 1, 0, or −1. For example, decimal 11 = 32 + 31 − 30, thus can be written as “++−”, while 6 = 32 − 31 + 0 × 30, i.e., “+−0”.

For this task, implement balanced ternary representation of integers with the following

Requirements

1. Support arbitrarily large integers, both positive and negative;
2. Provide ways to convert to and from text strings, using digits ‘+’, ‘-‘ and ‘0’ (unless you are already using strings to represent balanced ternary; but see requirement 5).
3. Provide ways to convert to and from native integer type (unless, improbably, your platform’s native integer type is balanced ternary). If your native integers can’t support arbitrary length, overflows during conversion must be indicated.
4. Provide ways to perform addition, negation and multiplication directly on balanced ternary integers; do not convert to native integers first.
5. Make your implementation efficient, with a reasonable definition of “effcient” (and with a reasonable definition of “reasonable”).

Test case With balanced ternaries a from string “+-0++0+”, b from native integer -436, c “+-++-“:

• write out a, b and c in decimal notation;
• calculate a × (bc), write out the result in both ternary and decimal notations.

```#include <iostream>
#include <string>
#include <climits>
using namespace std;

class BalancedTernary {
protected:
// Store the value as a reversed string of +, 0 and - characters
string value;

// Helper function to change a balanced ternary character to an integer
int charToInt(char c) const {
if (c == '0')
return 0;
return 44 - c;
}

// Helper function to negate a string of ternary characters
string negate(string s) const {
for (int i = 0; i < s.length(); ++i) {
if (s[i] == '+')
s[i] = '-';
else if (s[i] == '-')
s[i] = '+';
}
return s;
}

public:
// Default constructor
BalancedTernary() {
value = "0";
}

// Construct from a string
BalancedTernary(string s) {
value = string(s.rbegin(), s.rend());
}

// Construct from an integer
BalancedTernary(long long n) {
if (n == 0) {
value = "0";
return;
}

bool neg = n < 0;
if (neg)
n = -n;

value = "";
while (n != 0) {
int r = n % 3;
if (r == 0)
value += "0";
else if (r == 1)
value += "+";
else {
value += "-";
++n;
}

n /= 3;
}

if (neg)
value = negate(value);
}

// Copy constructor
BalancedTernary(const BalancedTernary &n) {
value = n.value;
}

BalancedTernary operator+(BalancedTernary n) const {
n += *this;
return n;
}

BalancedTernary& operator+=(const BalancedTernary &n) {
static char *carry = "--000++";

int lastNonZero = 0;
char c = '0';
for (int i = 0; i < value.length() || i < n.value.length(); ++i) {
char a = i < value.length() ? value[i] : '0';
char b = i < n.value.length() ? n.value[i] : '0';

int sum = charToInt(a) + charToInt(b) + charToInt(c) + 3;
c = carry[sum];

if (i < value.length())
else

lastNonZero = i;
}

if (c != '0')
value += c;
else
value = value.substr(0, lastNonZero + 1); // Chop off leading zeroes

return *this;
}

// Negation operator
BalancedTernary operator-() const {
BalancedTernary result;
result.value = negate(value);
return result;
}

// Subtraction operators
BalancedTernary operator-(const BalancedTernary &n) const {
return operator+(-n);
}

BalancedTernary& operator-=(const BalancedTernary &n) {
return operator+=(-n);
}

// Multiplication operators
BalancedTernary operator*(BalancedTernary n) const {
n *= *this;
return n;
}

BalancedTernary& operator*=(const BalancedTernary &n) {
BalancedTernary pos = *this;
BalancedTernary neg = -pos; // Storing an extra copy to avoid negating repeatedly
value = "0";

for (int i = 0; i < n.value.length(); ++i) {
if (n.value[i] == '+')
operator+=(pos);
else if (n.value[i] == '-')
operator+=(neg);
pos.value = '0' + pos.value;
neg.value = '0' + neg.value;
}

return *this;
}

// Stream output operator
friend ostream& operator<<(ostream &out, const BalancedTernary &n) {
out << n.toString();
return out;
}

// Convert to string
string toString() const {
return string(value.rbegin(), value.rend());
}

// Convert to integer
long long toInt() const {
long long result = 0;
for (long long i = 0, pow = 1; i < value.length(); ++i, pow *= 3)
result += pow * charToInt(value[i]);
return result;
}

// Convert to integer if possible
bool tryInt(long long &out) const {
long long result = 0;
bool ok = true;

for (long long i = 0, pow = 1; i < value.length() && ok; ++i, pow *= 3) {
if (value[i] == '+') {
ok &= LLONG_MAX - pow >= result; // Clear ok if the result overflows
result += pow;
} else if (value[i] == '-') {
ok &= LLONG_MIN + pow <= result; // Clear ok if the result overflows
result -= pow;
}
}

if (ok)
out = result;
return ok;
}
};

int main() {
BalancedTernary a("+-0++0+");
BalancedTernary b(-436);
BalancedTernary c("+-++-");

cout << "a = " << a << " = " << a.toInt() << endl;
cout << "b = " << b << " = " << b.toInt() << endl;
cout << "c = " << c << " = " << c.toInt() << endl;

BalancedTernary d = a * (b - c);

cout << "a * (b - c) = " << d << " = " << d.toInt() << endl;

BalancedTernary e("+++++++++++++++++++++++++++++++++++++++++");

long long n;
if (e.tryInt(n))
cout << "e = " << e << " = " << n << endl;
else
cout << "e = " << e << " is too big to fit in a long long" << endl;

return 0;
}
```

### Output:

```a = +-0++0+ = 523
b = -++-0-- = -436
c = +-++- = 65
a * (b - c) = ----0+--0++0 = -262023
e = +++++++++++++++++++++++++++++++++++++++++ is too big to fit in a long long```

SOURCE

Content is available under GNU Free Documentation License 1.2.