#include <iostream>
#include <string>
std::string evaluate_equation(std::string);
bool valid_equation(const std::string&);
int str2Int(const std::string&);
std::string int2Str(unsigned int);
bool isdigit(char);
std::string addStrs(const std::string&, const std::string&);
std::string multStrs(const std::string&, const std::string&);
int main (int argc, char* const argv[]) {
// Evaluate expressions at the console
std::string eqtn;
while (std::cin >> eqtn) {
if (!valid_equation(eqtn)) {
std::cout << "Equation invalid; not evaluated" << std::endl;
} else {
std::cout << evaluate_equation(eqtn) << std::endl;
}
}
return 0;
}
std::string evaluate_equation(std::string eq) {
/* By the order of operations:
(1) Evaluate the expression in the innermost set of paranthesis, if there is one;
(2) Evaluate multiplication expressions left-to-right;
(3) Evaluate addition expressions left-to-right.
Use recursion.
*/
// (1):
size_t LRFP = eq.find_last_of('('); // position of last right-facing paranthesis
if (LRFP != std::string::npos) {
// Set NLFP to be the position of the next left-facing paranthesis after the FRFPL
size_t NLFP = LRFP;
while (eq[++NLFP] != ')');
/* Replace the space between FRFP and NLFP inclusive with the evalulation of the expression
between FRFP and NLFP exclusive:
*/
std::string paranstr = eq.substr(LRFP + 1, NLFP - LRFP - 1);
eq.replace(LRFP, NLFP - LRFP + 1, evaluate_equation(paranstr));
return evaluate_equation(eq);
}
// (2):
size_t firstast = eq.find_first_of('*'); // position of first asterisk
if (firstast != std::string::npos) {
// Set num1 and num2 equal to the respective numbers to the left and right of the asterisk:
std::string num1, num2;
size_t num1begin(firstast), num2end(firstast);
while (num1begin > 0 && isdigit(eq[num1begin - 1]))
num1.insert(0, 1, eq[--num1begin]);
int eqsz = eq.size();
while ((num2end + 1) < eqsz && isdigit(eq[num2end + 1]))
num2.push_back(eq[++num2end]);
// Replace the space of the multiplication equation num1*num2 with its evaluation:
eq.replace(num1begin, num2end - num1begin + 1, multStrs(num1, num2));
return evaluate_equation(eq);
}
// (3):
size_t firstplus = eq.find_first_of('+');
if (firstplus != std::string::npos) {
// Set num1 and num2 equal to the respective numbers to the left and right of the asterisk:
std::string num1, num2;
size_t num1begin(firstplus), num2end(firstplus);
while (num1begin > 0 && isdigit(eq[num1begin - 1]))
num1.insert(0, 1, eq[--num1begin]);
int eqsz = eq.size();
while ((num2end + 1) < eqsz && isdigit(eq[num2end + 1]))
num2.push_back(eq[++num2end]);
// Replace the space of the multiplication equation num1*num2 with its evaluation:
eq.replace(num1begin, num2end - num1begin + 1, addStrs(num1, num2));
return evaluate_equation(eq);
}
// If we made it to this point, all that's left of the equation is a single number. Return it;
return eq;
}
bool valid_equation(const std::string& eq) {
std::string::const_iterator it = eq.begin();
// Equation cannot be an empty string:
if (it == eq.end())
return false;
// Count for the number of right-facing and left-facing parantheses:
int RFPcnt(0), LFPcnt(0);
/* Iterate through the characters of the equation to check that it is valid based on
which characters are lined up next to which. For example, if two plus signs are found
next to each other, that makes the equation meaningless and the our function
valid_equation() immediately returns false.
*/
while (it != eq.end()) {
if (*it == '(') {
/*
Rules for a right-facing paranthesis:
(1) Must be followed by a digit or another right-facing paranthesis
(2) Must be preceded by an operator or another right-facing paranthesis or nothing at all
*/
if ((it + 1) == eq.end()) {
return false;
} else {
if (!isdigit(*(it + 1)) && *(it + 1) != '(')
return false;
}
if (it != eq.begin()) {
if (*(it - 1) != '*' && *(it - 1) != '+' && *(it - 1) != '(')
return false;
}
++it; // If we made it here, increment the iterator
++RFPcnt; // Increment the count of right-facing paranthesis as well
} else if (*it == ')') {
/*
Rules for a left-facing paranthesis:
(1) Cannot be the beginning of an equation
(2) Must be preceded by a digit or another left-facing paranthesis
(3) Must be followed by an operator or another left-facing paranthesis or nothing at all
*/
if (it == eq.begin()) {
return false;
} else {
if (!isdigit(*(it - 1)) && *(it - 1) != ')')
return false;
}
if ((it + 1) != eq.end()) {
if (*(it + 1) != '*' && *(it + 1) != '+' && *(it + 1) != ')')
return false;
}
++it; // If we made it here, increment the iterator
++LFPcnt; // Increment the count of left-facing paranthesis as well
} else if (*it == '*' || *it == '+') {
/*
Rules for an operator:
(1) Cannot be the beginning or end of an equation
(2) Must be preceded by a digit or a left-facing paranthesis
(3) Must be followed by a digit or a right-facing paranthesis
*/
if (it == eq.begin() || (it + 1) == eq.end()) {
return false;
} else {
if (!isdigit(*(it - 1)) && *(it - 1) != ')')
return false;
if (!isdigit(*(it + 1)) && *(it + 1) != '(')
return false;
}
++it;
} else if (isdigit(*it)) {
// Simply increment the iterator until it's no longer on a digit:
while (isdigit(*++it));
} else { // If we're here, *it is invalid character
return false;
}
}
if (RFPcnt != LFPcnt) // Unbalanced paranthesis?
return false;
return true; // If we made it here, the equation is valid; return true
}
// Given a decimal representation as a string s, str2Int(s) returns the corresponding decimal as an int
int str2Int(const std::string& str) {
std::string::const_iterator it = str.begin();
if (it == str.end()) {
std::cout << "Invalid parameter: str2Int() only accepts non-empty strings." << std::endl;
return -1;
}
int sum = 0;
while (it != str.end()) {
if (!isdigit(*it)) {
std::cout << "Invalid paramter: str2Int only accepts strings of chars '0' through '9'" << std::endl;
return -1;
} else {
sum *= 10;
sum += *it++ - '0';
}
}
return sum;
}
// Given an int n, int2Str(n) return the string representation
std::string int2Str(unsigned int n) {
std::string retstring;
if (n == 0) {
retstring.push_back('0');
return retstring;
} else {
while (n != 0) {
retstring.insert(0, 1, char('0' + n % 10));
n /= 10;
}
return retstring;
}
}
// Function that checks whether a given character is in one of '0', '1', ..., '9'
bool isdigit(char c) {
return (c >= '0' && c <= '9');
}
// Adds 2 string decimal representations and returns the sum as a string decimal representation
std::string addStrs(const std::string& s1, const std::string& s2) {
return (int2Str(str2Int(s1) + str2Int(s2)));
}
// Multiplies 2 string decimal representations and returns the sum as a string decimal representation
std::string multStrs(const std::string& s1, const std::string& s2) {
return (int2Str(str2Int(s1) * str2Int(s2)));
}
