Calculator

SimpleCalculator.cpp

#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <map>
#include <stack>
#include <sstream>

using namespace std;

enum TokenType { 
	ttNumber = 0,
	ttBracketLeft,
	ttBracketRight,
	ttOperator,
	ttFunction,
	ttVariable,
	ttUnknown
};

struct Token
{
	string value;
	TokenType type;
};

map<string, double(*)(double)> functionTable;
map<string, double> variableTable;

struct treeNode
{
	string token;
	TokenType type;

};

void makeError(string str) {
	cerr << "[Error]: " << str << endl;
	exit(1);
}

string strFromConsoleInput() {
	char buf[256];
	cin.getline(buf, sizeof(buf));
	return string(buf);
}

vector<string> tokenListFromString(string source) {
	vector<string> result;

	source.push_back('\b');
	string token = "";

	for (size_t i = 0; i < source.length(); i++) {
		if (!isalnum(source[i]) && source[i] != '.') {
			if (token != "") {
				result.push_back(token);
				token = "";
			}
			char c = source[i];
			if (c == '(' || c == ')' || 
				c == '+' || c == '-' || 
				c == '*' || c == '/') {

				token.push_back(c);
				result.push_back(token);
				token = "";
			}
		}
		else token.push_back(source[i]);
	}

	return result;
}

std::vector<TokenType> tokenTypeListFromTokens(vector<string> tokens) {
	vector<TokenType> result;

	TokenType type = ttUnknown;

	for (size_t i = 0; i < tokens.size(); i++) {
		if (tokens[i] == "(") {
			type = ttBracketLeft;
			if (i != 0 && result[i - 1] == ttVariable) {
				result[i - 1] = ttFunction;
			}
		}
		else if (tokens[i] == ")") {
			type = ttBracketRight;
		}
		else if (tokens[i] == "+" || tokens[i] == "-" ||
				 tokens[i] == "/" || tokens[i] == "*") {
			type = ttOperator;
		}
		else if (isdigit(tokens[i][0])) {
			size_t dotCount = 0;
			for (size_t j = 0; j < tokens[i].length(); j++) {
				if (!isdigit(tokens[i][j])) {
					if (tokens[i][j] == '.') dotCount++;
				}
				if (dotCount > 1) {
					makeError("Wrong floating point number format.");
				}
			}
			type = ttNumber;
		}
		else {
			for (size_t j = 0; j < tokens[i].size(); j++) {
				if (!isalnum(tokens[i][j])) {
					makeError("Wrong symbols in variable name.");
				}
			}
			type = ttVariable;
		}
		result.push_back(type);
	}

	return result;
}

bool checkNextValue(vector<TokenType> & tokens, size_t current, TokenType type) {
	if (current + 1 >= tokens.size()) 
		return false;
	return (tokens[current + 1] == type);
}

bool checkSyntax(vector<TokenType> & tokens) {
	TokenType last = ttUnknown;
	for (size_t i = 0; i < tokens.size(); i++) {
		switch (tokens[i]) {
			case ttNumber: {
				if (i == tokens.size()-1) return true;
				if (!checkNextValue(tokens, i, ttOperator) &&
					!checkNextValue(tokens, i, ttBracketRight)) return false;
				break;
			}
			case ttOperator: {
				if (i == 0) return false;
				if (last == ttBracketLeft) return false;
				if (!checkNextValue(tokens, i, ttBracketLeft) &&
					!checkNextValue(tokens, i, ttVariable) &&
					!checkNextValue(tokens, i, ttFunction) &&
					!checkNextValue(tokens, i, ttNumber)) return false;
				break;
			}
			case ttFunction: {
				if (i == tokens.size()-1) return false;
				if (!checkNextValue(tokens, i, ttBracketLeft)) return false;
				break;
			}
			case ttVariable: {
				if (i == tokens.size()-1) return true;
				if (!checkNextValue(tokens, i, ttOperator) &&
					!checkNextValue(tokens, i, ttBracketRight)) return false;
				break;
			}
			case ttBracketLeft: {
				if (i == tokens.size()-1) return false;
				if (!checkNextValue(tokens, i, ttNumber) &&
					!checkNextValue(tokens, i, ttBracketLeft) &&
					!checkNextValue(tokens, i, ttVariable) &&
					!checkNextValue(tokens, i, ttFunction)) return false;
				break;
			}
			case ttBracketRight: {
				if (i == tokens.size()-1) return true;
				if (!checkNextValue(tokens, i, ttOperator) &&
					!checkNextValue(tokens, i, ttBracketRight)) return false;
				break;
			}
		}
		last = tokens[i];
	}
	return true;
}

double neg(double d) {
	return -d;
}

void initializeFunctionTable() {
	functionTable["sin"] = &sin;
	functionTable["cos"] = &cos;
	functionTable["neg"] = &neg;
}

void buildVariableTable(vector<Token> & tokens) {
	for (size_t i = 0; i < tokens.size(); i++) {
		if (tokens[i].type == ttVariable) {
			variableTable[tokens[i].value] = 0;
		}
	}
}

int getOperatorPriority(string op) {
	if (op == "+" || op == "-") return 1;
	if (op == "*" || op == "/") return 2;
	return 1;
}

vector<Token> reversePolishNotation(vector<string> tokens, vector<TokenType> tokenTypes) {
	vector<Token> sequece(tokens.size());
	vector<Token> result;
	for (size_t i = 0; i < tokens.size(); i++) {
		sequece[i].value = tokens[i];
		sequece[i].type = tokenTypes[i];
	}

	stack<Token> st;
	for (size_t i = 0; i < sequece.size(); i++) {
		switch (sequece[i].type) {
			case ttVariable:
			case ttNumber: result.push_back(sequece[i]); break;
			case ttFunction:
			case ttBracketLeft: st.push(sequece[i]); break;
			case ttBracketRight: {
				while (!st.empty() && st.top().type != ttBracketLeft) {
					result.push_back(st.top());
					st.pop();
				}

				if (st.empty()) {
					makeError("Wrong bracket sequence.");
				}

				st.pop();

				if (!st.empty() && st.top().type == ttFunction) {
					result.push_back(st.top());
					st.pop();
				}

				break;
			}
			case ttOperator: {
				while (!st.empty() && st.top().type == ttOperator) {
					if (getOperatorPriority(st.top().value) >= getOperatorPriority(sequece[i].value)) {
						result.push_back(st.top());
						st.pop();
					}
					else break;
				}

				st.push(sequece[i]);
				break;
			}
		}
	}

	while (!st.empty()) {
		if (st.top().type != ttOperator) {
			makeError("Wrong bracket sequence.");
		}
		result.push_back(st.top());
		st.pop();
	}

	return result;
}

string stringFromDouble(double v) {
	stringstream ss(stringstream::in | stringstream::out);
	ss << v;
	return ss.str();
}

double doubleFromString(string v) {
	double r = 0;
	stringstream ss(stringstream::in | stringstream::out);
	ss << v;
	ss >> r;
	return r;
}

Token calculate(Token op, Token n1, Token n2) {
	double d1 = doubleFromString(n1.value);
	double d2 = doubleFromString(n2.value);

	Token r;
	r.type = ttNumber;

	if (op.value == "+") {
		r.value = stringFromDouble(d1+d2);
	}
	if (op.value == "-") {
		r.value = stringFromDouble(d1-d2);
	}
	if (op.value == "*") {
		r.value = stringFromDouble(d1*d2);
	}
	if (op.value == "/") {
		if (fabs(d2) < 0.00000000001) {
			makeError("Division by zero.");
		}
		r.value = stringFromDouble(d1/d2);
	}

	return r;
}

Token calculate(Token func, Token n) {
	 map<string, double(*)(double)>::iterator it = functionTable.find(func.value);

	 if (it == functionTable.end()) {
	 	makeError("Function " + func.value + "() doesn't exists.");
	 }

	 Token res;
	 res.type = ttNumber;
	 res.value = stringFromDouble(it->second(doubleFromString(n.value)));

	 return res;
}

