Implementation Details

Implementation Details

The main steps of the calculation process are:

1. Create the operator precedence map.
2. Convert to RPN with Dijkstra's Shunting-yard algorithm.
3. Evaluate the expression in RPN form.

Converting to RPN.

Most of the Shunting-yard algorithm resides here. The idea is to do everything in one pass for elegance. Please see the source code for implementation-specific details, and refer to the pruned code below for a summary.

TokenQueue_t calculator::toRPN(const char* expr,
    std::map<std::string, double>* vars,
    std::map<std::string, int> opPrecedence) {
  TokenQueue_t rpnQueue; std::stack<std::string> operatorStack;

  while (*expr ) {
    if (isdigit(*expr )) {
      // If the token is a number, add it to the output queue.
    } else if (isvariablechar(*expr )) {
      // If the function is a variable, resolve it and
      // add the parsed number to the output queue.
    } else {
      // Otherwise, the variable is an operator or parenthesis.
      switch (*expr) {
        case '(':
          operatorStack.push("(");
          ++expr;
          break;
        case ')':
          while (operatorStack.top().compare("(")) {
            rpnQueue.push(new Token<std::string>(operatorStack.top()));
            operatorStack.pop();
          }
          operatorStack.pop();
          ++expr;
          break;
        default:
          {
            // The token is an operator.
            //
            // Let p(o) denote the precedence of an operator o.
            //
            // If the token is an operator, o1, then
            //   While there is an operator token, o2, at the top
            //       and p(o1) <= p(o2), then
            //     pop o2 off the stack onto the output queue.
            //   Push o1 on the stack.
          }
      }
    }
  }
  while (!operatorStack.empty()) {
    rpnQueue.push(new Token<std::string>(operatorStack.top()));
    operatorStack.pop();
  }
  return rpnQueue;
}

Evaluating RPN form.

The RPN is represented as tokens in a stack. To evaluate this, pop all of the elements off and handle operations when encountered.

std::stack<double> evaluation;
while (!rpn.empty()) {
  TokenBase* base = rpn.front();
  rpn.pop();

  if (base->type == OP) {
    Token<std::string>* strTok = static_cast<Token<std::string>*>(base);
    std::string str = strTok->val;
    if (evaluation.size() < 2) {
      throw std::domain_error("Invalid equation.");
    }
    double right = evaluation.top(); evaluation.pop();
    double left  = evaluation.top(); evaluation.pop();
    if (!str.compare("+")) {
      evaluation.push(left + right);
    } else if (!str.compare("*")) {
      evaluation.push(left * right);
    } else if (!str.compare("-")) {
      evaluation.push(left - right);
    } else if (!str.compare("/")) {
      evaluation.push(left / right);
    } else if (!str.compare("<<")) {
      evaluation.push((int) left << (int) right);
    } else if (!str.compare(">>")) {
      evaluation.push((int) left >> (int) right);
    } else {
      throw std::domain_error("Unknown operator: '" + str + "'.");
    }
  } else if (base->type == NUM) {
    Token<double>* doubleTok = static_cast<Token<double>*>(base);
    evaluation.push(doubleTok->val);
  } else {
    throw std::domain_error("Invalid token.");
  }
  delete base;
}

The evaluated value resides in evaluation.top of type double.