Calculator using shunting-yard algorithm

This is very nice! It's a neat little piece of designed code to solve a somewhat simple problem but in a fairly generic way. That's cool, it's the kind of code I like to see.

As usual, I could point out a few things to improve. At least, there is one thing that could be a nice improvement to this design and other similar designs (as this is a somewhat recurring design pattern).

That one thing in particular is that dependency between the TokenBase and the Calculator. I don't see how that is necessary, in fact, I think the code would be better without it (and also, because I kind of despise the OOP Visitor Pattern, it's horrible to maintain and it doesn't scale, I consider it a last resort if all else fails). Let's say you defined your TokenBase class as follows:

struct TokenBase { 
    virtual void evaluate (std::stack<double>&) = 0;   // note std::stack here. 
    virtual ~TokenBase() {}
};

This way, you could have token classes that actually do the evaluation by picking elements from the stack, without having to go through the "consume" function, as so:

class BinaryOperator : public TokenBase {
    std::function<double(double,double)> func_;
public:
    void evaluate (std::stack<double>& operands);
    BinaryOperator(std::function<double(double,double)> aFunc) : func_(aFunc) {}
};

void BinaryOperator::evaluate(std::stack<double>& operands) {
  double right = operands.top(); operands.pop();
  double left  = operands.top(); operands.pop();
  operands.push( func_(left, right) );
};

class LiteralValue : public TokenBase {
    double value_;
public:
    void evaluate (std::stack<double>& operands) { operands.push(value_); };
    LiteralValue(double aValue) : value_(aValue) { };
};

And so on for other operator arities. Then, you use a factory function to create them:

TokenBase* make_new_token(double aValue) {
  return new LiteralValue(aValue);
};

TokenBase* make_new_token(char op) {
  switch (op) {
    case '+':
        return new BinaryOperator(std::plus<double>());
    case '*':
        return new BinaryOperator(std::multiplies<double>());
    case '-':
        return new BinaryOperator(std::minus<double>());
    case '/':
        return new BinaryOperator(std::divides<double>());
    default:
        throw std::domain_error("Unknown Operator");
  };
};

A further improvement on that, to get rid of this ugly switch-case in the factory function is to use a singleton object that stores a std::map of archetypical tokens for each operator character. Then, each new operator class that you create can just register its archetype to this repository. Something like this (this is just a global variable, not a singleton, for simplicity):

std::map<char, TokenBase*> supportedOpTokens;

TokenBase* make_new_token(char op) {
  std::map<char, TokenBase*>::const_iterator it = supportedOpTokens.find(op);
  if(it != supportedOpTokens.end())
    return it->second->clone();  // say you add a "clone" function to TokenBase.
  throw std::domain_error("Unknown Operator");
};

int main() {
  supportedOpTokens['+'] = new BinaryOperator(std::plus<double>());
  supportedOpTokens['-'] = new BinaryOperator(std::minus<double>());
  supportedOpTokens['*'] = new BinaryOperator(std::multiplies<double>());
  supportedOpTokens['/'] = new BinaryOperator(std::divides<double>());
  supportedOpTokens['%'] = new BinaryOperator(std::modulus<double>());

  Calculator c;
  std::cout << c.calculate ("(20+10)*3/2-3") << std::endl;

  for(std::map<char, TokenBase*>::iterator it = supportedOpTokens.begin();
      it != supportedOpTokens.end(); ++it)
    delete it->second;
  return 0;
};

Of course, in reality the map would be wrapped in a singleton that would take care of the deletion (and would allow static initialization too). Imagine you had a bigger parser system with tons of operators of different kinds and arity, and you wanted the set of supported operators to be extendable and reconfigurable, it is much nicer to be able to register (and unregister) supported operators from anywhere, and not have to re-code the visiting function every time.

In any case, the code you posted will make a great contender for the code-snippet contest!

Nice snippet.

Mike makes some really good points about the semantics of the language you have used to program this in.

I'm going to make a few suggestions about the practical use of this... Bear in mind I haven't tested your code completely at all so other issues may exist.

Your code falls flat on it's face when unary operators are considered.

Take for example:
-1+2

One such solution might be:
http://stackoverflow.com/questions/2431863/infix-to-postfix-and-unary-binary-operators

See my snippet:

http://www.daniweb.com/software-development/cpp/code/216831/expression-evaluator

Not quite as aesthetically pretty as yours, by any stretch of the imagination but slightly more complete nonetheless.

@mike_2000_17:
Thank you for taking the time to provide the feedback you did! I agree with decoupling the Calculator and TokenBase and just didn't consider it as I was writing the code.
As for the reduction of the switch to a more maintainable construct - I really like the approach you suggested. I toyed with a way to make that better but gave up as each solution was more complex than what is there. I wanted to keep it pretty simple - also, I'm still pretty much a C++ n00b.

@iamthwee:
Yes. I focused more on the basic algorithm and less on a fully compliant solution. I also neglected to address exponentiation, modulus and a number of other features one would expect from a real calculator.
Supporting the 'transparantly adding a zero' could easily be added as a pass over the input. I see this as an easy way to add any number of verification steps: balanced paranthesis, unary operators, valid constructs, etc.

I think better approach would be to just 'transparentely add +'. I mean that you do not have substraction routine but enter adding with negation flag set for number scanner. Then you just toggle the negation flag for minus ignoring plusses. That could be handled by suffiently competent number parser.

Not quite as aesthetically pretty as yours, by any stretch of the imagination but slightly more complete nonetheless.

Looks like that other snippet is not also complete:

4+--4--4--6
Expression invalid retard!

Sorry, other language but I posted the code in Python to clarify what I meant: http://www.daniweb.com/software-development/python/code/427548/simple-expression-cleanup

Nice article!

For coding up the Shunting Yard algorithm I personally found the following Wiki pages very useful:

http://en.wikipedia.org/wiki/Shunting-yard_algorithm
http://en.wikipedia.org/wiki/Reverse_Polish_notation

So long as you're OK with using stacks and queues, then I found it reasonably straightforward
to implement the algorithms as described in those Wiki pages.

I made a few modifications of my own, especially with regard to the tokenization of the RPN, ensuring it can distinguish minus signs from unary operators, so that it can handle calculations like -8+3, or 11 ^ -3, for example. That plus other sanity checks like ensuring there are no mismatched parentheses etc, and adding additional methematical operators like sin, cos, log etc...

However, I still need to clean up my own attempt a little and adopt the object oriented approach as you have ably done.

Explanation and code downloadable from here:

http://www.technical-recipes.com/2011/a-mathematical-expression-parser-in-java/