//////////////////////////////////////////////////////////////////////////////
// xcalc.h
// Author: Seree Rakwong
// Date: 19-NOV-10
// Purpose: Evaluate an expression
// Author: Seree Rakwong
// Date: 19-NOV-10
// Purpose: Evaluate an expression
#ifndef xcalc_h
#define xcalc_h
#include <string>
#include <stack>
#include <vector>
typedef enum xcalc_error_t_ {
error_none = 0,
imbalance_parenthesis = 1000,
incorrect_operand = 1001,
require_2_operands = 1002,
divided_by_zero = 1003,
unknown_operator = 1004,
unavailable_output = 1005,
incomplete_minus_operand = 1006
} xcalc_error_t;
// expression events
class xcalc_parser;
class xcalc_interface {
friend class xcalc_parser;
protected:
virtual void start_expression()=0;
virtual int end_expression()=0;
virtual int found_operator(char op)=0;
virtual int found_operand(char *op)=0;
virtual int found_left_parenthesis()=0;
virtual int found_right_parenthesis()=0;
virtual void found_error(xcalc_error_t err_no, char *param)=0;
};
// expression parser
class xcalc_parser {
private:
int is_operator(char ch);
int is_parenthesis(char ch);
int is_whitespaces(char ch);
int is_number(char ch);
protected:
int parse(char *expr, xcalc_interface *xcalc_ptr);
};
// integrate between expression events and parser
class xcalc : public xcalc_interface,
public xcalc_parser
{
class xcalc_operand {
public:
int type_;
std::string operand_;
};
class xcalc_operator {
public:
int precedence_;
char operator_;
};
std::stack<xcalc_operand> operand_stack_;
std::stack<xcalc_operator> operator_stack_;
#ifdef DEBUG
std::vector<std::string> polish_;
#endif
xcalc_error_t errno_;
std::string errtext_;
// to recognize the previous operand or operator
int prev_op; // 0 - is operand, 1 - is operator, 2 - is '(', 3 - is ')'
private:
int find_type(char *op);
int get_precedence(char op);
protected:
void start_expression();
int end_expression();
int found_operator(char op);
int found_operand(char *op);
int found_left_parenthesis();
int found_right_parenthesis();
void found_error(xcalc_error_t err_no, char *param);
int parse(char *expr);
int evaluate(char op);
public:
xcalc();
int execute(char *expr, int *type, char *out);
xcalc_error_t errno() { return errno_; }
const char *errtext() { return errtext_.c_str(); }
};
#endif // xcalc_h
//////////////////////////////////////////////////////////////////////////////
// xcalc.cpp
// Author: Seree Rakwong
// Date: 19-NOV-10
// Purpose: Evaluate an expression
#include <cmath>
#include <iostream>
using namespace std;
int xcalc_parser::is_operator(char ch) {
switch(ch) {
case '+':
case '-':
return 1;
case '*':
case '/':
case '%':
return 2;
case '^':
return 3;
}
return 0;
}
int xcalc_parser::is_parenthesis(char ch) {
if(ch == '(') return 1;
if(ch == ')') return 2;
return 0;
}
int xcalc_parser::is_number(char ch) {
if(ch >= '0' && ch <= '9') return 1;
if(ch == '.') return 2;
return 0;
}
int xcalc_parser::is_whitespaces(char ch) {
if(ch == ' ' ||
ch == '\r' ||
ch == '\t' ||
ch == '\n' ||
ch == '\v') {
// all are whitespaces
return 1;
}
return 0;
}
int xcalc_parser::parse(char *expr, xcalc_interface *xcalc_ptr) {
if(!xcalc_ptr) return -1;
xcalc_ptr->start_expression();
char *exp = expr;
int rc = 0;
string str;
while(*exp) {
rc = is_operator(*exp);
if(rc) {
if(!str.empty()) {
rc = xcalc_ptr->found_operand((char *)str.c_str());
if(rc) return rc;
str = "";
}
xcalc_ptr->found_operator(*exp);
}
else {
rc = is_parenthesis(*exp);
if(rc) {
if(!str.empty()) {
rc = xcalc_ptr->found_operand((char *)str.c_str());
if(rc) return rc;
str = "";
}
if(rc == 1) {
// '('
rc = xcalc_ptr->found_left_parenthesis();
if(rc) return rc;
}
else {
// ')'
rc = xcalc_ptr->found_right_parenthesis();
if(rc) return rc;
}
}
else {
if(is_whitespaces(*exp)) {
if(!str.empty()) {
rc = xcalc_ptr->found_operand((char *)str.c_str());
if(rc) return rc;
str = "";
}
}
else {
if(is_number(*exp)) {
str += *exp;
}
else {
// function found such as cos, sin, tan, etc
}
}
}
}
// next character
exp++;
}
if(!str.empty()) {
rc = xcalc_ptr->found_operand((char *)str.c_str());
if(rc) return rc;
}
rc = xcalc_ptr->end_expression();
return rc;
}
xcalc::xcalc()
: errno_(error_none),
errtext_() {
}
int xcalc::parse(char *expr) {
return xcalc_parser::parse(expr, this);
}
int xcalc::execute(char *expr, int *type, char *out) {
int rc = parse(expr);
if(rc) {
*type = errno_;
sprintf(out, "%s", errtext_.c_str());
return rc;
}
//if(operand_stack_.empty()) return unavailable_output;
xcalc_operand op_stack = operand_stack_.top();
*type = op_stack.type_;
sprintf(out, "%s", op_stack.operand_.c_str());
return 0;
}
void xcalc::start_expression() {
#ifdef DEBUG
polish_.clear();
#endif
prev_op = -1;
while(!operator_stack_.empty()) operator_stack_.pop();
while(!operand_stack_.empty()) operand_stack_.pop();
}
int xcalc::end_expression() {
// pop all operator stack remain
while(!operator_stack_.empty()) {
xcalc_operator op_stack = operator_stack_.top();
if(op_stack.operator_ == '(') {
found_error(imbalance_parenthesis, 0);
return imbalance_parenthesis;
}
//evaluate expression
int rc = evaluate(op_stack.operator_);
if(rc) return rc;
#ifdef DEBUG
polish_.push_back(string(1, op_stack.operator_));
#endif
// remove the top
operator_stack_.pop();
}
#ifdef DEBUG
vector<string>::iterator it = polish_.begin();
cout << "\nPolish: ";
for(; it != polish_.end(); it++)
cout << *it << ", ";
cout << endl;
#endif
// the operand stack must only be one element left
if(operand_stack_.size() != 1) {
//cout << "operand stack size: " << operand_stack_.size() << endl;
//cout << "operator stack size: " << operator_stack_.size() << endl;
found_error(unavailable_output, 0);
return unavailable_output;
}
return error_none;
}
void xcalc::found_error(xcalc_error_t err_no, char *param) {
string msg;
switch(err_no) {
case imbalance_parenthesis:
msg = "Imbalance parenthesis";
cerr << msg << endl;
break;
case incorrect_operand:
msg = "Incorrect operand: ";
msg += param;
cerr << msg << endl;
break;
case require_2_operands:
msg = "Require 2 operands";
cerr << msg << endl;
break;
case divided_by_zero:
msg = "Divided by zero";
cerr << msg << endl;
break;
case unknown_operator:
msg = "Unknown operator: ";
msg += param;
cerr << msg << endl;
break;
case unavailable_output:
msg = "Unavailable output";
cerr << msg << endl;
break;
case incomplete_minus_operand:
msg = "Incomplete minus operand";
cerr << msg << endl;
break;
}
// save error message
errno_ = err_no;
errtext_ = msg;
}
int xcalc::found_operator(char op) {
#ifdef DEBUG
//cout << op << " ";
#endif
int precedence = get_precedence(op);
xcalc_operator op_type;
op_type.precedence_ = precedence;
op_type.operator_ = op;
if(operator_stack_.empty()) {
operator_stack_.push(op_type);
}
else {
xcalc_operator op_stack = operator_stack_.top();
if(op == '-' && (prev_op == -1 || prev_op == 2)) { //prev_op = '('
operator_stack_.push(op_type);
return error_none;
}
if(op_type.precedence_ > op_stack.precedence_) {
operator_stack_.push(op_type);
}
else if(op_type.precedence_ == op_stack.precedence_) {
// remove the top
operator_stack_.pop();
int rc = evaluate(op_stack.operator_);
if(rc) return rc;
#ifdef DEBUG
polish_.push_back(string(1, op_stack.operator_));
#endif
// push the new operator
operator_stack_.push(op_type);
}
else {
// evaluate the expression
while(op_type.precedence_ <= op_stack.precedence_ && op_stack.operator_ != '(') {
//remove the top of the operator stack
operator_stack_.pop();
// evaluate expresstion
int rc = evaluate(op_stack.operator_);
if(rc) return rc;
#ifdef DEBUG
polish_.push_back(string(1, op_stack.operator_));
#endif
if(operator_stack_.empty()) {
break;
}
else {
op_stack = operator_stack_.top();
}
}
//push the new operator
operator_stack_.push(op_type);
}
} // operator_stack_ is not empty
prev_op = 1;
return error_none;
}
int xcalc::found_operand(char *op) {
#ifdef DEBUG
//cout << op << " ";
#endif
int type = find_type(op);
if(type == -1) {
found_error(incorrect_operand, op);
return incorrect_operand;
}
//evaluate expression
if(!operator_stack_.empty()) {
xcalc_operator operator_type = operator_stack_.top();
if(operator_type.operator_ == '-' && (prev_op == 2 || operand_stack_.size() == 0)) { //prev_op = '('
xcalc_operand op_type2;
//remove the top
//operand_stack_.pop();
char buffer[32];
if(type == 1) { //integer
long l1 = atol(op);
long l2 = (0 - l1);
sprintf(buffer, "%d", l2);
}
else {
float f1 = atof(op);
float f2 = (0.0f - f1);
sprintf(buffer, "%f", f2);
}
op_type2.type_ = type;
op_type2.operand_ = buffer;
// push back the operand
operand_stack_.push(op_type2);
operator_stack_.pop(); // remove the '-' operator
#ifdef DEBUG
polish_.push_back(buffer);
#endif
return error_none;
}
}
}
xcalc_operand op_type;
op_type.type_ = type;
op_type.operand_ = op;
operand_stack_.push(op_type);
#ifdef DEBUG
polish_.push_back(string(op));
#endif
return error_none;
}
int xcalc::found_left_parenthesis() {
#ifdef DEBUG
//cout << "( ";
#endif
char op = '(';
int precedence = get_precedence(op);
xcalc_operator op_type;
op_type.precedence_ = precedence;
op_type.operator_ = op;
operator_stack_.push(op_type);
prev_op = 2;
return error_none;
}
int xcalc::found_right_parenthesis() {
#ifdef DEBUG
//cout << ") ";
#endif
// pop operator stack until found '(' in the operator stack
// also evaluate the expression
if(operator_stack_.empty()) {
found_error(imbalance_parenthesis, 0);
return imbalance_parenthesis;
}
int found_left_parenthesis = 0;
while(!operator_stack_.empty()) {
xcalc_operator op_stack = operator_stack_.top();
if(op_stack.operator_ == '(') {
// don't use
found_left_parenthesis = 1;
operator_stack_.pop();
break;
}
// evaluate expression
int rc = evaluate(op_stack.operator_);
if(rc) return rc;
#ifdef DEBUG
polish_.push_back(string(1, op_stack.operator_));
#endif
// remove the top
operator_stack_.pop();
}
if(!found_left_parenthesis) {
found_error(imbalance_parenthesis, 0);
return imbalance_parenthesis;
}
prev_op = 3;
return error_none;
}
int xcalc::get_precedence(char op) {
switch(op) {
case '+':
case '-':
return 1;
case '*':
case '/':
case '%':
return 2;
case '^':
return 3;
case '(':
case ')':
return 4;
}
return 0;
}
int xcalc::find_type(char *op) {
//if op is integer, return 1
//else op is float, return 2
//otherwise, -1 (error)
int dot_cnt = 0;
while(*op) {
if(*op == '.') dot_cnt++;
op++;
}
if(dot_cnt == 0) return 1;
else if(dot_cnt == 1) return 2;
return -1;
}
// all operators require 2 operands
int xcalc::evaluate(char op) {
xcalc_operand op1, op2;
if(!operand_stack_.empty()) {
op2 = operand_stack_.top();
operand_stack_.pop();
}
else {
found_error(require_2_operands, 0);
return require_2_operands;
}
if(!operand_stack_.empty()) {
op1 = operand_stack_.top();
operand_stack_.pop();
}
else {
found_error(require_2_operands, 0);
return require_2_operands;
}
// got 2 operands, then evaluate them
char buffer[32];
if(op1.type_ == 1 && op2.type_ == 1) {
// both are integer
long l1 = atol(op1.operand_.c_str());
long l2 = atol(op2.operand_.c_str());
long l3 = 0;
switch(op) {
case '+': l3 = l1+l2; sprintf(buffer, "%d", l3); break;
case '-': l3 = l1-l2; sprintf(buffer, "%d", l3); break;
case '*': l3 = l1*l2; sprintf(buffer, "%d", l3); break;
case '/': {
if(l2 == 0) {
found_error(divided_by_zero, 0);
return divided_by_zero; // divided by zero
}
sprintf(buffer, "%f", ((float)l1/(float)l2));
op1.type_ = 2;
break;
}
case '%': l3 = l1%l2; sprintf(buffer, "%d", l3); break;
case '^': l3 = (long)pow((float)l1, (int)l2); sprintf(buffer, "%d", l3); break;
}
op1.operand_ = buffer;
operand_stack_.push(op1);
}
else {
float f1 = atof(op1.operand_.c_str());
float f2 = atof(op2.operand_.c_str());
float f3 = 0.0f;
char buffer[32];
switch(op) {
case '+': f3 = f1+f2; sprintf(buffer, "%f", f3); break;
case '-': f3 = f1-f2; sprintf(buffer, "%f", f3); break;
case '*': f3 = f1*f2; sprintf(buffer, "%f", f3); break;
case '/': {
if(f2 == 0.0f) {
found_error(divided_by_zero, 0);
return divided_by_zero; // divided by zero
}
f3 = f1/f2;
sprintf(buffer, "%f", f3);
break;
}
case '%': f3 = (float)((long)f1%(long)f2); sprintf(buffer, "%f", f3); break;
case '^': f3 = pow(f1, f2); sprintf(buffer, "%f", f3); break;
}
op1.operand_ = buffer;
op1.type_ = 2;
operand_stack_.push(op1);
}
return error_none; // successful
}
///////////////////////////////////////////////////////////////////////////
// test.cpp
// Author: Seree Rakwong
// Date: 19-NOV-10
// Purpose: Evaluate an expression
#include "xcalc.h"
using namespace std;
int main(int argc, char **argv) {
if(argc < 2) {
cerr << "USAGE: " << argv[0] << " expr" << endl;
return 1;
}
cout << "Input: " << argv[1] << endl;
int type;
char out[64];
xcalc calc;
calc.execute(argv[1], &type, out);
cout << "type:[" << type << "]" << endl;
cout << "out:[" << out << "]" << endl;
return 0;
}
ไม่มีความคิดเห็น:
แสดงความคิดเห็น