CodeArchive ExpressionEvaluation
From Ubcacm
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