vector<Token> optimizeEquation(std::vector<Token> eq) {
	int p = 1;

	while (p != -1) {
		Token t;
		p = -1;
		for (size_t i = 2; i < eq.size(); i++) {
			if (eq[i].type == ttOperator) {
				if (eq[i-1].type == ttNumber && eq[i-2].type == ttNumber) {
					t = calculate(eq[i], eq[i-2], eq[i-1]);

					eq.insert(eq.begin() + i + 1, t);
					for (int j = 0; j < 3; j++) {
						eq.erase(eq.begin() + i - 2);
					}

					p = i;
					break;
				}
			}
		}
	}

	return eq;
}

double getResult(std::vector<Token> eq) {
	for (size_t i = 0; i < eq.size(); i++) {
		if (eq[i].type == ttVariable) {
			eq[i].type = ttNumber;
			eq[i].value = stringFromDouble(variableTable[eq[i].value]);
		}
	}

	bool p = true;

	while (p) {
		Token t;
		p = false;
		for (size_t i = 1; i < eq.size(); i++) {
			if (i >= 2 && eq[i].type == ttOperator) {
				if (eq[i-1].type == ttNumber && eq[i-2].type == ttNumber) {
					t = calculate(eq[i], eq[i-2], eq[i-1]);
					eq.insert(eq.begin() + i + 1, t);
					for (int j = 0; j < 3; j++) {
						eq.erase(eq.begin() + i - 2);
					}

					p = true;

					break;
				}
			}
			if (eq[i].type == ttFunction) {
				if (eq[i-1].type == ttNumber) {
					t = calculate(eq[i], eq[i-1]);

					eq.insert(eq.begin() + i + 1, t);
					for (int j = 0; j < 2; j++) {
						eq.erase(eq.begin() + i - 1);
					}

					p = true;
					break;
				}
			}
		}
	}

	return doubleFromString(eq[0].value);
}

string buildEquationString(std::vector<Token> eq) {
	string result;
	stack<string> st;

	for (int i = 0; i < eq.size(); i++) {
		if (eq[i].type == ttOperator) {
			string s1 = st.top(); st.pop();
			string s2 = st.top(); st.pop();

			st.push("(" + s2 + eq[i].value + s1 + ")");
		}
		else if (eq[i].type == ttFunction) {
			string s = st.top(); st.pop();
			st.push(eq[i].value + "(" + s + ")");
		}
		else {
			st.push(eq[i].value);
		}
	}

	return st.top();
}
     
int main(int, char**) {
	initializeFunctionTable();

	vector<string> tokens = tokenListFromString(strFromConsoleInput());
	vector<TokenType> tokenTypes = tokenTypeListFromTokens(tokens);

	// for (size_t i = 0; i < tokens.size(); i++) {
	// 	cout << tokens[i] << " - ";

	// 	string type = "";

	// 	switch (tokenTypes[i]) {
	// 		case ttBracketLeft: type = "Bracket left"; break;
	// 		case ttBracketRight: type = "Bracket right"; break;
	// 		case ttOperator: type = "Operator"; break;
	// 		case ttNumber: type = "Number"; break;
	// 		case ttVariable: type = "Variable"; break;
	// 		case ttFunction: type = "Function"; break;
	// 	}

	// 	cout << type << endl;
	// }

	if (!checkSyntax(tokenTypes)) {
		cout << "Wrong equation syntax." << endl;
		exit(1);
	}

	std::vector<Token> rpn = reversePolishNotation(tokens, tokenTypes);

	// for (size_t i = 0; i < rpn.size(); i++) {
	// 	cout << rpn[i].value << " ";
	// }
	// cout << endl;

	std::vector<Token> opt = optimizeEquation(rpn);

	// for (size_t i = 0; i < opt.size(); i++) {
	// 	cout << opt[i].value << " ";
	// }
	// cout << endl; 

	cout << "Optimized equation: " << buildEquationString(opt) << endl;

	buildVariableTable(opt);

	for (map<string, double>::iterator it = variableTable.begin(); it != variableTable.end(); it++) {
		cout << "Input value for \"" << it->first << "\": ";
		double v = 0;
		cin >> v;
		variableTable[it->first] = v;
	}

	cout << "Result: " << getResult(opt) << endl;

	return 0;
}