Vectors and Evaluating Infix Expression C++?

2009-06-03 04:36:23 UTC

I think you're essentially going to need a parser. Because you're going to have to make decisions like which operators bind more tightly than the others.

I may be missing a simple and elegant solution though.

cja

2009-06-03 13:18:53 UTC

Limiting expressions to just binary arithmetical operations and not allowing parentheses helps keep this simple. By using two vectors, as you're talking about above, I think you're making it more difficult, complicating expression validation and evaluation.

My idea is to put operands and operators together in a single vector. This way you can evaluate "x op y", store the result in the vector where the operator was, remove the operands, evaulate the next "x op y", and so on until the vector contains only the final result. (Keeping operator precedence in mind, of course.) This evaluation assumes a properly formed expression; input validation is required so you won't attempt to evaulate a malformed expression.

So, see below for how I would do it. I hope it gives you some ideas of how to get your program working.

#include

#include

#include

#include

using namespace std;

enum ElementType { Value, Operator };

enum Precedence { Add, Sub, Mul, Div, Rem };

typedef map PrecedenceMap;

typedef double (*func)(double,double);

double add(double,double);

double sub(double,double);

double mul(double,double);

double div(double,double);

double rem(double,double);

const size_t NUM_OPS = 5;

typedef struct {

char op;

func f;

} BinaryOp_t;

BinaryOp_t ops[NUM_OPS] = {

{ '/', div }, { '*', mul }, { '%', rem },

{ '-', sub }, { '+', add }

};

struct ExpressionElement {

ElementType typ;

union ElementVal {

double val;

char op;

} e;

ExpressionElement(ElementType t, double v) {

typ = t; e.val = v;

}

ExpressionElement(ElementType t, char op) {

typ = t; e.op = op;

}

};

struct Expression {

Expression(const string &s) {

stringstream ss(s);

ExpressionElement *e;

double val;

char op;

init();

while (ss.good() && (isValid)) {

if (ss >> val) {

e = new ExpressionElement( Value,val );

exp.push_back(e);

if (ss.good() && (ss >> op)) {

if (pMap.find(op) != pMap.end()) {

e = new ExpressionElement( Operator,op );

exp.push_back(e);

// would be good to add some validation

// for non-integral operands for %

} else {

isValid = false;

}

}

} else {

isValid = false;

}

}

}

void init() {

// may find a use for this map for precedence

// at some point; for now, it's handy for

// validating operators

pMap.insert(pair( '+',Add) );

pMap.insert(pair( '-',Sub) );

pMap.insert(pair( '*',Mul) );

pMap.insert(pair( '/',Div) );

pMap.insert(pair( '%',Rem) );

isValid = true;

}

vector::iterator findOp(char op) {

vector::iterator i = exp.begin();

bool found = false;

while ((i != exp.end()) && (found == false)) {

found = (((*i)->typ == Operator) &&

((*i)->e.op == op));

if (!found) ++i;

}

return i;

}

double eval() {

double result = 0;

if (isValid == true) {

result = exp[0]->e.val;

vector::iterator i;

for (size_t j = 0; j < NUM_OPS; j++) {

while ((i = findOp(ops[j].op)) != exp.end()) {

(*i)->typ = Value;

(*i)->e.val =

ops[j].f( ( *(i-1) )->e.val,( *(i+1) )->e.val );

exp.erase(i+1);

exp.erase(i-1);

result = (*i)->e.val;

// print();

}

}

}

return result;

}

void print() {

if (isValid == true) {

vector::iterator i = exp.begin();

while (i != exp.end()) {

if ((*i)->typ == Value) {

cout << (*i)->e.val;

} else {

cout << (*i)->e.op;

}

cout << " ";

++i;

}

} else {

cout << " (invalid expression) " << endl;

}

cout << endl;

}

vector exp;

PrecedenceMap pMap;

bool isValid;

};

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

string line;

while (true) {

cout << "> ";

getline(cin,line);

if (line.size() > 0) {

Expression exp(line);

if (exp.isValid == true) {

cout << exp.eval() << endl;

} else {

cout << " (invalid) " << endl;

}

}

}

return 0;

}

double add(double x, double y) { return x + y; }

double sub(double x, double y) { return x - y; }

double mul(double x, double y) { return x * y; }

double div(double x, double y) { return x / y; }

double rem(double x, double y) {

int i = static_cast(x),

j = static_cast(y);

return static_cast(i % j);

}

#if 0

Sample run:

> 5 + 3 * 2 - 8 / 2

7

> 2.2 + 3.3

5.5

> 8 + 2 +

(invalid)

> * +

(invalid)

>

> 4 + 5

9

> 5/2

2.5

> 5 % 2

1

> 9 + 2 * 3 % 5 - 7

3

#endif

HandyManOrNot

2009-06-02 21:58:42 UTC

The key is your vector of ops.Since you are using only +-*/, you just start through the ops vector and first look for the * and / characters. Each time you find one, you use its vector index to access the surrounding two numbers in the int vector. Using ASCII character matching, determine which operation to perform, update one of the int vectors with the new value and eliminate the other, then eliminate the op vector. Once all the * and / ops are gone, do the same for the + and - ops.

This code is a little too complex to simply post, hopefully you have a working vector with update and remove functions, and know how to loop through the vectors and keep track of position.