Modular Arithmetic Calculator

ModCalculator.cpp

//Modular Arithmetic Calculator(According to Fermat's little theorem)
//So some of the calculations can not be done.
//Also can be used as Expression Calculator if change "ModNumber" to INT_MAX in CalculationElement Class

#include <algorithm>
#include <stack>
#include <list>
#include <vector>
#include <map>

#include <string>
#include <iostream>
#include <cstdlib>
#include <map>

#include <cmath>

using namespace std;

const int MAX_CALCULATION_ELEMENT = 10000;

const int EXPR_ADD = 1;
const int EXPR_SUB = 2;
const int EXPR_MUL = 3;
const int EXPR_DIV = 4;
const int EXPR_LOP = 5;
const int EXPR_ROP = 6;




class ModSystem
{
private:
	map<int, int>NegativeMap;
	int GCD(int a, int b)
	{
		int c;
		if (a < b)swap(a, b);
		while (true)
		{
			c = a%b;
			if (c == 0)break;
			a = b; b = c;
		}
		return b;
	}
	bool isPrime(int p)
	{
		int end = sqrt(p);
		for (int i = 2; i <= end; i++)
		{
			if (p%i == 0)return false;
		}
		return true;
	}
public:
	ModSystem(int _ModNumber)
	{
		this->_ModNumber = _ModNumber;
		NegativeMap.clear();
		if (!isPrime(_ModNumber))cerr << "Warning: Calculation Result may be wrong because it doesn't meet the condition of Fermat Theory." << endl;
	}
	int _ModNumber;
	int GetNegative(int number)
	{
		if (GCD(number, _ModNumber) != 1)cerr << "Warning: Calculation Result may be wrong because it doesn't meet the condition of Fermat Theory." << endl;
		if (NegativeMap.find(number) != NegativeMap.end())
		{
			return NegativeMap[number];
		}
		int m = _ModNumber - 2;
		int k = number, result = 1;
		while (m > 0)
		{
			if (m % 2 == 1)result = (result*k) % _ModNumber;
			k = (k*k) % _ModNumber;
			m /= 2;
		}
		NegativeMap[number] = result;
		return result;
	}
};
ModSystem *GlobalSystem;
class ModNumber
{
public:
	ModSystem *System;
	int Number;
	ModNumber()
	{
		System = GlobalSystem;
		Number = 0;
	}
	ModNumber(ModSystem *System)
	{
		this->System = System;
	}
	ModNumber(int Number, ModSystem *System)
	{
		this->System = System;
		this->Number = Number;
		this->Settle();
	}
	ModNumber(const ModNumber &Number)
	{
		this->System = Number.System;
		this->Number = Number.Number;
	}
	void Settle()
	{
		Number %= System->_ModNumber;
		if (Number < 0)Number += System->_ModNumber;
	}

	void BeforeCalculate(const ModNumber &a, const ModNumber &b)
	{
		if (a.System != b.System)cerr << "Calculation Invaild." << endl;
	}


	ModNumber& operator=(const int Number)
	{
		this->Number = Number;
		this->Settle();
		return *this;
	}

	ModNumber &operator += (const ModNumber &Number)
	{
		BeforeCalculate(*this, Number);
		this->Number += Number.Number;
		this->Settle();
		return *this;
	}
	ModNumber operator + (const ModNumber &Number)
	{
		BeforeCalculate(*this, Number);
		ModNumber Result(*this);
		Result += Number;
		return Result;
	}
	ModNumber &operator -= (const ModNumber &Number)
	{
		BeforeCalculate(*this, Number);
		this->Number -= Number.Number;
		this->Settle();
		return *this;
	}
	ModNumber operator - (const ModNumber &Number)
	{
		BeforeCalculate(*this, Number);
		ModNumber Result(*this);
		Result -= Number;
		return Result;
	}
	ModNumber &operator *= (const ModNumber &Number)
	{
		BeforeCalculate(*this, Number);
		this->Number *= Number.Number;
		this->Settle();
		return *this;
	}
	ModNumber operator * (const ModNumber &Number)
	{
		BeforeCalculate(*this, Number);
		ModNumber Result(*this);
		Result *= Number;
		return Result;
	}
	ModNumber &operator /= (const ModNumber &Number)
	{
		BeforeCalculate(*this, Number);
		this->Number *= System->GetNegative(Number.Number);
		this->Settle();
		return *this;
	}
	ModNumber operator / (const ModNumber &Number)
	{
		BeforeCalculate(*this, Number);
		ModNumber Result(*this);
		Result /= Number;
		return Result;
	}
};

class CalculationElement
{
public:
	bool isNumber;
	ModNumber number;
	int expr;
};




class CalculationData
{
public:
	list<CalculationElement>CalculationElements;
	static CalculationData* Create(string str)
	{
		CalculationData *dat = new CalculationData();
		int tmpNumber = 0;
		str += '#';
		bool requirePush = false;
		for (int i = 0; i < str.size(); i++)
		{
			char processCH = str[i];
			if ('0' <= processCH && processCH <= '9')
			{
				requirePush = true;
				tmpNumber = tmpNumber * 10 + (int)(processCH - '0');
			}
			if (processCH == '+' || processCH == '-' || processCH == '*' || processCH == '/' || processCH == '(' || processCH == ')' || processCH == '#')
			{
				int PushExpr = 0;
				if (processCH == '+'){ PushExpr = EXPR_ADD; }
				if (processCH == '-'){ PushExpr = EXPR_SUB; }
				if (processCH == '*'){ PushExpr = EXPR_MUL; }
				if (processCH == '/'){ PushExpr = EXPR_DIV; }
				if (processCH == '('){ PushExpr = EXPR_LOP; }
				if (processCH == ')'){ PushExpr = EXPR_ROP; }
				if (requirePush)
				{
					CalculationElement num;
					num.isNumber = true; num.number = tmpNumber; num.expr = -1;
					dat->CalculationElements.push_back(num);
					tmpNumber = 0;
				}
				CalculationElement expr;
				expr.isNumber = false; expr.expr = PushExpr; expr.number = 0;
				dat->CalculationElements.push_back(expr);
				requirePush = false;
			}
		}
		dat->CalculationElements.pop_back();
		return dat;
	}
};

class Calculator
{
private:
	static void ___Calculate(list<CalculationElement> &List, list<CalculationElement>::iterator &Begin, list<CalculationElement>::iterator &End, int FirstCalculate, int SecondCalculate)
	{
		for (list<CalculationElement>::iterator iter = Begin; iter != End; iter++)
		{
			if (!iter->isNumber)
			{
				if (iter->expr == FirstCalculate || iter->expr == SecondCalculate)
				{
					list<CalculationElement>::iterator iterExpr = iter;
					list<CalculationElement>::iterator iterCurrent = --iter;
					iter++; iter++;
					list<CalculationElement>::iterator iterNext = iter;
					if (iterExpr->expr == EXPR_MUL)
					{
						iterCurrent->number *= iterNext->number;
					}
					if (iterExpr->expr == EXPR_DIV)
					{
						iterCurrent->number /= iterNext->number;
					}
					if (iterExpr->expr == EXPR_ADD)
					{
						iterCurrent->number += iterNext->number;
					}
					if (iterExpr->expr == EXPR_SUB)
					{
						iterCurrent->number -= iterNext->number;
					}
					List.erase(iterExpr);
					List.erase(iterNext);
					iter = iterCurrent;
				}
			}
		}
	}
	static void __Calculate(list<CalculationElement> &List, list<CalculationElement>::iterator &Begin, list<CalculationElement>::iterator &End)
		//Calcute Expression from Begin to End and save result in Begin
	{
		cout << "Calculating Expression ";
		PrintList(Begin, End);
		___Calculate(List, Begin, End, EXPR_MUL, EXPR_DIV);
		___Calculate(List, Begin, End, EXPR_ADD, EXPR_SUB);
		cout << " = " << Begin->number.Number << endl;
	}

	static list<CalculationElement>::iterator __Next(bool isBegin, list<CalculationElement>::iterator &iter)
	{
		if (!isBegin)return ++iter;
		return iter;
	}
public:
	static void PrintList(list<CalculationElement>::iterator Begin, list<CalculationElement>::iterator End)
	{
		for (list<CalculationElement>::iterator iter = Begin; iter != End; iter++)
		{
			if (iter->isNumber)cout << iter->number.Number;
			if (!iter->isNumber)
			{
				if (iter->expr == EXPR_ADD)cout << "+";
				if (iter->expr == EXPR_SUB)cout << "-";
				if (iter->expr == EXPR_MUL)cout << "*";
				if (iter->expr == EXPR_DIV)cout << "/";
				if (iter->expr == EXPR_LOP)cout << "(";
				if (iter->expr == EXPR_ROP)cout << ")";
			}
		}
	}

	static ModNumber Calculate(CalculationData *Dat)
	{
		bool requireBack = false;
		stack<list<CalculationElement>::iterator>requireCalculate;
		for (list<CalculationElement>::iterator iter = Dat->CalculationElements.begin(); iter != Dat->CalculationElements.end();)
		{

			if (!iter->isNumber)
			{
				if (iter->expr == EXPR_LOP)
				{
					requireCalculate.push(iter);
				}
				if (iter->expr == EXPR_ROP)
				{
					if (requireCalculate.empty())
					{
						cerr << "Error while calculating." << endl; return 0;
					}
					list<CalculationElement>::iterator iterLeft = requireCalculate.top();
					requireCalculate.pop();
					list<CalculationElement>::iterator iterRight = iter;

					list<CalculationElement>::iterator tmpIter = iterLeft;
					tmpIter++;
					list<CalculationElement>::iterator iterRealLeft = tmpIter;

					tmpIter = iterRight;
					list<CalculationElement>::iterator iterRealRight = tmpIter;
					Calculator::__Calculate(Dat->CalculationElements, iterRealLeft, iterRealRight);
					iter = iterLeft;
					if (iter == Dat->CalculationElements.begin())
					{
						requireBack = true;
					}
					else
					{
						iter--;
					}
					Dat->CalculationElements.erase(iterLeft);
					Dat->CalculationElements.erase(iterRight);
				}
			}
			if (!requireBack)
			{
				iter++;
			}
			else
			{
				requireBack = false;
				iter = Dat->CalculationElements.begin();
			}
			if (Dat->CalculationElements.size() <=1)
			{
				break;
			}
		}
		if (!requireCalculate.empty())
		{
			cerr << "Error while calculating." << endl; return 0;
		}
		Calculator::__Calculate(Dat->CalculationElements, Dat->CalculationElements.begin(), Dat->CalculationElements.end());
		return Dat->CalculationElements.begin()->number;
	}
};



int main(int argc, char* argv[])
{
	int tmp;
	cout << "ModSystem ModNumber: ";
	cin >> tmp;
	GlobalSystem = new ModSystem(tmp);
	string str;
	cout << "Expression: ";
	cin >> str;
	CalculationData *dat = CalculationData::Create(str);
	cout << "Result = " << Calculator::Calculate(dat).Number << endl;
	system("PAUSE");
	return 0;
}