I remade an equation-solver program from Java to C++, and I plan to post it soon but I would rather not until I can determine where modulus fits in with PEMDAS.
To those who don't know, PEMDAS is the order in which mathematical expressions are to be evaluated. The order is
-Paranthesis'
-Exponents
-Mulitplication and Division (same level)
-Addition and Substraction (same level)
so if I have an expression 2 + 3 * 5, according to PEMDAS, 3 * 5 must resolve first so the expression becomes 2 + 15, and the answer afterwards is 17.
Now my problem is that I don't know where Modulus fits in with PEMDAS.
Does it have higher or lower precedence than Multiplication/Division?
8 * 9 % 5 --- what should happen first? 8 * 9 or 9 % 5?
It matters because 8 * 9 first yields 72, and 72 % 5 yields 2 (because 5 subtracts into 72 fourteen times, but cannot subtract into 2 wholly, so 2 is the remainder).
If 9%5 occurs first, 4 is the result for that minor expression and 8 * 4 is 32 so the operator precedence does indeed matter.
I've done some looking up on Google and couldn't find an article to resolve this issue.
Here's my program as it is now--
/**
* Numerics.cpp
*/
#ifndef NUMERICS
#define NUMERICS
#include <sstream>
#include <string>
using std::stringstream;
using std::string;
/**
* Convenience class for enabling easy
* conversions between strings and primitive types.
*
* This class is not meant to support non-primitive types,
* but it should if target class Type has istream and ostream
* operators overloaded.
*/
namespace Numerics{
template<class T>
class Numerical{
private:
T number;
public:
Numerical(T value = 0) : number(value){}
Numerical(const string& arg){
(*this)(arg);
}
/**
* Attempts to assign the argument value to the value
* of this Object's type.
* If the value is invalid, nothing happens.
*/
string operator()(const string& arg){
stringstream ss (stringstream::in | stringstream::out);
try{
ss << arg;
ss >> number;
}catch(...){
// currently unsupported
}
return ss.str();
}
/**
* Attempts to assign the argument value to the value of
* this Object's type.
*/
T operator()(T value){
return (number = value);
}
/**
* Returns a string representation of this Object's number
*/
string getString(){
stringstream ss (stringstream::in | stringstream::out);
ss << number;
return ss.str();
}
/**
* Returns a copy of this Object's number
*/
T getValue(){
return number;
}
/**
* Extraction operator used to return the underlying value
* during operations assosciated with primitive types.
*/
operator T& (){
return number;
}
/**
* const version of the above operator. Returns a copy
* of this Object's number.
*/
operator T () const{
return number;
}
};
/* Some meaningful typedefs for Numerical types */
typedef Numerical<short> Short;
typedef Numerical<unsigned short> U_Short;
typedef Numerical<int> Integer;
typedef Numerical<unsigned int> U_Integer;
typedef Numerical<double> Double;
typedef Numerical<float> Float;
typedef Numerical<char> Byte;
typedef Numerical<unsigned char> U_Byte;
typedef Numerical<wchar_t> Wide_Byte;
typedef Numerical<long int> Long;
typedef Numerical<unsigned long int> U_Long;
/* For non-standard types, like __int8, __int16, __int32, and __int64 */
#ifdef ALLOW_NONSTANDARD_PRIMITIVE_TYPES
#if (ALLOW_NONSTANDARD_PRIMITIVE_TYPES == 0x01)
typedef Numerical < __int8 > __Int8;
typedef Numerical < unsigned __int8 > U___Int8;
typedef Numerical < __int16 > __Int16;
typedef Numerical < unsigned __int16 > U___Int16;
typedef Numerical < __int32 > __Int32;
typedef Numerical < unsigned __int32 > U___Int32;
typedef Numerical < __int64 > __Int64;
typedef Numerical < unsigned __int64 > U___Int64;
#endif
#endif
}
#endif/**
* EquationSolver.h
*/
#ifndef EQUATION_SOLVER_H
#define EQUATION_SOLVER_H
#include <string>
#include <vector>
using std::string;
using std::vector;
namespace EquationHelper{
class EquationSolver{
private:
EquationSolver();
static string doOperation(const string&, char, const string&);
static void correctedString(string&);
static void removeSpaces(string&);
static string parse(const string&);
static bool isSolvable(const string&);
static void calculate(vector<string>&, vector<char>&, const string&);
public:
static string solve(const string&, int = 50);
};
}
#include "EquationSolver.cpp"
#endif/**
* EquationSolver.cpp
*/
#ifdef EQUATION_SOLVER_H
#include <iostream>
#include <cmath>
#include <vector>
#include "Numerics.cpp"
using namespace EquationHelper;
using namespace Numerics;
using std::size_t;
using std::vector;
using std::string;
using std::cout;
using std::endl;
using std::ios;
typedef EquationSolver ES;
/**
* Private constructor - does nothing.
*/
ES::EquationSolver(){}
/**
* Performs the specified operation against the
* argument strings. The operation is dependant on
* the value of op.
*/
string ES::doOperation(const string& lhs, char op, const string& rhs){
Double bdLhs = lhs;
Double bdRhs = rhs;
Double temp;
switch(op){
case '^':
temp( pow( bdLhs, bdRhs ) );
break;
case '*':
temp( bdLhs * bdRhs );
break;
case '/':
temp( bdLhs / bdRhs );
break;
case '+':
temp( bdLhs + bdRhs );
break;
case '%':
temp( fmod(bdLhs, bdRhs) );
break;
}
return temp.getString();
}
/**
* Returns the string with its enclosing paranthesis
* stripped from it.
*/
void ES::correctedString(string& arg){
size_t pos1 = arg.find_first_of("(");
size_t pos2 = arg.find_last_of(")");
if(pos1 >= 0 && pos1 < arg.length() && pos2 >= 0 && pos2 <= arg.length())
arg[pos1] = arg[pos2] = ' ';
}
/**
* Remove spaces from the argument string.
*/
void ES::removeSpaces(string& argu){
string temp = "";
for(size_t i = 0; i < argu.length(); i++)
if(argu[i] != ' ')
temp += argu[i]; // only add non-space characters to temp
argu = temp;
}
/**
* The brains of the program.
* Solves expressions by using recursion for complex expressions.
*/
string ES::parse(const string& param){
string expression = param;
correctedString(expression);
removeSpaces(expression); // Removes paranthesis and spaces from the String expression
string finalExpression = ""; // Placeholder for the final String before values and operands are parsed
bool operatorEncountered = true; // Used to determine if the previous value encountered is an operand
for(size_t i = 0; i < expression.length(); i++){ // for all of the characters in the String expression
if(expression[i] == '('){ // if we encounter a left paranthesis, the value must be a nested expression
string placeHolder = "("; // to prevent problems determining during boolean expression-checks
int valuesCounted = 1; // i.e., when should we stop? When valuesCounted is 0?
operatorEncountered = false; // because this will evaluate to be a number, we don't want to consider
// this char-expression to be an operand
for(size_t j = i + 1; valuesCounted != 0; j++){ // We know that i has to be "(" and we've accounted for it, so i+1 is what we'll use
if(expression[j] == '(') // if we encounted a left paranthesis, increment count
valuesCounted++;
else if(expression[j] == ')') // else if its a left paranthesis, decrement count
valuesCounted--;
placeHolder += expression[j]; // append the character to the expression
}
string evaluatedString = parse(placeHolder); // recursive call - evaluate the nested expression
finalExpression += evaluatedString; // append the evaluatedString to the finalExpression String
i += (placeHolder.length() - 1); // the nested expression is already solved - force i to jump to non-redundant characters
}else{
if(expression[i] == '-' && operatorEncountered == false) // if we encountered a minus sign and we didn't encounter any operands
// before it, changes the subtraction to plus a negative
finalExpression += '+';
finalExpression += expression[i]; // append the character to the expression
if((expression[i] == '+'
|| expression[i] == '/'
|| expression[i] == '^'
|| expression[i] == '*'
|| expression[i] == '%'
|| expression[i] == '-')) // if we encounter a valid operand (including minus), flag operandEncountereed to be true
operatorEncountered = true;
else if(expression[i] != ' ') // else if we dont encounter whitespace nor an operand, flag operand to be false
operatorEncountered = false;
}
}
removeSpaces(finalExpression); // for safety measures, removing whitespace again
string perfectExpression = ""; // I'm planning on storing a better version of the finalExpression here
for(size_t i = 0; i < finalExpression.length(); i++){ // for every character in the String finalExpression
if((i + 1) < finalExpression.length()) // to prevent overshooting the array, this measure is taken
if(finalExpression[i] == '-' && finalExpression[i + 1] == '-') // if there are two - chars next to each other
i += 2; // ignore them.
perfectExpression += finalExpression[i]; // append to the perfectExpression
}
finalExpression = perfectExpression; // make finalExpression point to the same address as perfectExpression
vector<string> totalNumbers; // I'm planning to use this to store Number values (as Strings)
vector<char> totalOperations; // I'm planning to use this to store Operand values (as Characters)
cout << finalExpression << endl; // Technically a debug, but it adds a nice touch to the program.
for(size_t i = 0; i < finalExpression.length(); i++){ // for every character in the finalExpression
if(finalExpression[i] >= '0' && finalExpression[i] <= '9'
|| finalExpression[i] == '-' || finalExpression[i] == '.'){ // if our character is part of a number
string temp = ""; //
for(size_t j = i; j < finalExpression.length(); j++){ // We're technically breaking good programming practice here--
// I don't intend on traversing the entire String. We're breaking
// out of this loop the moment a non-numeric character is encountered
if(finalExpression[j] >= '0' && finalExpression[j] <= '9'
|| finalExpression[j] == '-' || finalExpression[j] == '.'){
temp += finalExpression[j]; // append to the temporary String
}else break;
}
totalNumbers.push_back(temp); // add our collected number to the ArrayList
i += temp.length() == 0 ? 0 : (temp.length() - 1); // we don't want to have redundancy, i.e.
// if number 242 is analyzed, 242, 42 and 2 shouldn't be stored, just 242
// so advance i past numbers already analyzed
}else if(finalExpression[i] == '*'
|| finalExpression[i] == '/'
|| finalExpression[i] == '^'
|| finalExpression[i] == '+'
|| finalExpression[i] == '%'
){ // If we run into an operand-character, store it in the operand list
totalOperations.push_back(finalExpression[i]);
}
}
ES::calculate(totalNumbers, totalOperations, "^");
ES::calculate(totalNumbers, totalOperations, "*/%");
ES::calculate(totalNumbers, totalOperations, "+");
return totalNumbers[0]; // return the value remaining in the first position of the ArrayList
}
/**
* Calculates the numbers in the first vector using the operands in the 2nd vector,
* based on the expressions allowed which are determined by the string argument.
*/
void ES::calculate(vector<string>& totalNumbers, vector<char>& totalOperations,
const string& arg){
for(int i = 0; i < static_cast<int>(totalOperations.size()); i++){
if( arg.find(totalOperations[i]) != arg.npos){
totalNumbers[i] = doOperation(totalNumbers[i], totalOperations[i], totalNumbers[i + 1]);
size_t oldNumberLength = totalNumbers.size();
size_t oldOperatorLength = totalOperations.size();
size_t nextNumberLength = oldNumberLength - 1;
size_t nextOperatorLength = oldOperatorLength - 1;
size_t sCount = 0;
size_t oCount = 0;
vector<string> temp1 ( nextNumberLength );
vector<char> temp2 ( nextOperatorLength );
for(size_t j = 0; j < oldNumberLength; j++){
if(j != static_cast<int>(i + 1)){
temp1[sCount++] = totalNumbers[j];
}
if(j != i && j < oldOperatorLength){
temp2[oCount++] = totalOperations[j];
}
}
totalNumbers = temp1;
totalOperations = temp2;
i--;
}
}
}
/**
* Returns true if the equation is solvable (not really),
* returns false otherwise.
*
* This function is truly a misnomer, because more restrictions
* should be put in place.
*/
bool ES::isSolvable(const string& eq){
int paranthesisCount = 0; // assuming 0 paranthesis to begin with
for(size_t i = 0; i < eq.length(); i++){ // for every char in the String eq
if(eq[i] == '(') // if the element is a left paranthesis
paranthesisCount++; // increment the paranthesisCount
else if(eq[i] == ')') // else if the element is a right paranthesis
paranthesisCount--; // decrement the paranthesisCount
if(paranthesisCount < 0) // if brackets aren't in correct order, return false
return false;
}
return paranthesisCount == 0; // return true if paranthesisCount is zero, otherwise return false
}
/**
* An attempt to solve a string-expression, given
* a precision value.
*/
string ES::solve(const string& eq, int prec){
if(isSolvable(eq)){
stringstream ss (stringstream::in | stringstream::out);
cout << eq << endl; // Prints out the equation before it is parsed
string value;
value += '(';
value += eq;
value += ')';
ss.setf(0, ios::floatfield);
ss.precision(prec);
ss << parse(value);
return ss.str(); // returning the final value of the expression
}else return "";
}
#endif/**
* DriverProgram.cpp
*/
/****************************************
* @Author: Mark Alexander Edwards Jr.
*
* This program uses a utility class to solve
* complex equations represented by string
* expressions
****************************************/
#include <iostream>
#include <ctime>
#include <string>
#include "Numerics.cpp"
#include "EquationSolver.h"
using std::cin;
using std::cout;
using std::endl;
using std::flush;
using std::string;
using namespace Numerics;
using namespace EquationHelper;
int main(){
cout << ES::solve("5 + 3 * (8 - 4)") << endl << endl;
cout << ES::solve("12 / (3 * 4) + 5") << endl << endl;
while(true){
cout << "Enter an equation you would \nlike to solve (enter 'exit' to quit): " << flush;
try{
string temp;
getline(cin, temp);
clock_t t1 = clock();
if(temp.compare("exit") == 0) exit(0);
cout << "Answer: " + ES::solve(temp, 4) << endl;
clock_t t2 = clock();
cout << "\nTime taken to calculate value: " <<
(t2-t1) << " Clock cycles" <<endl;
}catch(...){
cout << "Invalid expression! Please try again!" << endl;
}
}
cin.ignore();
cin.get();
return 0;
}