Sunday, April 15, 2012

Integer Expression Evaluator code

/*
* Expression evaluator. It supports +,-,*,/ and (), and integers.
* Example: 2*((5+4)/2)*6=48
* This code does not evaluate unary expression, such as -1
*
*/
#include <iostream>
#include <stack>
using namespace std;

enum OPR{ADD='+', SUB='-', MUL='*', DIV='/', PAR='('};

int eval(const string &exp);
int calc(int, int, OPR);
int rank(OPR r1);

int main(int argc, char *argv[])
{
string exp;

if(argc > 1)
exp = argv[1];
else
exp = "2*((5+4)/2)*6+(2)";
int result = eval(exp);
cout << exp << "=" << result << endl;
}

/*
* Evaluates a math expression
*/

int eval(const string & exp)
{

stack<int> Opd; //stack for operands
stack<OPR> Opr; //stack for operators
int opd1;
int opd2;
OPR opr1;
int result = 0;
int i = 0;
int Len = exp.length();
for(i = 0; i < Len; i++)
{
//end of a parentheses
if(exp[i] == ')')
{
while(Opr.top() != PAR) //If last pushed opeator is not (, then evaluate
{
opr1 = Opr.top();
Opr.pop();

opd1 = Opd.top();
Opd.pop();

opd2 = Opd.top();
Opd.pop();

Opd.push(calc(opd1,opd2,opr1));
}
Opr.pop(); // pop '('
}
else if(isdigit(exp[i])) //if a number, push to operand stack
{
Opd.push(exp[i] - '0');
}
else
{
//If current element is an operator, and operator stack is not empty
//compare their precedence.
if(!Opr.empty())
{
opr1 = Opr.top();
if(opr1 != '(' && rank(opr1) >= rank(static_cast<OPR>(exp[i])) )
{
opd1 = Opd.top();
Opd.pop();
opd2 = Opd.top();
Opd.pop();
result = calc(opd1,opd2, opr1);
Opr.pop();
Opd.push(result);
}
}
Opr.push(static_cast<OPR>(exp[i]));
}

}

//Evaluate the last binary expression remainig in the stack
while(!Opr.empty())
{
opr1 = Opr.top();
Opr.pop();
opd1 = Opd.top();
Opd.pop();
opd2 = Opd.top();
Opd.pop();
Opd.push(calc(opd1,opd2,opr1));
}

return Opd.top();
}

/*
* Evaluates an binary expression such as 1+2
*/
int calc(int opd1, int opd2, OPR opr1)
{
int c;
switch(opr1)
{
case ADD:
c = opd2 + opd1; break;
case SUB:
c = opd1 - opd2; break;
case MUL:
c = opd1 * opd2; break;
case DIV:
c = opd2 / opd1; break;
}
return c;
}
/*
* Operator Precedence
*/
int rank(OPR opr1)
{
int r = 0;
switch(opr1)
{
case ADD:
case SUB:
r = 1; break;
case MUL:
case DIV:
r = 2; break;
case PAR:
r = 3; break;
}

return r;
}

No comments: