| #include "expr_eval.h" |
| #include "arch_error.h" |
| #include "vtr_util.h" |
| #include "vtr_math.h" |
| #include <vector> |
| #include <stack> |
| #include <string> |
| #include <sstream> |
| #include <cstring> //memset |
| |
| using std::stack; |
| using std::string; |
| using std::stringstream; |
| using std::vector; |
| |
| /**** Enums ****/ |
| /* Used to identify the type of symbolic formula object */ |
| typedef enum e_formula_obj { |
| E_FML_UNDEFINED = 0, |
| E_FML_NUMBER, |
| E_FML_BRACKET, |
| E_FML_COMMA, |
| E_FML_OPERATOR, |
| E_FML_NUM_FORMULA_OBJS |
| } t_formula_obj; |
| |
| /* Used to identify an operator in a formula */ |
| typedef enum e_operator { |
| E_OP_UNDEFINED = 0, |
| E_OP_ADD, |
| E_OP_SUB, |
| E_OP_MULT, |
| E_OP_DIV, |
| E_OP_MIN, |
| E_OP_MAX, |
| E_OP_GCD, |
| E_OP_LCM, |
| E_OP_NUM_OPS |
| } t_operator; |
| |
| /**** Class Definitions ****/ |
| /* This class is used to represent an object in a formula, such as |
| * a number, a bracket, an operator, or a variable */ |
| class Formula_Object { |
| public: |
| /* indicates the type of formula object this is */ |
| t_formula_obj type; |
| |
| /* object data, accessed based on what kind of object this is */ |
| union u_Data { |
| int num; /*for number objects*/ |
| t_operator op; /*for operator objects*/ |
| bool left_bracket; /*for bracket objects -- specifies if this is a left bracket*/ |
| |
| u_Data() { memset(this, 0, sizeof(u_Data)); } |
| } data; |
| |
| Formula_Object() { |
| this->type = E_FML_UNDEFINED; |
| } |
| |
| std::string to_string() const { |
| if (type == E_FML_NUMBER) { |
| return std::to_string(data.num); |
| } else if (type == E_FML_BRACKET) { |
| if (data.left_bracket) { |
| return "("; |
| } else { |
| return ")"; |
| } |
| } else if (type == E_FML_COMMA) { |
| return ","; |
| } else if (type == E_FML_OPERATOR) { |
| if (data.op == E_OP_ADD) { |
| return "+"; |
| } else if (data.op == E_OP_SUB) { |
| return "-"; |
| } else if (data.op == E_OP_MULT) { |
| return "*"; |
| } else if (data.op == E_OP_DIV) { |
| return "/"; |
| } else if (data.op == E_OP_MIN) { |
| return "min"; |
| } else if (data.op == E_OP_MAX) { |
| return "max"; |
| } else if (data.op == E_OP_GCD) { |
| return "gcd"; |
| } else if (data.op == E_OP_LCM) { |
| return "lcm"; |
| } else { |
| return "???"; //Unkown |
| } |
| } else { |
| return "???"; //Unkown |
| } |
| } |
| }; |
| |
| /*---- Functions for Parsing the Symbolic Formulas ----*/ |
| |
| /* converts specified formula to a vector in reverse-polish notation */ |
| static void formula_to_rpn(const char* formula, const t_formula_data& mydata, vector<Formula_Object>& rpn_output); |
| |
| static void get_formula_object(const char* ch, int& ichar, const t_formula_data& mydata, Formula_Object* fobj); |
| |
| /* returns integer specifying precedence of passed-in operator. higher integer |
| * means higher precedence */ |
| static int get_fobj_precedence(const Formula_Object& fobj); |
| |
| /* Returns associativity of the specified operator */ |
| static bool op_associativity_is_left(const t_operator& op); |
| |
| /* used by the shunting-yard formula parser to deal with operators such as add and subtract */ |
| static void handle_operator(const Formula_Object& fobj, vector<Formula_Object>& rpn_output, stack<Formula_Object>& op_stack); |
| |
| /* used by the shunting-yard formula parser to deal with brackets, ie '(' and ')' */ |
| static void handle_bracket(const Formula_Object& fobj, vector<Formula_Object>& rpn_output, stack<Formula_Object>& op_stack); |
| |
| /* used by the shunting-yard formula parser to deal with commas, ie ','. These occur in function calls*/ |
| static void handle_comma(const Formula_Object& fobj, vector<Formula_Object>& rpn_output, stack<Formula_Object>& op_stack); |
| |
| /* parses revere-polish notation vector to return formula result */ |
| static int parse_rpn_vector(vector<Formula_Object>& rpn_vec); |
| |
| /* applies operation specified by 'op' to the given arguments. arg1 comes before arg2 */ |
| static int apply_rpn_op(const Formula_Object& arg1, const Formula_Object& arg2, const Formula_Object& op); |
| |
| /* checks if specified character represents an ASCII number */ |
| static bool is_char_number(const char ch); |
| |
| // returns true if ch is an operator |
| static bool is_operator(const char ch); |
| |
| // returns true if the specified name is an known function operator |
| static bool is_function(std::string name); |
| |
| // returns the length of any identifier (e.g. name, function) starting at the beginning of str |
| static int identifier_length(const char* str); |
| |
| /* increments str_ind until it reaches specified char is formula. returns true if character was found, false otherwise */ |
| static bool goto_next_char(int* str_ind, const string& pw_formula, char ch); |
| |
| /**** Function Implementations ****/ |
| /* returns integer result according to specified non-piece-wise formula and data */ |
| int parse_formula(std::string formula, const t_formula_data& mydata) { |
| int result = -1; |
| |
| /* output in reverse-polish notation */ |
| vector<Formula_Object> rpn_output; |
| |
| /* now we have to run the shunting-yard algorithm to convert formula to reverse polish notation */ |
| formula_to_rpn(formula.c_str(), mydata, rpn_output); |
| |
| /* then we run an RPN parser to get the final result */ |
| result = parse_rpn_vector(rpn_output); |
| |
| return result; |
| } |
| |
| /* EXPERIMENTAL: |
| * |
| * returns integer result according to specified piece-wise formula and data. the piecewise |
| * notation specifies different formulas that should be evaluated based on the index of |
| * the incoming wire in 'mydata'. for example the formula |
| * |
| * {0:(W/2)} t-1; {(W/2):W} t+1; |
| * |
| * indicates that the function "t-1" should be evaluated if the incoming wire index falls |
| * within the range [0,W/2) and that "t+1" should be evaluated if it falls within the |
| * [W/2,W) range. The piece-wise format is: |
| * |
| * {start_0:end_0} formula_0; ... {start_i;end_i} formula_i; ... |
| */ |
| int parse_piecewise_formula(const char* formula, const t_formula_data& mydata) { |
| int result = -1; |
| int str_ind = 0; |
| int str_size = 0; |
| |
| int t = mydata.get_var_value("t"); |
| int tmp_ind_start = -1; |
| int tmp_ind_count = -1; |
| string substr; |
| |
| /* convert formula to string format */ |
| string pw_formula(formula); |
| str_size = pw_formula.size(); |
| |
| if (pw_formula[str_ind] != '{') { |
| archfpga_throw(__FILE__, __LINE__, "parse_piecewise_formula: the first character in piece-wise formula should always be '{'\n"); |
| } |
| |
| /* find the range to which t corresponds */ |
| /* the first character must be '{' as verified above */ |
| while (str_ind != str_size - 1) { |
| /* set to true when range to which wire number corresponds has been found */ |
| bool found_range = false; |
| bool char_found = false; |
| int range_start = -1; |
| int range_end = -1; |
| tmp_ind_start = -1; |
| tmp_ind_count = -1; |
| |
| /* get the start of the range */ |
| tmp_ind_start = str_ind + 1; |
| char_found = goto_next_char(&str_ind, pw_formula, ':'); |
| if (!char_found) { |
| archfpga_throw(__FILE__, __LINE__, "parse_piecewise_formula: could not find char %c\n", ':'); |
| } |
| tmp_ind_count = str_ind - tmp_ind_start; /* range start is between { and : */ |
| substr = pw_formula.substr(tmp_ind_start, tmp_ind_count); |
| range_start = parse_formula(substr.c_str(), mydata); |
| |
| /* get the end of the range */ |
| tmp_ind_start = str_ind + 1; |
| char_found = goto_next_char(&str_ind, pw_formula, '}'); |
| if (!char_found) { |
| archfpga_throw(__FILE__, __LINE__, "parse_piecewise_formula: could not find char %c\n", '}'); |
| } |
| tmp_ind_count = str_ind - tmp_ind_start; /* range end is between : and } */ |
| substr = pw_formula.substr(tmp_ind_start, tmp_ind_count); |
| range_end = parse_formula(substr.c_str(), mydata); |
| |
| if (range_start > range_end) { |
| archfpga_throw(__FILE__, __LINE__, "parse_piecewise_formula: range_start, %d, is bigger than range end, %d\n", range_start, range_end); |
| } |
| |
| /* is the incoming wire within this range? (inclusive) */ |
| if (range_start <= t && range_end >= t) { |
| found_range = true; |
| } else { |
| found_range = false; |
| } |
| |
| /* we're done if found correct range */ |
| if (found_range) { |
| break; |
| } |
| char_found = goto_next_char(&str_ind, pw_formula, '{'); |
| if (!char_found) { |
| archfpga_throw(__FILE__, __LINE__, "parse_piecewise_formula: could not find char %c\n", '{'); |
| } |
| } |
| /* the string index should never actually get to the end of the string because we should have found the range to which the |
| * current wire number corresponds */ |
| if (str_ind == str_size - 1) { |
| archfpga_throw(__FILE__, __LINE__, "parse_piecewise_formula: could not find a closing '}'?\n"); |
| } |
| |
| /* at this point str_ind should point to '}' right before the formula we're interested in starts */ |
| /* get the value corresponding to this formula */ |
| tmp_ind_start = str_ind + 1; |
| goto_next_char(&str_ind, pw_formula, ';'); |
| tmp_ind_count = str_ind - tmp_ind_start; /* formula is between } and ; */ |
| substr = pw_formula.substr(tmp_ind_start, tmp_ind_count); |
| |
| /* now parse the formula corresponding to the appropriate piece-wise range */ |
| result = parse_formula(substr.c_str(), mydata); |
| |
| return result; |
| } |
| |
| /* increments str_ind until it reaches specified char in formula. returns true if character was found, false otherwise */ |
| static bool goto_next_char(int* str_ind, const string& pw_formula, char ch) { |
| bool result = true; |
| int str_size = pw_formula.size(); |
| if ((*str_ind) == str_size - 1) { |
| archfpga_throw(__FILE__, __LINE__, "goto_next_char: passed-in str_ind is already at the end of string\n"); |
| } |
| |
| do { |
| (*str_ind)++; |
| if (pw_formula[*str_ind] == ch) { |
| /* found the next requested character */ |
| break; |
| } |
| |
| } while ((*str_ind) != str_size - 1); |
| if ((*str_ind) == str_size - 1 && pw_formula[*str_ind] != ch) { |
| result = false; |
| } |
| return result; |
| } |
| |
| /* Parses the specified formula using a shunting yard algorithm (see wikipedia). The function's result |
| * is stored in the rpn_output vector in reverse-polish notation */ |
| static void formula_to_rpn(const char* formula, const t_formula_data& mydata, vector<Formula_Object>& rpn_output) { |
| stack<Formula_Object> op_stack; /* stack for handling operators and brackets in formula */ |
| Formula_Object fobj; /* for parsing formula objects */ |
| |
| int ichar = 0; |
| const char* ch = nullptr; |
| /* go through formula and build rpn_output along with op_stack until \0 character is hit */ |
| while (true) { |
| ch = &formula[ichar]; |
| |
| if ('\0' == (*ch)) { |
| /* we're done */ |
| break; |
| } else if (' ' == (*ch)) { |
| /* skip space */ |
| } else { |
| /* parse the character */ |
| get_formula_object(ch, ichar, mydata, &fobj); |
| switch (fobj.type) { |
| case E_FML_NUMBER: |
| /* add to output vector */ |
| rpn_output.push_back(fobj); |
| break; |
| case E_FML_OPERATOR: |
| /* operators may be pushed to op_stack or rpn_output */ |
| handle_operator(fobj, rpn_output, op_stack); |
| break; |
| case E_FML_BRACKET: |
| /* brackets are only ever pushed to op_stack, not rpn_output */ |
| handle_bracket(fobj, rpn_output, op_stack); |
| break; |
| case E_FML_COMMA: |
| handle_comma(fobj, rpn_output, op_stack); |
| break; |
| default: |
| archfpga_throw(__FILE__, __LINE__, "in formula_to_rpn: unknown formula object type: %d\n", fobj.type); |
| break; |
| } |
| } |
| ichar++; |
| } |
| |
| /* pop all remaining operators off of stack */ |
| Formula_Object fobj_dummy; |
| while (!op_stack.empty()) { |
| fobj_dummy = op_stack.top(); |
| |
| if (E_FML_BRACKET == fobj_dummy.type) { |
| archfpga_throw(__FILE__, __LINE__, "in formula_to_rpn: Mismatched brackets in user-provided formula\n"); |
| } |
| |
| rpn_output.push_back(fobj_dummy); |
| op_stack.pop(); |
| } |
| |
| return; |
| } |
| |
| /* Fills the formula object fobj according to specified character and mydata, |
| * which help determine which numeric value, if any, gets assigned to fobj |
| * ichar is incremented by the corresponding count if the need to step through the |
| * character array arises */ |
| static void get_formula_object(const char* ch, int& ichar, const t_formula_data& mydata, Formula_Object* fobj) { |
| /* the character can either be part of a number, or it can be an object like W, t, (, +, etc |
| * here we have to account for both possibilities */ |
| |
| int id_len = identifier_length(ch); |
| |
| if (id_len != 0) { |
| //We have a variable or function name |
| std::string var_name(ch, id_len); |
| |
| if (is_function(var_name)) { |
| fobj->type = E_FML_OPERATOR; |
| if (var_name == "min") |
| fobj->data.op = E_OP_MIN; |
| else if (var_name == "max") |
| fobj->data.op = E_OP_MAX; |
| else if (var_name == "gcd") |
| fobj->data.op = E_OP_GCD; |
| else if (var_name == "lcm") |
| fobj->data.op = E_OP_LCM; |
| else { |
| archfpga_throw(__FILE__, __LINE__, "in get_formula_object: recognized function: %s\n", var_name.c_str()); |
| } |
| |
| } else { |
| //A variable |
| fobj->type = E_FML_NUMBER; |
| fobj->data.num = mydata.get_var_value(var_name); |
| } |
| |
| ichar += (id_len - 1); //-1 since ichar is incremented at end of loop in formula_to_rpn() |
| |
| } else if (is_char_number(*ch)) { |
| /* we have a number -- use atoi to convert */ |
| stringstream ss; |
| while (is_char_number(*ch)) { |
| ss << (*ch); |
| ichar++; |
| ch++; |
| } |
| ichar--; |
| fobj->type = E_FML_NUMBER; |
| fobj->data.num = vtr::atoi(ss.str().c_str()); |
| } else { |
| switch ((*ch)) { |
| case '+': |
| fobj->type = E_FML_OPERATOR; |
| fobj->data.op = E_OP_ADD; |
| break; |
| case '-': |
| fobj->type = E_FML_OPERATOR; |
| fobj->data.op = E_OP_SUB; |
| break; |
| case '/': |
| fobj->type = E_FML_OPERATOR; |
| fobj->data.op = E_OP_DIV; |
| break; |
| case '*': |
| fobj->type = E_FML_OPERATOR; |
| fobj->data.op = E_OP_MULT; |
| break; |
| case '(': |
| fobj->type = E_FML_BRACKET; |
| fobj->data.left_bracket = true; |
| break; |
| case ')': |
| fobj->type = E_FML_BRACKET; |
| fobj->data.left_bracket = false; |
| break; |
| case ',': |
| fobj->type = E_FML_COMMA; |
| break; |
| default: |
| archfpga_throw(__FILE__, __LINE__, "in get_formula_object: unsupported character: %c\n", *ch); |
| break; |
| } |
| } |
| |
| return; |
| } |
| |
| /* returns integer specifying precedence of passed-in operator. higher integer |
| * means higher precedence */ |
| static int get_fobj_precedence(const Formula_Object& fobj) { |
| int precedence = 0; |
| |
| if (E_FML_BRACKET == fobj.type || E_FML_COMMA == fobj.type) { |
| precedence = 0; |
| } else if (E_FML_OPERATOR == fobj.type) { |
| t_operator op = fobj.data.op; |
| switch (op) { |
| case E_OP_ADD: //fallthrough |
| case E_OP_SUB: |
| precedence = 2; |
| break; |
| case E_OP_MULT: //fallthrough |
| case E_OP_DIV: |
| precedence = 3; |
| break; |
| case E_OP_MIN: //fallthrough |
| case E_OP_MAX: //fallthrough |
| case E_OP_LCM: //fallthrough |
| case E_OP_GCD: //fallthrough |
| precedence = 4; |
| break; |
| default: |
| archfpga_throw(__FILE__, __LINE__, "in get_fobj_precedence: unrecognized operator: %d\n", op); |
| break; |
| } |
| } else { |
| archfpga_throw(__FILE__, __LINE__, "in get_fobj_precedence: no precedence possible for formula object type %d\n", fobj.type); |
| } |
| |
| return precedence; |
| } |
| |
| /* Returns associativity of the specified operator */ |
| static bool op_associativity_is_left(const t_operator& /*op*/) { |
| bool is_left = true; |
| |
| /* associativity is 'left' for all but the power operator, which is not yet implemented */ |
| //TODO: |
| //if op is 'power' set associativity is_left=false and return |
| |
| return is_left; |
| } |
| |
| /* used by the shunting-yard formula parser to deal with operators such as add and subtract */ |
| static void handle_operator(const Formula_Object& fobj, vector<Formula_Object>& rpn_output, stack<Formula_Object>& op_stack) { |
| if (E_FML_OPERATOR != fobj.type) { |
| archfpga_throw(__FILE__, __LINE__, "in handle_operator: passed in formula object not of type operator\n"); |
| } |
| |
| int op_pr = get_fobj_precedence(fobj); |
| bool op_assoc_is_left = op_associativity_is_left(fobj.data.op); |
| |
| Formula_Object fobj_dummy; |
| bool keep_going = false; |
| do { |
| /* here we keep popping operators off the stack onto back of rpn_output while |
| * associativity of operator is 'left' and precedence op_pr = top_pr, or while |
| * precedence op_pr < top_pr */ |
| |
| /* determine whether we should keep popping operators off the op stack */ |
| if (op_stack.empty()) { |
| keep_going = false; |
| } else { |
| /* get precedence of top operator */ |
| int top_pr = get_fobj_precedence(op_stack.top()); |
| |
| keep_going = ((op_assoc_is_left && op_pr == top_pr) |
| || op_pr < top_pr); |
| |
| if (keep_going) { |
| /* pop top operator off stack onto the back of rpn_output */ |
| fobj_dummy = op_stack.top(); |
| rpn_output.push_back(fobj_dummy); |
| op_stack.pop(); |
| } |
| } |
| |
| } while (keep_going); |
| |
| /* place new operator object on top of stack */ |
| op_stack.push(fobj); |
| |
| return; |
| } |
| |
| /* used by the shunting-yard formula parser to deal with brackets, ie '(' and ')' */ |
| static void handle_bracket(const Formula_Object& fobj, vector<Formula_Object>& rpn_output, stack<Formula_Object>& op_stack) { |
| if (E_FML_BRACKET != fobj.type) { |
| archfpga_throw(__FILE__, __LINE__, "in handle_bracket: passed-in formula object not of type bracket\n"); |
| } |
| |
| /* check if left or right bracket */ |
| if (fobj.data.left_bracket) { |
| /* left bracket, so simply push it onto operator stack */ |
| op_stack.push(fobj); |
| } else { |
| bool keep_going = false; |
| do { |
| /* here we keep popping operators off op_stack onto back of rpn_output until a |
| * left bracket is encountered */ |
| |
| if (op_stack.empty()) { |
| /* didn't find an opening bracket - mismatched brackets */ |
| archfpga_throw(__FILE__, __LINE__, "Ran out of stack while parsing brackets -- bracket mismatch in user-specified formula\n"); |
| keep_going = false; |
| } |
| |
| Formula_Object next_fobj = op_stack.top(); |
| if (E_FML_BRACKET == next_fobj.type) { |
| if (next_fobj.data.left_bracket) { |
| /* matching bracket found -- pop off stack and finish */ |
| op_stack.pop(); |
| keep_going = false; |
| } else { |
| /* should not find two right brackets without a left bracket in-between */ |
| archfpga_throw(__FILE__, __LINE__, "Mismatched brackets encountered in user-specified formula\n"); |
| keep_going = false; |
| } |
| } else if (E_FML_OPERATOR == next_fobj.type) { |
| /* pop operator off stack onto the back of rpn_output */ |
| Formula_Object fobj_dummy = op_stack.top(); |
| rpn_output.push_back(fobj_dummy); |
| op_stack.pop(); |
| keep_going = true; |
| } else { |
| archfpga_throw(__FILE__, __LINE__, "Found unexpected formula object on operator stack: %d\n", next_fobj.type); |
| keep_going = false; |
| } |
| } while (keep_going); |
| } |
| return; |
| } |
| |
| /* used by the shunting-yard formula parser to deal with commas, ie ','. These occur in function calls*/ |
| static void handle_comma(const Formula_Object& fobj, vector<Formula_Object>& rpn_output, stack<Formula_Object>& op_stack) { |
| if (E_FML_COMMA != fobj.type) { |
| archfpga_throw(__FILE__, __LINE__, "in handle_comm: passed-in formula object not of type comma\n"); |
| } |
| |
| //Commas are treated as right (closing) bracket since it completes a |
| //sub-expression, except that we do not cause the left (opening) brack to |
| //be popped |
| |
| bool keep_going = true; |
| do { |
| /* here we keep popping operators off op_stack onto back of rpn_output until a |
| * left bracket is encountered */ |
| |
| if (op_stack.empty()) { |
| /* didn't find an opening bracket - mismatched brackets */ |
| archfpga_throw(__FILE__, __LINE__, "Ran out of stack while parsing comma -- bracket mismatch in user-specified formula\n"); |
| keep_going = false; |
| } |
| |
| Formula_Object next_fobj = op_stack.top(); |
| if (E_FML_BRACKET == next_fobj.type) { |
| if (next_fobj.data.left_bracket) { |
| /* matching bracket found */ |
| keep_going = false; |
| } else { |
| /* should not find two right brackets without a left bracket in-between */ |
| archfpga_throw(__FILE__, __LINE__, "Mismatched brackets encountered in user-specified formula\n"); |
| keep_going = false; |
| } |
| } else if (E_FML_OPERATOR == next_fobj.type) { |
| /* pop operator off stack onto the back of rpn_output */ |
| Formula_Object fobj_dummy = op_stack.top(); |
| rpn_output.push_back(fobj_dummy); |
| op_stack.pop(); |
| keep_going = true; |
| } else { |
| archfpga_throw(__FILE__, __LINE__, "Found unexpected formula object on operator stack: %d\n", next_fobj.type); |
| keep_going = false; |
| } |
| |
| } while (keep_going); |
| } |
| |
| /* parses a reverse-polish notation vector corresponding to a switchblock formula |
| * and returns the integer result */ |
| static int parse_rpn_vector(vector<Formula_Object>& rpn_vec) { |
| int result = -1; |
| |
| /* first entry should always be a number */ |
| if (E_FML_NUMBER != rpn_vec[0].type) { |
| archfpga_throw(__FILE__, __LINE__, "parse_rpn_vector: first entry is not a number (was %s)\n", rpn_vec[0].to_string().c_str()); |
| } |
| |
| if (rpn_vec.size() == 1) { |
| /* if the vector size is 1 then we just have a number (which was verified above) */ |
| result = rpn_vec[0].data.num; |
| } else { |
| /* have numbers and operators */ |
| Formula_Object fobj; |
| int ivec = 0; |
| /* keep going until we have gone through the whole vector */ |
| while (!rpn_vec.empty()) { |
| /* keep going until we have hit an operator */ |
| do { |
| ivec++; /* first item should never be operator anyway */ |
| if (ivec == (int)rpn_vec.size()) { |
| archfpga_throw(__FILE__, __LINE__, "parse_rpn_vector(): found multiple numbers in formula, but no operator\n"); |
| } |
| } while (E_FML_OPERATOR != rpn_vec[ivec].type); |
| |
| /* now we apply the selected operation to the two previous entries */ |
| /* the result is stored in the object that used to be the operation */ |
| rpn_vec[ivec].data.num = apply_rpn_op(rpn_vec[ivec - 2], rpn_vec[ivec - 1], rpn_vec[ivec]); |
| rpn_vec[ivec].type = E_FML_NUMBER; |
| |
| /* remove the previous two entries from the vector */ |
| rpn_vec.erase(rpn_vec.begin() + ivec - 2, rpn_vec.begin() + ivec - 0); |
| ivec -= 2; |
| |
| /* if we're down to one element, we are done */ |
| if (1 == rpn_vec.size()) { |
| result = rpn_vec[ivec].data.num; |
| rpn_vec.erase(rpn_vec.begin() + ivec); |
| } |
| } |
| } |
| |
| return result; |
| } |
| |
| /* applies operation specified by 'op' to the given arguments. arg1 comes before arg2 */ |
| static int apply_rpn_op(const Formula_Object& arg1, const Formula_Object& arg2, const Formula_Object& op) { |
| int result = -1; |
| |
| /* arguments must be numbers */ |
| if (E_FML_NUMBER != arg1.type || E_FML_NUMBER != arg2.type) { |
| archfpga_throw(__FILE__, __LINE__, "in apply_rpn_op: one of the arguments is not a number (was '%s %s %s')\n", arg1.to_string().c_str(), op.to_string().c_str(), arg2.to_string().c_str()); |
| } |
| |
| /* check that op is actually an operation */ |
| if (E_FML_OPERATOR != op.type) { |
| archfpga_throw(__FILE__, __LINE__, "in apply_rpn_op: the object specified as the operation is not of operation type\n"); |
| } |
| |
| /* apply operation to arguments */ |
| switch (op.data.op) { |
| case E_OP_ADD: |
| result = arg1.data.num + arg2.data.num; |
| break; |
| case E_OP_SUB: |
| result = arg1.data.num - arg2.data.num; |
| break; |
| case E_OP_MULT: |
| result = arg1.data.num * arg2.data.num; |
| break; |
| case E_OP_DIV: |
| result = arg1.data.num / arg2.data.num; |
| break; |
| case E_OP_MAX: |
| result = std::max(arg1.data.num, arg2.data.num); |
| break; |
| case E_OP_MIN: |
| result = std::min(arg1.data.num, arg2.data.num); |
| break; |
| case E_OP_GCD: |
| result = vtr::gcd(arg1.data.num, arg2.data.num); |
| break; |
| case E_OP_LCM: |
| result = vtr::lcm(arg1.data.num, arg2.data.num); |
| break; |
| default: |
| archfpga_throw(__FILE__, __LINE__, "in apply_rpn_op: invalid operation: %d\n", op.data.op); |
| break; |
| } |
| |
| return result; |
| } |
| |
| /* checks if specified character represents an ASCII number */ |
| static bool is_char_number(const char ch) { |
| bool result = false; |
| |
| if (ch >= '0' && ch <= '9') { |
| result = true; |
| } else { |
| result = false; |
| } |
| |
| return result; |
| } |
| |
| static bool is_operator(const char ch) { |
| switch (ch) { |
| case '+': //fallthrough |
| case '-': //fallthrough |
| case '/': //fallthrough |
| case '*': //fallthrough |
| case ')': //fallthrough |
| case '(': //fallthrough |
| case ',': |
| return true; |
| default: |
| return false; |
| } |
| } |
| |
| static bool is_function(std::string name) { |
| if (name == "min" |
| || name == "max" |
| || name == "gcd" |
| || name == "lcm") { |
| return true; |
| } |
| return false; |
| } |
| |
| //returns the length of the substring consisting of valid vairable characters from |
| //the start of the string |
| static int identifier_length(const char* str) { |
| int ichar = 0; |
| |
| if (!str) return 0; |
| |
| while (str[ichar] != '\0') { |
| //No whitespace |
| if (str[ichar] == ' ') break; |
| |
| //Not an operator |
| if (is_operator(str[ichar])) break; |
| |
| //First char must not be a number |
| if (ichar == 0 && is_char_number(str[ichar])) break; |
| |
| ++ichar; //Next character |
| } |
| |
| return ichar; |
| } |
| |
| /* checks if the specified formula is piece-wise defined */ |
| bool is_piecewise_formula(const char* formula) { |
| bool result = false; |
| /* if formula is piecewise, we expect '{' to be the very first character */ |
| if ('{' == formula[0]) { |
| result = true; |
| } else { |
| result = false; |
| } |
| return result; |
| } |
