CodeArchive ExpressionEvaluation

Yury's version: expression evaluation with brackets. No unary operators or spaces allowed. */ have priority over +-. Based on Reverse Polish Notation.

inline void update(vector < double > &vn, vector < char > &vo){
  if     (vo.back() == '/') vn[vn.size() - 2] /= vn.back();
  else if(vo.back() == '*') vn[vn.size() - 2] *= vn.back();
  else if(vo.back() == '-') vn[vn.size() - 2] -= vn.back();
  else if(vo.back() == '+') vn[vn.size() - 2] += vn.back();
  vn.pop_back(), vo.pop_back();
}

double evaluate(char *s){
  vector < double > vn; vector < char > vo;
  while(*s){
    if(isdigit(*s)) vn.push_back(strtod(s, &s));
    else{
      if(*s == '*' || *s == '/')
   while(vo.size() && (vo.back() == '*' || vo.back() == '/')) update(vn, vo);
      else if(*s == '+' || *s == '-')
   while(vo.size() && vo.back() != '(') update(vn, vo);
      else if(*s == ')') while(vo.back() != '(') update(vn, vo);
      if(*s == ')') vo.pop_back(), s++; 
      else vo.push_back(*s++);
    }
  }
  while(vo.size()) update(vn, vo);
  return vn.back();
}

Recursive Descend parsing (Matthew's version)

Right things in Left recursive order, and do this mechanically again

#include <iostream>
#include <string>

using namespace std;

double values[256];

double eval_expr(const char* strg, const char* &next);

double eval_number(const char* strg, const char* &next) {
  if (*strg == '(') {
    double result = eval_expr(strg+1, next);
    ++next; // This is the ')'
    return result;
  }
  /* This is just for 10932 */
  if (*strg >= 'a' && *strg <= 'z') {
    next = strg+1;
    return values[*strg];
  }
  /* End for special code */
  
  char* dummy;
  double result = strtod(strg, &dummy);
  next = dummy;
  return result;
}

double eval_factor(const char* strg, const char* &next) {
  double acc = eval_number(strg, next);
  while(*next) {
    if (*next == '*') acc *= eval_number(next+1, next);
    else if (*next == '/') acc /= eval_number(next+1, next);
    else return acc;
  } // No need to return anything
  return acc;
}

double eval_expr(const char* strg, const char* &next) {
  double acc = eval_factor(strg, next);
  while(*next) {
    if (*next == '+') acc += eval_factor(next+1, next);
    else if (*next == '-') acc -= eval_factor(next+1, next);
    else return acc;
  } // Don't return anything....
  return acc;
}

double eval(const string& strg, int idx = 0) {
  const char* dummy;
  return eval_expr(strg.c_str()+idx, dummy);
}

int main() {
  string input;
  cout.setf(ios::fixed, ios::floatfield);
  cout.precision(2);
  while(getline(cin, input)) {
    if (input.length() >= 2 && input[1] == '=')
      values[ input[0] ] = eval(input, 2);
    else
      cout << eval(input) << endl;
  }
  return 0;
}

-- Main.MatthewChan - 29 Mar 2006