#include "stdafx.h" #include #include #include #include "MathExpression.h" namespace expInterpreter { const int expr_str_err_N = 5; const char *expr_str_err[] = { "unknown error.", // error code 0 "unexcepted end.", // error code 1 "operator error.", // error code 2 "input data error.", // error code 3 "expression too long." // error code 4 }; const int compute_err_N = 5; const char *compute_err[] = { "unknown error.", // error code 0 "compute data error.", // error code 1 "input data error.", // error code 2 "devided by zero.", // error code 3 "pow return non." // error code 4 }; // read an element from the string at the start position and put it into atom,finish at the end position,if parse finished return -1 int read_atom(Atom *atom, const char *exprStr, int start); //read a digit from the string at the start position and put it into result,finish at the end position,if parse finished return -1 int read_digit(double *result, const char *exprStr, int start); // judge whether the character is a letter inline bool isEmpty(char ch); //judge whether the character is a digit inline bool isDigit(char ch); // judge whether the character is a symbol inline bool isSymbol(char ch); // judge whether the character is a variable inline bool isVariable(char ch); // get the atom's character symbol char atom_symbol(Atom *atom); // judge if the two atoms are legal to be connected enum BL { F = 0, T = 1 }; // T true£¬F false BL legel_Atom(Atom *atom1, Atom *atom2); BL legel_Atom(char ch1, char ch2); enum CR { A = 0, B = 1, D = 2, E = 3 }; // A greater£¬B lesser £¬D equal£¬E error // judge the two symbols' priority CR compare_symbol(char ch1, char ch2); //the length of the expression string const int Expression::poland_MAX = 255; Expression::Expression() { this->poland = new Atom[poland_MAX]; this->poland[0].type = ATOM_END; this->poland_N = 0; this->var = new double[26]; for (unsigned int i = 0; i < 26; i++) { this->var[i] = 1; // initialize the variable value to 1 } } Expression::~Expression() { delete[] this->poland; delete[] this->var; } int Expression::SetExprStr(const char *exprStr) { Atom Bak, Now; this->poland_N = 0; char symbol_stack[poland_MAX]; int symbol_stack_N = 0; symbol_stack[symbol_stack_N++] = '#'; Bak.type = ATOM_END; int index = 0; int error_code = 0; while (symbol_stack_N) { if (index < 0) // if the expression is over { error_code = 1; goto error_return; } index = read_atom(&Now, exprStr, index); if (!legel_Atom(&Bak, &Now)) // judge whether the atom is legal { if (Now.type == ATOM_SYMBOL && Now.value.symbol == '-') // try the multi meaning of the one dmenshional { Now.value.symbol = '~'; if (!legel_Atom(&Bak, &Now)) { error_code = 2; goto error_return; } } else { error_code = 2; goto error_return; } } switch (Now.type) //calculate according to the atom type { case ATOM_ERROR: error_code = 3; goto error_return; break; case ATOM_SYMBOL: // atom symbol,include the end sign case ATOM_END: { bool poped = true; char ch = atom_symbol(&Now); while (poped) { switch (compare_symbol(symbol_stack[symbol_stack_N - 1], ch)) // compare the current operator with the top of the symbol stack { case A: // the last symbol's priority is higher, then do the last operator's operation this->poland[this->poland_N].type = ATOM_SYMBOL; this->poland[this->poland_N].value.symbol = symbol_stack[symbol_stack_N - 1]; this->poland_N++; if (this->poland_N >= poland_MAX) { error_code = 4; goto error_return; } symbol_stack_N--; poped = true; break; case B: // this time's operator is higher, then push the symbol into the stack, waiting for process symbol_stack[symbol_stack_N++] = ch; poped = false; break; case D: // the priority is equal, such as '(' and ')', pop the top of the stack symbol_stack_N--; poped = false; break; case E: // the priority is error, such as '(', ')', '~', '^' and so on error_code = 2; goto error_return; } } } break; case ATOM_CONSTANT: // variable or constant,push into the reverse polish notation case ATOM_VARIABLE: this->poland[this->poland_N++] = Now; if (this->poland_N >= poland_MAX) { error_code = 4; goto error_return; } break; } Bak = Now; } this->poland[this->poland_N].type = ATOM_END; return 0; error_return: return error_code; } const char *Expression::GetExprErrorStr(int err) { return err < 1 ? expr_str_err[0] : err >= expr_str_err_N ? expr_str_err[0] : expr_str_err[err]; } const char *Expression::GetResultErrorStr(int err) { return err < 1 ? compute_err[0] : err >= compute_err_N ? compute_err[0] : compute_err[err]; } void Expression::SetVar(char x, double value) { if (!isVariable(x)) return; x |= 0x20; // convert the character to lower case this->var[x - 'a'] = value; } int Expression::GetResult(double *result) { double digit[poland_MAX]; //reverse polish notation auxiliary stack int digit_N = 0; int index = 0; int error_code = 0; for (index = 0; index < this->poland_N; index++) { switch (this->poland[index].type) { case ATOM_ERROR: error_code = 2; goto error_return; break; case ATOM_SYMBOL: switch (this->poland[index].value.symbol) { case '+': if (digit_N < 2) { error_code = 1; goto error_return; } digit[digit_N - 2] = digit[digit_N - 2] + digit[digit_N - 1]; digit_N--; break; case '-': if (digit_N < 2) { error_code = 1; goto error_return; } digit[digit_N - 2] = digit[digit_N - 2] - digit[digit_N - 1]; digit_N--; break; case '*': if (digit_N < 2) { error_code = 1; goto error_return; } digit[digit_N - 2] = digit[digit_N - 2] * digit[digit_N - 1]; digit_N--; break; case '/': if (digit_N < 2) { error_code = 1; goto error_return; } digit[digit_N - 2] = digit[digit_N - 2] / digit[digit_N - 1]; digit_N--; if (!_finite(digit[digit_N - 1])) { error_code = 3; goto error_return; } break; case '^': if (digit_N < 2) { error_code = 1; goto error_return; } digit[digit_N - 2] = pow(digit[digit_N - 2], digit[digit_N - 1]); digit_N--; if (_isnan(digit[digit_N - 1])) { error_code = 4; goto error_return; } break; case '~': if (digit_N < 1) { error_code = 1; goto error_return; } digit[digit_N - 1] = -digit[digit_N - 1]; break; } break; case ATOM_CONSTANT: digit[digit_N++] = this->poland[index].value.constant; break; case ATOM_VARIABLE: digit[digit_N++] = this->var[this->poland[index].value.variable - 'a']; break; case ATOM_END: break; } } if (digit_N != 1) { error_code = 1; goto error_return; } else { *result = digit[0]; return 0; } error_return: return error_code; } const Atom *Expression::GetPoland() { return this->poland; } // compitable matrix BL legel_matrix[10][10] = { // + - * / ^ ( ) i ~ # F, F, F, F, F, T, F, T, T, F, // + F, F, F, F, F, T, F, T, T, F, // - F, F, F, F, F, T, F, T, T, F, // * F, F, F, F, F, T, F, T, T, F, // / F, F, F, F, F, T, F, T, T, F, // ^ F, F, F, F, F, T, F, T, T, F, // ( T, T, T, T, T, F, T, F, F, T, // ) T, T, T, T, T, F, T, F, F, T, // i F, F, F, F, F, T, F, T, F, F, // ~ F, F, F, F, F, T, F, T, T, F, // # }; // compitable matrix down index value char legel_matrix_ch[10] = { '+', '-', '*', '/', '^', '(', ')', 'i', '~', '#', }; // priority matrix CR cmp_matrix[9][9] = { // + - * / ^ ( ) ~ # A, A, B, B, B, B, A, B, A, // + A, A, B, B, B, B, A, B, A, // - A, A, A, A, B, B, A, B, A, // * A, A, A, A, B, B, A, B, A, // / A, A, A, A, A, B, A, B, A, // ^ B, B, B, B, B, B, D, B, E, // ( E, E, E, E, E, E, E, E, E, // ) A, A, A, A, A, B, A, A, A, // ~ B, B, B, B, B, B, E, B, D, // # }; // compatible matrix down index value char cmp_matrix_ch[9] = { '+', '-', '*', '/', '^', '(', ')', '~', '#', }; BL legel_Atom(char ch1, char ch2) { int index1 = 0; while (legel_matrix_ch[index1] != ch1 && index1 < 10) index1++; if (index1 == 10) return F; int index2 = 0; while (legel_matrix_ch[index2] != ch2 && index2 < 10) index2++; if (index2 == 10) return F; return legel_matrix[index1][index2]; } char atom_symbol(Atom *atom) { switch (atom->type) { case ATOM_ERROR: return -1; case ATOM_SYMBOL: return atom->value.symbol; case ATOM_CONSTANT: case ATOM_VARIABLE: return 'i'; case ATOM_END: return '#'; } return -1; } BL legel_Atom(Atom *atom1, Atom *atom2) { char ch1 = atom_symbol(atom1); if (ch1 < 0) return F; char ch2 = atom_symbol(atom2); if (ch2 < 0) return F; return legel_Atom(ch1, ch2); } CR compare_symbol(char ch1, char ch2) { int index1 = 0; while (cmp_matrix_ch[index1] != ch1 && index1 < 9) index1++; if (index1 == 9) return E; int index2 = 0; while (cmp_matrix_ch[index2] != ch2 && index2 < 9) index2++; if (index2 == 9) return E; return cmp_matrix[index1][index2]; } int read_atom(Atom *atom, const char *exprStr, int start) { while (isEmpty(exprStr[start])) start++; if (exprStr[start] == '\0') { atom->type = ATOM_END; return -1; } if (isVariable(exprStr[start])) { atom->type = ATOM_VARIABLE; atom->value.variable = exprStr[start] | 0x20; // the variable length is only 1, convert to lower case start++; } else if (isSymbol(exprStr[start])) { atom->type = ATOM_SYMBOL; atom->value.symbol = exprStr[start]; start++; } else if (isDigit(exprStr[start])) // while is digit,call the library function to read a real number { double digit; start = read_digit(&digit, exprStr, start); atom->type = ATOM_CONSTANT; atom->value.constant = digit; } else { atom->type = ATOM_ERROR; start++; } return start; } int read_digit(double *result, const char *exprStr, int start) //lever the libary function to read a real number { int len = 0; while (isDigit(exprStr[start + len])) len++; *result = atof(exprStr + start); start += len; return start; } inline bool isEmpty(char ch) { return (ch == ' ' || ch == '\t' || ch == '\r' || ch == '\n'); } inline bool isDigit(char ch) { return (ch == '.' || (ch >= '0' && ch <= '9')); } const int sml_N = 7; const char sml[] = { '+', '-', '*', '/', '^', '(', ')' }; inline bool isSymbol(char ch) { for (unsigned int i = 0; i < sml_N; i++) { if (ch == sml[i]) return true; } return false; } inline bool isVariable(char ch) { return ((ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z')); } }