Created
March 10, 2017 12:41
-
-
Save nicktogo/cbca86ddb37b4ff60d8fd7a80e4187b8 to your computer and use it in GitHub Desktop.
The following code snippet is used toconvert an infix notation to a Reverse Polish notation and calculate it.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| void RPOUtil::Parse(TCHAR* exp) { // exp is the right hand side of an math equation, such as "2x + sin(x)" | |
| int length = ::wcslen(exp); | |
| char* cexp = new char[length + 1]; | |
| for (size_t i = 0; i < length; i++) { | |
| cexp[i] = exp[i]; | |
| } | |
| cexp[length] = '\0'; | |
| string str(cexp); | |
| Replace(str); // replace "sin", "cos", "tan", "log" with "s", "c", "t", "l" respectively | |
| length = str.length(); | |
| char after[255]; | |
| strncpy_s(after, str.c_str(), sizeof(after)); | |
| after[sizeof(after) - 1] = 0; | |
| stack<char> operands; // digit or x (variable) | |
| stack<char> operators; // operators such as: '+', '-', '*', '/', '^', 's', 'c', 't', 'l', '(', ')' | |
| for (int i = 0; i < length; i++) { | |
| char c = after[i]; | |
| if (isOperand(c)) { // digit or x (variable) | |
| operands.push(c); | |
| } | |
| else { | |
| if (c == '(') { | |
| operators.push(c); | |
| } | |
| else if (c == ')') { | |
| while (operators.top() != '(') { | |
| char ch = popStackTop(&operators); | |
| operands.push(ch); | |
| } | |
| operators.pop(); | |
| if (isSingleOperator(operators.top())) { // single operator defined as "s", "c", "t", "l" | |
| char ch = popStackTop(&operators); | |
| operands.push(ch); | |
| } | |
| } | |
| else { | |
| if (operators.empty() || operators.top() == '(') { | |
| operators.push(c); | |
| } | |
| else { | |
| if (isHigher(c, operators.top())) { // compare the priority of operators | |
| operators.push(c); | |
| } | |
| else { | |
| char top = operators.top(); | |
| operands.push(top); | |
| operators.pop(); | |
| operators.push(c); | |
| } | |
| } | |
| } | |
| } | |
| } | |
| while (!operators.empty()) { | |
| char ch = popStackTop(&operators); | |
| operands.push(ch); | |
| } | |
| while (!ops.empty()) { | |
| popStackTop(&ops); | |
| } | |
| while (!operands.empty()) { | |
| char ch = popStackTop(&operands); | |
| ops.push(ch); | |
| } | |
| } | |
| double RPOUtil::Calculate(double i) { | |
| stack<double> resultStack; | |
| stack<char> opscpy = ops; | |
| while (!opscpy.empty()) { | |
| char c = popStackTop(&opscpy); | |
| double temp; | |
| if (isOperand(c)) { | |
| double number; | |
| number = isX(c) ? i : (double)atoi(&c); | |
| resultStack.push(number); | |
| } | |
| else if (isSingleOperator(c)) { | |
| double rhs = popStackTop(&resultStack); | |
| temp = operate(c, rhs); | |
| resultStack.push(temp); | |
| } | |
| else { | |
| double rhs = popStackTop(&resultStack); | |
| double lhs = popStackTop(&resultStack); | |
| temp = operate(c, lhs, rhs); | |
| resultStack.push(temp); | |
| } | |
| } | |
| return resultStack.top(); | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment