Tag Archives: template
C++ || Multi Digit, Decimal & Negative Number Infix To Postfix Conversion & Evaluation
The following is sample code which demonstrates the implementation of a multi digit, decimal, and negative number infix to postfix converter and evaluator using a Finite State Machine
REQUIRED KNOWLEDGE FOR THIS PROGRAM
How To Convert Infix To Postfix
How To Evaluate A Postfix Expression
What Is A Finite State Machine?
Using a Finite State Machine, the program demonstrated on this page has the ability to convert and evaluate a single digit, multi digit, decimal number, and/or negative number infix equation. So for example, if the the infix equation of (19.87 * -2) was entered into the program, the converted postfix expression of 19.87 ~2* would display to the screen, as well as the final evaluated answer of -39.74.
NOTE: In this program, negative numbers are represented by the “~” symbol on the postfix string. This is used to differentiate between a negative number and a subtraction symbol.
This program has the following flow of control:
• Get an infix expression from the user
• Convert the infix expression to postfix
• Use a Finite State Machine to isolate all of the math operators, multi digit, decimal, negative and single digit numbers that are found in the postfix expression
• Evaluate the postfix expression using the tokens found from the above step
• Display the evaluated answer to the screen
The above steps are implemented below.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444 445 446 447 448 449 450 451 452 453 454 455 456 457 458 459 460 461 462 463 464 465 466 467 468 469 470 471 472 473 |
// ============================================================================ // Author: Kenneth Perkins // Taken From: http://programmingnotes.org/ // Date: Jan 31, 2014 // File: InToPostEval.cpp // Description: The following demonstrates the implementation of an infix to // postfix converter and evaluator. Using a Finite State Machine, this // program has the ability to convert and evaluate multi digit, decimal, // negative and positive values. // ============================================================================ #include <iostream> #include <cstdlib> #include <cmath> #include <cctype> #include <string> #include <vector> #include <stack> #include <algorithm> using namespace std; /* This holds the transition states for our Finite State Machine -- They are placed in numerical order for easy understanding within the FSM array, which is located below */ enum FSM_TRANSITIONS { REJECT = 0, INTEGER, REAL, NEGATIVE, OPERATOR, UNKNOWN, SPACE }; /* This is the Finite State Machine -- The zero represents a place holder, so the row in the array starts on row 1 instead of 0 integer, real, negative, operator, unknown, space */ int stateTable[][7] = { {0, INTEGER, REAL, NEGATIVE, OPERATOR, UNKNOWN, SPACE}, /* STATE 1 */ {INTEGER, INTEGER, REAL, REJECT, REJECT, REJECT, REJECT}, /* STATE 2 */ {REAL, REAL, REJECT, REJECT, REJECT, REJECT, REJECT}, /* STATE 3 */ {NEGATIVE, INTEGER, REAL, REJECT, REJECT, REJECT, REJECT}, /* STATE 4 */ {OPERATOR, REJECT, REJECT, REJECT, REJECT, REJECT, REJECT}, /* STATE 5 */ {UNKNOWN, REJECT, REJECT, REJECT, REJECT, UNKNOWN, REJECT}, /* STATE 6 */ {SPACE, REJECT, REJECT, REJECT, REJECT, REJECT, REJECT} }; // function prototypes void DisplayDirections(); string ConvertInfixToPostfix(string infix); bool IsMathOperator(char token); int OrderOfOperations(char token); vector<string> Lexer(string postfix); int Get_FSM_Col(char& currentChar); double EvaluatePostfix(const vector<string>& postfix); double Calculate(char token, double op1, double op2); int main() { // declare variables string infix = ""; string postfix = ""; double answer = 0; vector<string> tokens; // display directions to user DisplayDirections(); // get data from user cout << "\nPlease enter an Infix expression: "; getline(cin, infix); postfix = ConvertInfixToPostfix(infix); // use the "Lexer" function to isolate multi digit, negative and decimal // numbers, aswell as single digit numbers and math operators tokens = Lexer(postfix); // display the found tokens to the screen //for (unsigned x = 0; x < tokens.size(); ++x) //{ // cout<<tokens.at(x)<<endl; //} cout << "\nThe Infix expression = " << infix; cout << "\nThe Postfix expression = " << postfix << endl; answer = EvaluatePostfix(tokens); cout << "\nFinal answer = " << answer << endl; cin.get(); return 0; }// end of main void DisplayDirections() {// this function displays instructions to the screen cout << "\n==== Infix To Postfix Conversion & Evaluation ====\n" << "\nMath Operators:\n" << "+ || Addition\n" << "- || Subtraction\n" << "* || Multiplication\n" << "/ || Division\n" << "% || Modulus\n" << "^ || Power\n" << "$ || Square Root\n" << "s || Sine\n" << "c || Cosine\n" << "t || Tangent\n" << "- || Negative Number\n" << "Sample Infix Equation: ((s(-4^5)*1.4)/($(23+2)--2.8))*(c(1%2)/(7.28*.1987)^(t23))\n"; // ((sin(-4^5)*1.4)/(sqrt(23+2)--2.8))*(cos(1%2)/(7.28*.1987)^(tan(23))) }// end of DisplayDirections string ConvertInfixToPostfix(string infix) {// this function converts an infix expression to postfix // declare function variables string postfix; stack<char> charStack; // remove all whitespace from the string infix.erase(std::remove_if(infix.begin(), infix.end(), [](char c) { return std::isspace(static_cast<unsigned char>(c)); }), infix.end()); // automatically convert negative numbers to have the ~ symbol for (unsigned x = 0; x < infix.length(); ++x) { if (infix[x] != '-') { continue; } else if (x + 1 < infix.length() && IsMathOperator(infix[x + 1])) { continue; } if (x == 0 || infix[x - 1] == '(' || IsMathOperator(infix[x - 1])) { infix[x] = '~'; } } // loop thru array until there is no more data for (unsigned x = 0; x < infix.length(); ++x) { // place numbers (standard, decimal, & negative) // numbers onto the 'postfix' string if ((isdigit(infix[x])) || (infix[x] == '.') || (infix[x] == '~')) { postfix += infix[x]; } else if (isspace(infix[x])) { continue; } else if (IsMathOperator(infix[x])) { postfix += " "; // use the 'OrderOfOperations' function to check equality // of the math operator at the top of the stack compared to // the current math operator in the infix string while ((!charStack.empty()) && (OrderOfOperations(charStack.top()) >= OrderOfOperations(infix[x]))) { // place the math operator from the top of the // stack onto the postfix string and continue the // process until complete postfix += charStack.top(); charStack.pop(); } // push the remaining math operator onto the stack charStack.push(infix[x]); } // push outer parentheses onto stack else if (infix[x] == '(') { charStack.push(infix[x]); } else if (infix[x] == ')') { // pop the current math operator from the stack while ((!charStack.empty()) && (charStack.top() != '(')) { // place the math operator onto the postfix string postfix += charStack.top(); // pop the next operator from the stack and // continue the process until complete charStack.pop(); } if (!charStack.empty()) // pop '(' symbol off the stack { charStack.pop(); } else // no matching '(' { cout << "\nPARENTHESES MISMATCH #1\n"; exit(1); } } else { cout << "\nINVALID INPUT #1\n"; exit(1); } } // place any remaining math operators from the stack onto // the postfix array while (!charStack.empty()) { postfix += charStack.top(); charStack.pop(); } return postfix; }// end of ConvertInfixToPostfix bool IsMathOperator(char token) {// this function checks if operand is a math operator switch (tolower(token)) { case '+': case '-': case '*': case '/': case '%': case '^': case '$': case 'c': case 's': case 't': return true; break; default: return false; break; } }// end of IsMathOperator int OrderOfOperations(char token) {// this function returns the priority of each math operator int priority = 0; switch (tolower(token)) { case 'c': case 's': case 't': priority = 5; break; case '^': case '$': priority = 4; break; case '*': case '/': case '%': priority = 3; break; case '-': priority = 2; break; case '+': priority = 1; break; } return priority; }// end of OrderOfOperations vector<string> Lexer(string postfix) {// this function parses a postfix string using an FSM to generate // each individual token in the expression vector<string> tokens; char currentChar = ' '; int col = REJECT; int currentState = REJECT; string currentToken = ""; // use an FSM to parse multidigit and decimal numbers // also does error check for invalid input of decimals for (unsigned x = 0; x < postfix.length();) { currentChar = postfix[x]; // get the column number for the current character col = Get_FSM_Col(currentChar); // exit if the real number has multiple periods "." // in the expression (i.e: 19.3427.23) if ((currentState == REAL) && (col == REAL)) { cerr << "\nINVALID INPUT #2\n"; exit(1); } /* ======================================================== THIS IS WHERE WE CHECK THE FINITE STATE MACHINE TABLE USING THE "col" VARIABLE FROM ABOVE ^ ========================================================= */ // get the current state of our machine currentState = stateTable[currentState][col]; /* =================================================== THIS IS WHERE WE CHECK FOR A SUCCESSFUL PARSE - If the current state in our machine == REJECT (the starting state), then we have successfully parsed a token, which is returned to its caller - ELSE we continue trying to find a successful token =================================================== */ if (currentState == REJECT) { if (currentToken != " ") // we dont care about whitespace { tokens.push_back(currentToken); } currentToken = ""; } else { currentToken += currentChar; ++x; } } // this ensures the last token gets saved when // we reach the end of the postfix string buffer if (currentToken != " ") // we dont care about whitespace { tokens.push_back(currentToken); } return tokens; }// end of Lexer int Get_FSM_Col(char& currentChar) {// this function determines the state of the type of character being examined // check for whitespace if (isspace(currentChar)) { return SPACE; } // check for integer numbers else if (isdigit(currentChar)) { return INTEGER; } // check for real numbers else if (currentChar == '.') { return REAL; } // check for negative numbers else if (currentChar == '~') { currentChar = '-'; return NEGATIVE; } // check for math operators else if (IsMathOperator(currentChar)) { return OPERATOR; } return UNKNOWN; }// end of Get_FSM_Col double EvaluatePostfix(const vector<string>& postfix) {// this function evaluates a postfix expression // declare function variables double op1 = 0; double op2 = 0; double answer = 0; stack<double> doubleStack; cout << "\nCalculations:\n"; // loop thru array until there is no more data for (unsigned x = 0; x < postfix.size(); ++x) { // push numbers onto the stack if ((isdigit(postfix[x][0])) || (postfix[x][0] == '.')) { doubleStack.push(atof(postfix[x].c_str())); } // push negative numbers onto the stack else if ((postfix[x].length() > 1) && ((postfix[x][0] == '-') && (isdigit(postfix[x][1]) || (postfix[x][1] == '.')))) { doubleStack.push(atof(postfix[x].c_str())); } // if expression is a math operator, pop numbers from stack // & send the popped numbers to the 'Calculate' function else if (IsMathOperator(postfix[x][0]) && (!doubleStack.empty())) { char token = tolower(postfix[x][0]); // if expression is square root, sin, cos, // or tan operation only pop stack once if (token == '$' || token == 's' || token == 'c' || token == 't') { op2 = 0; op1 = doubleStack.top(); doubleStack.pop(); answer = Calculate(token, op1, op2); doubleStack.push(answer); } else if (doubleStack.size() > 1) { op2 = doubleStack.top(); doubleStack.pop(); op1 = doubleStack.top(); doubleStack.pop(); answer = Calculate(token, op1, op2); doubleStack.push(answer); } } else // this should never execute, & if it does, something went really wrong { cout << "\nINVALID INPUT #3\n"; exit(1); } } // pop the final answer from the stack, and return to main if (!doubleStack.empty()) { answer = doubleStack.top(); } return answer; }// end of EvaluatePostfix double Calculate(char token, double op1, double op2) {// this function carries out the actual math process double ans = 0; switch (tolower(token)) { case '+': cout << op1 << token << op2 << " = "; ans = op1 + op2; break; case '-': cout << op1 << token << op2 << " = "; ans = op1 - op2; break; case '*': cout << op1 << token << op2 << " = "; ans = op1 * op2; break; case '/': cout << op1 << token << op2 << " = "; ans = op1 / op2; break; case '%': cout << op1 << token << op2 << " = "; ans = ((int)op1 % (int)op2) + modf(op1, &op2); break; case '^': cout << op1 << token << op2 << " = "; ans = pow(op1, op2); break; case '$': cout << char(251) << op1 << " = "; ans = sqrt(op1); break; case 'c': cout << "cos(" << op1 << ") = "; ans = cos(op1); break; case 's': cout << "sin(" << op1 << ") = "; ans = sin(op1); break; case 't': cout << "tan(" << op1 << ") = "; ans = tan(op1); break; default: ans = 0; break; } cout << ans << endl; return ans; }// http://programmingnotes.org/ |
QUICK NOTES:
The highlighted lines are sections of interest to look out for.
The code is heavily commented, so no further insight is necessary. If you have any questions, feel free to leave a comment below.
The following is sample output.
====== RUN 1 ======
==== Infix To Postfix Conversion & Evaluation ====Math Operators:
+ || Addition
- || Subtraction
* || Multiplication
/ || Division
% || Modulus
^ || Power
$ || Square Root
s || Sine
c || Cosine
t || Tangent
~ || Negative NumberSample Infix Equation: ((s(~4^5)*1.4)/($(23+2)-~2.8))*(c(1%2)/(7.28*.1987)^(t23))
Please enter an Infix expression: 12/3*9
The Infix expression = 12/3*9
The Postfix expression = 12 3 /9*Calculations:
12/3 = 4
4*9 = 36Final answer = 36
====== RUN 2 ======
==== Infix To Postfix Conversion & Evaluation ====
Math Operators:
+ || Addition
- || Subtraction
* || Multiplication
/ || Division
% || Modulus
^ || Power
$ || Square Root
s || Sine
c || Cosine
t || Tangent
~ || Negative NumberSample Infix Equation: ((s(~4^5)*1.4)/($(23+2)-~2.8))*(c(1%2)/(7.28*.1987)^(t23))
Please enter an Infix expression: -150.89996 - 87.56643
The Infix expression = -150.89996 - 87.56643
The Postfix expression = ~150.89996 87.56643-Calculations:
-150.9-87.5664 = -238.466Final answer = -238.466
====== RUN 3 ======
==== Infix To Postfix Conversion & Evaluation ====
Math Operators:
+ || Addition
- || Subtraction
* || Multiplication
/ || Division
% || Modulus
^ || Power
$ || Square Root
s || Sine
c || Cosine
t || Tangent
~ || Negative NumberSample Infix Equation: ((s(~4^5)*1.4)/($(23+2)-~2.8))*(c(1%2)/(7.28*.1987)^(t23))
Please enter an Infix expression: ((s(~4^5)*1.4)/($(23+2)-~2.8))*(c(1%2)/(7.28*.1987)^(t23))
The Infix expression = ((s(-4^5)*1.4)/($(23+2)--2.8))*(c(1%2)/(7.28*.1987)^(t23))
The Postfix expression = ~4 5^ s1.4* 23 2+ $~2.8-/ 1 2% c7.28 .1987* 23t^/*Calculations:
-4^5 = -1024
sin(-1024) = 0.158533
0.158533*1.4 = 0.221947
23+2 = 25
√25 = 5
5--2.8 = 7.8
0.221947/7.8 = 0.0284547
1%2 = 1
cos(1) = 0.540302
7.28*0.1987 = 1.44654
tan(23) = 1.58815
1.44654^1.58815 = 1.79733
0.540302/1.79733 = 0.300614
0.0284547*0.300614 = 0.00855389Final answer = 0.00855389
====== RUN 4 ======
==== Infix To Postfix Conversion & Evaluation ====
Math Operators:
+ || Addition
- || Subtraction
* || Multiplication
/ || Division
% || Modulus
^ || Power
$ || Square Root
s || Sine
c || Cosine
t || Tangent
- || Negative Number
Sample Infix Equation: ((s(-4^5)*1.4)/($(23+2)--2.8))*(c(1%2)/(7.28*.1987)^(t23))Please enter an Infix expression: (1987 + 1991) * -1
The Infix expression = (1987 + 1991) * -1
The Postfix expression = 1987 1991+ ~1*Calculations:
1987+1991 = 3978
3978*-1 = -3978Final answer = -3978
C++ || Snippet – Custom Template Linked List Sample Code
This page will consist of sample code for a singly linked list, which is loosely based on the built in C++ “List” library. Provided in the linked list class are the following functions:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 |
* PushFront - Adds new item to the front of the list (LIFO) * PushBack - Adds new item to the back of the list (FIFO) * PopFront - Returns & removes first item from the list * PopBack - Returns & removes last item from the list * Front - Returns (but does not delete) the first item from the list * Back - Returns (but does not delete) the last item from the list * Delete - Searches and deletes the requested item * Display - Display all the current contents in the list * Replace - Replaces existing item from the list with a new item If existing item cannot be found, the new item is added to the back of the list * InsertBefore - Inserts new item before the existing item. If existing item cannot be found, the new item is added to the back of the list * InsertAfter - Inserts new item after the existing item. If existing item cannot be found, the new item is added to the back of the list * InsertInOrder - Inserts new item in numerical order, from lowest to highest * Size - Return the current size of the list * MakeEmpty - Initializes the list to an empty state |
From the following, the functions of interest to look out for are the “Delete, Display, Replace, InsertBefore, InsertAfter, and InsertInOrder” functions as they are typically used as programming assignments in many C++ Data structures courses to further demonstrate how linked lists operate.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444 445 446 447 448 449 450 451 452 |
// ============================================================================ // Author: Kenneth Perkins // Date: Jul 26, 2012 // Taken From: http://programmingnotes.org/ // File: LinkedList.h // Description: This is a class which implements various functions which // demonstrates the use of a Linked List. // ============================================================================ #include <iostream> template <class ItemType> class LinkedList { public: LinkedList(); /* Function: Constructor initializes list Precondition: None Postcondition: Defines private variables */ bool IsEmpty(); /* Function: Determines whether queue is empty Precondition: List has been created Postcondition: The function = true if the list is empty and the function = false if list is not empty */ void PushFront(ItemType item); /* Function: Adds new item to the front of the list (LIFO) Precondition: List has been created and is not full Postcondition: Item is in the list */ void PushBack(ItemType item); /* Function: Adds new item to the back of the list (FIFO) Precondition: List has been created and is not full Postcondition: Item is in the list */ ItemType PopFront(); /* Function: Returns & removes first item from the last Precondition: List has been initialized Postcondition: The first item in the list is removed */ ItemType PopBack(); /* Function: Returns & removes last item from the list Precondition: List has been initialized Postcondition: The last item in the list is removed */ ItemType Front(); /* Function: Returns (but does not delete) the first item from the list Precondition: List has been initialized Postcondition: The first item in the list is removed */ ItemType Back(); /* Function: Returns (but does not delete) the last item from the list Precondition: List has been initialized Postcondition: The last item in the list is removed */ void Delete(ItemType item); /* Function: Searches and deletes the requested item Precondition: List has been created and is not empty Postcondition: Item removed from the list */ void Display(); /* Function: Display all the current contents in the list Precondition: List has been created and is not empty Postcondition: List is displayed to the screen */ void Replace(ItemType initial, ItemType replace); /* Function: Replaces existing item from the list with a new item Precondition: List has been created and is not empty Postcondition: Initial item is replaced with the new one */ void InsertBefore(ItemType initial, ItemType newItem); /* Function: Inserts new item before the existing item Precondition: List has been created and is not empty Postcondition: New item is inserted before the existing item */ void InsertAfter(ItemType initial, ItemType newItem); /* Function: Inserts new item after the existing item Precondition: List has been created and is not empty Postcondition: New item is inserted after the existing item */ void InsertInOrder(ItemType item); /* Function: Inserts new item in numerical order, from lowest to highest Precondition: List has been created and is not empty Postcondition: The list is sorted in numerical order */ int Size(); /* Function: Return the current size of the list Precondition: List has been initialized Postcondition: The size of the list is returned */ void MakeEmpty(); /* Function: Initializes the list to an empty state Precondition: List has been created Postcondition: List no longer exists */ ~LinkedList(); /* Function: Deletes all the items in the list Precondition: List has been declared Postcondition: List no longer exists */ private: struct node { ItemType info; node* next; }; node* head; int size; }; //========================= Implementation ================================// template <class ItemType> LinkedList<ItemType>::LinkedList() { head = NULL; size = 0; }// end of LinkedList template <class ItemType> bool LinkedList<ItemType>::IsEmpty() { return (head==NULL); }// end of IsEmpty template <class ItemType> void LinkedList<ItemType>::PushFront(ItemType item) { // LIFO node* temp = new node; temp-> info = item; temp-> next = head; head = temp; ++size; }// end of PushFront template <class ItemType> void LinkedList<ItemType>::PushBack(ItemType item) { // FIFO node* temp = new node; temp->info = item; temp->next = NULL; if(IsEmpty()) { head=temp; } else { node* temp2 = head; while(temp2->next!=NULL) { temp2=temp2->next; } temp2->next=temp; } ++size; }// end of PushBack template <class ItemType> ItemType LinkedList<ItemType>::PopFront() { if(IsEmpty()) { std::cout<<"\nLIST EMPTY\n"; } else { ItemType item = head-> info; node* temp = head; head = head-> next; delete temp; --size; return item; } }// end of PopFront template <class ItemType> ItemType LinkedList<ItemType>::PopBack() { if(IsEmpty()) { std::cout<<"\nLIST EMPTY\n"; } else if(size == 1) { ItemType item = PopFront(); return item; } else { node* temp = head; ItemType item; while(temp->next != NULL) { if(temp->next->next==NULL) { node* temp2=temp->next; temp->next=temp->next->next; item = temp2-> info; delete temp2; break; } temp=temp->next; } --size; return item; } }// end of PopBack template <class ItemType> ItemType LinkedList<ItemType>::Front() { if(IsEmpty()) { std::cout<<"\nLIST EMPTY\n"; } else { return head-> info; } }// end of Front template <class ItemType> ItemType LinkedList<ItemType>::Back() { if(IsEmpty()) { std::cout<<"\nLIST EMPTY\n"; } else { node* temp = head; while(temp->next != NULL) { temp = temp-> next; } ItemType item = temp-> info; return item; } }// end of Back template <class ItemType> void LinkedList<ItemType>::Delete(ItemType item) { node* temp=head; if(IsEmpty()) { return; } else if(temp->info==item) { head=head->next; delete temp; --size; } else { while(temp->next!=NULL) { if(temp->next->info==item) { node* temp2=temp->next; temp->next=temp->next->next; delete temp2; --size; break; } temp=temp->next; } } }// end of Delete template <class ItemType> void LinkedList<ItemType>::Display() { node* temp=head; while(temp!=NULL) { std::cout<<temp->info<<std::endl; temp=temp->next; } }// end of Display template <class ItemType> void LinkedList<ItemType>::Replace(ItemType initial, ItemType replace) { node* temp=head; if(IsEmpty()) { PushFront(replace); } else if(temp->info==initial) { temp->info=replace; } else { while(temp->next!=NULL) { if(temp->info==initial) { temp->info=replace; break; } temp=temp->next; } if(temp->next==NULL) { PushBack(replace); } } }// end of Replace template <class ItemType> void LinkedList<ItemType>::InsertBefore(ItemType initial, ItemType newItem) { node* temp=head; node* temp2=new node; temp2->info=initial; temp2->next=NULL; if(IsEmpty()) { PushFront(newItem); } else if(temp->info==initial) { temp->info=newItem; temp2->next=temp->next; temp->next=temp2; ++size; } else { while(temp->next!=NULL) { if(temp->info==initial) { temp->info=newItem; temp2->next=temp->next; temp->next=temp2; ++size; break; } temp=temp->next; } if(temp->next==NULL) { PushBack(newItem); } } }// end of InsertBefore template <class ItemType> void LinkedList<ItemType>::InsertAfter(ItemType initial, ItemType newItem) { node* temp=head; node* temp2=new node; temp2->info=newItem; temp2->next=NULL; if(IsEmpty()) { PushFront(newItem); } else if(temp->info==initial) { temp2->next=temp->next; temp->next=temp2; ++size; } else { while(temp->next!=NULL) { if(temp->info==initial) { temp2->next=temp->next; temp->next=temp2; ++size; break; } temp=temp->next; } if(temp->next==NULL) { PushBack(newItem); } } }// end of InsertAfter template <class ItemType> void LinkedList<ItemType>::InsertInOrder(ItemType item) { if(IsEmpty()) { PushFront(item); } else { node* temp=head; node* temp2=new node; if(item <=(temp->info)) { ItemType placeHolder=temp->info; temp2->info=placeHolder; temp->info=item; temp2->next=temp->next; temp->next=temp2; ++size; } else { while(temp->next!=NULL) { if(((temp->info) <= item) && (item <= (temp->next->info))) { temp2->info=item; temp2->next=temp->next; temp->next=temp2; ++size; return; } temp=temp->next; } if(temp->next==NULL) { PushBack(item); } } } }// end of InsertInOrder template <class ItemType> int LinkedList<ItemType>::Size() { if(IsEmpty()) { std::cout<<"\nLIST EMPTY\n"; } return size; }// end of Size template <class ItemType> void LinkedList<ItemType>::MakeEmpty() { if(!IsEmpty()) { std::cout << "\nDestroying nodes...\n"; while(!IsEmpty()) { node* temp = head; //std::cout << temp-> info << '\n'; head = head-> next; delete temp; } size = 0; } }// end of MakeEmpty template <class ItemType> LinkedList<ItemType>::~LinkedList() { MakeEmpty(); }// http://programmingnotes.org/ |
===== DEMONSTRATION HOW TO USE =====
Use of the above template class is the same as its STL counterpart. Here is a sample program demonstrating its use.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 |
#include <iostream> #include <string> #include "LinkedList.h" using namespace std; int main() { // declare variables, using a string as // the item type for the class. // NOTE: you can also use an int, float, double etc. // instead of a string LinkedList<string> list; // demontrate the "InOrder" function cout<<"** These are names of fruits sorted in order" <<" using the 'InsertInOrder()' function:\n\n"; list.InsertInOrder("Tomato"); list.InsertInOrder("Orange"); list.InsertInOrder("Apple"); list.InsertInOrder("Plum"); list.Display(); cout<<"\nThere is currently "<<list.Size()<<" items in the list\n\n"; // demonstrate the "Delete" function cout<<"\n** Here is the same list with the word 'Plum' deleted" << "\nusing the 'Delete()' function:\n\n"; list.Delete("Plum"); list.Display(); cout<<"\nThere is currently "<<list.Size()<<" items in the listnn"; // demonstrate the "InsertAfter" function cout<<"\n** Now the word 'Bike' will be added to the list," <<"\nright after the word 'Apple' using the " <<"'InsertAfter()' function:\n\n"; list.InsertAfter("Apple","Bike"); list.Display(); cout<<"\nThere is currently "<<list.Size()<<" items in the list\n\n"; // demonstrate the "InsertBefore" function cout<<"\n** Now the name 'Jessica' will be added to the list," <<"\nright before the word 'Orange' using the " <<"'InsertBefore()' function:\n\n"; list.InsertBefore("Orange","Jessica"); list.Display(); cout<<"\nThere is currently "<<list.Size()<<" items in the list\n\n"; // demonstrate the "Replace" function cout<<"\n** The word 'Orange' will now be replaced with the name," <<"\n'Kat' using the 'Replace()' function:\n\n"; list.Replace("Orange","Kat"); list.Display(); cout<<"\nThere is currently "<<list.Size()<<" items in the list\n\n"; }// http://programmingnotes.org/ |
Once compiled, you should get this as your output
** These are names of fruits sorted in order using the 'InsertInOrder()' function:Apple
Orange
Plum
TomatoThere is currently 4 items in the list
** Here is the same list with the word 'Plum' deleted
using the 'Delete()' function:Apple
Orange
TomatoThere is currently 3 items in the list
** Now the word 'Bike' will be added to the list,
right after the word 'Apple' using the 'InsertAfter()' function:Apple
Bike
Orange
TomatoThere is currently 4 items in the list
** Now the name 'Jessica' will be added to the list,
right before the word 'Orange' using the 'InsertBefore()' function:Apple
Bike
Jessica
Orange
TomatoThere is currently 5 items in the list
** The word 'Orange' will now be replaced with the name,
'Kat' using the 'Replace()' function:Apple
Bike
Jessica
Kat
TomatoThere is currently 5 items in the list
C++ || Snippet – Singly Linked List Custom Template Queue Sample Code
This page will consist of sample code for a custom singly linked list template queue. This implementation differs from the previously highlighted doubly linked list in that this version uses a single node to store its data rather than using two separate nodes (front and rear).
Looking for sample code for a stack? Click here.
REQUIRED KNOWLEDGE FOR THIS SNIPPET
Structs
Classes
Template Classes - What Are They?''
Queue - What is it?
FIFO - First In First Out
#include < queue>
Linked Lists - How To Use
This template class is a custom duplication of the Standard Template Library (STL) queue class. Whether you like building your own data structures, you simply do not like to use any inbuilt functions, opting to build everything yourself, or your homework requires you make your own data structure, this sample code is really useful. I feel its beneficial building functions such as this, that way you better understand the behind the scene processes.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 |
// ============================================================================ // Author: K Perkins // Date: Jul 14, 2012 // Taken From: http://programmingnotes.org/ // File: SingleQueue.h // Description: This is a class which implements various functions // demonstrating the use of a queue. // ============================================================================ #include <iostream> template <class ItemType> class SingleQueue { public: SingleQueue(); /* Function: Constructor initializes queue Precondition: None Postcondition: Defines private variables */ bool IsEmpty(); /* Function: Determines whether queue is empty Precondition: Queue has been created Postcondition: The function = true if the queue is empty and the function = false if queue is not empty */ bool IsFull(); /* Function: Determines whether queue is full Precondition: Queue has been created Postcondition: The function = true if the queue is full and the function = false if queue is not full */ void EnQueue(ItemType item); /* Function: Adds new item to the back of the queue Precondition: Queue has been created and is not full Postcondition: Item is in the queue */ ItemType DeQueue(); /* Function: Returns and then deletes the first item in the queue Precondition: Queue has been created and is not empty Postcondition: The first item in the queue has been removed and the queue order is maintained */ ItemType Front(); /* Function: Returns (but does not delete) the first item in the queue Precondition: Queue has been created and is not empty Postcondition: The first item in the queue has been returned and the queue order is maintained */ ItemType Rear(); /* Function: Returns (but does not delete) the last item in the queue Precondition: Queue has been created and is not empty Postcondition: The last item in the queue has been returned and the queue order is maintained */ int Size(); /* Function: Return the current size of the queue Precondition: Queue has been initialized Postcondition: The size of the queue is returned */ void MakeEmpty(); /* Function: Initializes queue to an empty state Precondition: Queue has been created Postcondition: Queue no longer exists */ ~SingleQueue(); /* Function: Removes the queue Precondition: Queue has been declared Postcondition: Queue no longer exists */ private: struct NodeType { ItemType currentItem; NodeType* next; }; NodeType* head; // front of queue int size; }; //========================= Implementation ================================// template<class ItemType> SingleQueue<ItemType>::SingleQueue() { head = NULL; size = 0; }/* end of SingleQueue */ template<class ItemType> bool SingleQueue<ItemType>::IsEmpty() { return (head == NULL); }/* end of IsEmpty */ template<class ItemType> bool SingleQueue<ItemType>::IsFull() { try { NodeType* location = new NodeType; delete location; return false; } catch(std::bad_alloc&) { return true; } }/* end of IsFull */ template<class ItemType> void SingleQueue<ItemType>::EnQueue(ItemType newItem) { if(IsFull()) { std::cout<<"nQUEUE FULLn"; } else { NodeType* newNode = new NodeType; // adds new node newNode-> currentItem = newItem; newNode-> next = NULL; if(IsEmpty()) { head = newNode; } else { NodeType* tempPtr = head; while(tempPtr-> next != NULL) { tempPtr = tempPtr-> next; } tempPtr-> next = newNode; } ++size; } }/* end of EnQueue */ template<class ItemType> ItemType SingleQueue<ItemType>::DeQueue() { if(IsEmpty()) { std::cout<<"nQUEUE EMPTYn"; } else { NodeType* tempPtr = head; // temporary pointer ItemType item = head-> currentItem; head = head-> next; delete tempPtr; --size; return item; } }/* end of DeQueue */ template<class ItemType> ItemType SingleQueue<ItemType>::Front() { if(IsEmpty()) { std::cout<<"nQUEUE EMPTYn"; } else { ItemType item = head-> currentItem; return item; } }/* end of Front */ template<class ItemType> ItemType SingleQueue<ItemType>::Rear() { if(IsEmpty()) { std::cout<<"nQUEUE EMPTYn"; } else { NodeType* tempPtr = head; // temporary pointer while(tempPtr->next != NULL) { tempPtr = tempPtr-> next; } ItemType item = tempPtr-> currentItem; return item; } }/* end of Rear */ template<class ItemType> int SingleQueue<ItemType>::Size() { if(IsEmpty()) { std::cout<<"nQUEUE EMPTYn"; } return size; }/* end of Size */ template<class ItemType> void SingleQueue<ItemType>::MakeEmpty() { if(!IsEmpty()) { std::cout << "Destroying nodes ...n"; while(!IsEmpty()) { NodeType* tempPtr = head; //std::cout << tempPtr-> currentItem << 'n'; head = head-> next; delete tempPtr; } size = 0; } }/* end of MakeEmpty */ template<class ItemType> SingleQueue<ItemType>::~SingleQueue() { MakeEmpty(); }// http://programmingnotes.org/ |
QUICK NOTES:
The highlighted lines are sections of interest to look out for.
The code is heavily commented, so no further insight is necessary. If you have any questions, feel free to leave a comment below.
===== DEMONSTRATION HOW TO USE =====
Use of the above template class is the same as its STL counterpart. Here is a sample program demonstrating its use.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 |
#include <iostream> #include "SingleQueue.h" using namespace std; int main() { // declare variables SingleQueue<char> charQueue; SingleQueue<int> intQueue; SingleQueue<double> doubleQueue; // ------ Char Example ------// char charArry[]="My Programming Notes Is A Big Help!"; int counter=0; while(charArry[counter]!='\0') { charQueue.EnQueue(charArry[counter]); ++counter; } cout<<"charQueue has "<<charQueue.Size()<<" items in it " <<"and contains the text:n"; while(!charQueue.IsEmpty()) { cout<<charQueue.DeQueue(); } cout<<endl; // ------ Int Example ------// int intArry[]={1,22,309,461,-92,66,7,8,1987,9,27,12}; counter=0; while(counter < sizeof(intArry)/sizeof(intArry[0])) { intQueue.EnQueue(intArry[counter]); ++counter; } cout<<"nintQueue has "<<intQueue.Size()<<" items in it.n" <<"The sum of the numbers in the queue is: "; counter=0; while(!intQueue.IsEmpty()) { counter-=intQueue.DeQueue(); } cout<<counter<<endl; // ------ Double Example ------// double doubleArry[]={31.62,2.8,43.9,4.4,19.87,6.23,7.787,68.99,9.6,3.540,12.04}; double sum=0; counter=0; while(counter < sizeof(doubleArry)/sizeof(doubleArry[0])) { doubleQueue.EnQueue(doubleArry[counter]); ++counter; } cout<<"ndoubleQueue has "<<doubleQueue.Size()<<" items in it.n" <<"The sum of the numbers in the queue is: "; while(!doubleQueue.IsEmpty()) { sum+=doubleQueue.DeQueue(); } cout<<sum<<endl; return 0; }// http://programmingnotes.org/ |
Once compiled, you should get this as your output
charQueue has 35 items in it and contains the text:
My Programming Notes Is A Big Help!intQueue has 12 items in it.
The sum of the numbers in the queue is: -2817doubleQueue has 11 items in it.
The sum of the numbers in the queue is: 210.777
Press any key to continue . . .
C++ || Snippet – Doubly Linked List Custom Template Queue Sample Code
This page will consist of sample code for a custom doubly linked list template queue. This implementation is considered a doubly linked list because it uses two nodes to store data in the queue – a ‘front’ and a ‘rear’ node. This is not a circular linked list, nor does it link forwards and/or backwards.
Looking for sample code for a stack? Click here.
REQUIRED KNOWLEDGE FOR THIS SNIPPET
Structs
Classes
Template Classes - What Are They?
Queue - What is it?
FIFO - First In First Out
#include < queue>
Linked Lists - How To Use
This template class is a custom duplication of the Standard Template Library (STL) queue class. Whether you like building your own data structures, you simply do not like to use any inbuilt functions, opting to build everything yourself, or your homework requires you make your own data structure, this sample code is really useful. I feel its beneficial building functions such as this, that way you better understand the behind the scene processes.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 |
// ============================================================================ // Author: K Perkins // Date: May 20, 2012 // Taken From: http://programmingnotes.org/ // File: DoubleQueue.h // Description: This is a class which implements various functions // demonstrating the use of a queue. // ============================================================================ #include <iostream> template <class ItemType> class DoubleQueue { public: DoubleQueue(); /* Function: Constructor initializes queue Precondition: None Postcondition: Defines private variables */ bool IsEmpty(); /* Function: Determines whether queue is empty Precondition: Queue has been created Postcondition: The function = true if the queue is empty and the function = false if queue is not empty */ bool IsFull(); /* Function: Determines whether queue is full Precondition: Queue has been created Postcondition: The function = true if the queue is full and the function = false if queue is not full */ void EnQueue(ItemType item); /* Function: Adds new item to the back of the queue Precondition: Queue has been created and is not full Postcondition: Item is in the queue */ ItemType DeQueue(); /* Function: Returns and then deletes the first item in the queue Precondition: Queue has been created and is not empty Postcondition: The first item in the queue has been removed and the queue order is maintained */ ItemType Front(); /* Function: Returns (but does not delete) the first item in the queue Precondition: Queue has been created and is not empty Postcondition: The first item in the queue has been returned and the queue order is maintained */ ItemType Rear(); /* Function: Returns (but does not delete) the last item in the queue Precondition: Queue has been created and is not empty Postcondition: The last item in the queue has been returned and the queue order is maintained */ int Size(); /* Function: Return the current size of the queue Precondition: Queue has been initialized Postcondition: The size of the queue is returned */ void MakeEmpty(); /* Function: Initializes queue to an empty state Precondition: Queue has been created Postcondition: Queue no longer exists */ ~DoubleQueue(); /* Function: Removes the queue Precondition: Queue has been declared Postcondition: Queue no longer exists */ private: struct NodeType { ItemType currentItem; NodeType* next; }; NodeType* front; // front of queue NodeType* rear; // back of queue int size; }; //========================= Implementation ================================// template<class ItemType> DoubleQueue<ItemType>::DoubleQueue() { front = NULL; rear = NULL; size = 0; }/* end of DoubleQueue */ template<class ItemType> bool DoubleQueue<ItemType>::IsEmpty() { return (front == NULL); }/* end of IsEmpty */ template<class ItemType> bool DoubleQueue<ItemType>::IsFull() { try { NodeType* location = new NodeType; delete location; return false; } catch(std::bad_alloc&) { return true; } }/* end of IsFull */ template<class ItemType> void DoubleQueue<ItemType>::EnQueue(ItemType newItem) { if(IsFull()) { std::cout<<"nQUEUE FULLn"; } else { NodeType* newNode = new NodeType; // adds new node newNode-> currentItem = newItem; newNode-> next = NULL; if(rear == NULL) { front = newNode; } else { rear-> next = newNode; } rear = newNode; ++size; } }/* end of EnQueue */ template<class ItemType> ItemType DoubleQueue<ItemType>::DeQueue() { if(IsEmpty()) { std::cout<<"nQUEUE EMPTYn"; } else { NodeType* tempPtr = front; // temporary pointer ItemType item = front-> currentItem; front = front-> next; if(front == NULL) { rear = NULL; } delete tempPtr; --size; return item; } }/* end of DeQueue */ template<class ItemType> ItemType DoubleQueue<ItemType>::Front() { if(IsEmpty()) { std::cout<<"nQUEUE EMPTYn"; } else { return front-> currentItem; } }/* end of Front */ template<class ItemType> ItemType DoubleQueue<ItemType>::Rear() { if(IsEmpty()) { std::cout<<"nQUEUE EMPTYn"; } else { return rear-> currentItem; } }/* end of Rear */ template<class ItemType> int DoubleQueue<ItemType>::Size() { if(IsEmpty()) { std::cout<<"nQUEUE EMPTYn"; } return size; }/* end of Size */ template<class ItemType> void DoubleQueue<ItemType>::MakeEmpty() { if(!IsEmpty()) { std::cout << "Destroying nodes ...n"; while(!IsEmpty()) { NodeType* tempPtr = front; //std::cout << tempPtr-> currentItem << 'n'; front = front-> next; delete tempPtr; } rear = NULL; size = 0; } }/* end of MakeEmpty */ template<class ItemType> DoubleQueue<ItemType>::~DoubleQueue() { MakeEmpty(); }// http://programmingnotes.org/ |
QUICK NOTES:
The highlighted lines are sections of interest to look out for.
The code is heavily commented, so no further insight is necessary. If you have any questions, feel free to leave a comment below.
===== DEMONSTRATION HOW TO USE =====
Use of the above template class is the same as its STL counterpart. Here is a sample program demonstrating its use.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 |
#include <iostream> #include "DoubleQueue.h" using namespace std; int main() { // declare variables DoubleQueue<char> charQueue; DoubleQueue<int> intQueue; DoubleQueue<float> floatQueue; // ------ Char Example ------// char charArry[]="My Programming Notes Helped Me Succeed!"; int counter=0; while(charArry[counter]!='\0') { charQueue.EnQueue(charArry[counter]); ++counter; } cout<<"charQueue has "<<charQueue.Size()<<" items in it " <<"and contains the text:n"; while(!charQueue.IsEmpty()) { cout<<charQueue.DeQueue(); } cout<<endl; // ------ Int Example ------// int intArry[]={1,22,3,46,5,66,7,8,1987}; counter=0; while(counter<9) { intQueue.EnQueue(intArry[counter]); ++counter; } cout<<"nintQueue has "<<intQueue.Size()<<" items in it.n" <<"The sum of the numbers in the queue is: "; counter=0; while(!intQueue.IsEmpty()) { counter-=intQueue.DeQueue(); } cout<<counter<<endl; // ------ Float Example ------// float floatArry[]={41.6,2.8,43.9,4.4,19.87,6.23,7.787,68.99,9.6,81.540}; float sum=0; counter=0; while(counter<10) { floatQueue.EnQueue(floatArry[counter]); ++counter; } cout<<"nfloatQueue has "<<floatQueue.Size()<<" items in it.n" <<"The sum of the numbers in the queue is: "; while(!floatQueue.IsEmpty()) { sum-=floatQueue.DeQueue(); } cout<<sum<<endl; return 0; }// http://programmingnotes.org/ |
Once compiled, you should get this as your output
charQueue has 39 items in it and contains the text:
My Programming Notes Helped Me Succeed!intQueue has 9 items in it.
The sum of the numbers in the queue is: -2145floatQueue has 10 items in it.
The sum of the numbers in the queue is: -286.717
C++ || Snippet – Linked List Custom Template Stack Sample Code
This page will consist of sample code for a custom linked list template stack. This page differs from the previously highlighted array based template stack in that this version uses a singly linked list to store data rather than using an array.
Looking for sample code for a queue? Click here.
REQUIRED KNOWLEDGE FOR THIS SNIPPET
Structs
Classes
Template Classes - What Are They?
Stacks
LIFO - What Is It?
#include < stack>
Linked Lists - How To Use
This template class is a custom duplication of the Standard Template Library (STL) stack class. Whether you like building your own data structures, you simply do not like to use any inbuilt functions, opting to build everything yourself, or your homework requires you make your own data structure, this sample code is really useful. I feel its beneficial building functions such as this, that way you better understand the behind the scene processes.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 |
// ============================================================================ // Author: K Perkins // Date: Apr 9, 2012 // Taken From: http://programmingnotes.org/ // File: ClassStackListType.h // Description: This is a class which implements various functions // demonstrating the use of a stack. // ============================================================================ #include <iostream> template <class ItemType> class StackListType { public: StackListType(); /* Function: constructor initializes class variables Precondition: none Postcondition: defines private variables */ bool IsEmpty(); /* Function: Determines whether the stack is empty Precondition: Stack has been initialized Postcondition: Function value = (stack is empty) */ bool IsFull(); /* Function: Determines whether the stack is full Precondition: Stack has been initialized Postcondition: Function value = (stack is full) */ int Size(); /* Function: Return the current size of the stack Precondition: Stack has been initialized Postcondition: If (stack is full) exception FullStack is thrown else newItem is at the top of the stack */ void MakeEmpty(); /* Function: Empties the stack Precondition: Stack has been initialized Postcondition: Stack is empty */ void Push(ItemType newItem); /* Function: Adds newItem to the top of the stack Precondition: Stack has been initialized Postcondition: If (stack is full) exception FullStack is thrown else newItem is at the top of the stack */ ItemType Pop(); /* Function: Returns & then removes top item from the stack Precondition: Stack has been initialized Postcondition: If (stack is empty) exception EmptyStack is thrown else top element has been removed from the stack */ ItemType Top(); /* Function: Returns the top item from the stack Precondition: Stack has been initialized Postcondition: If (stack is empty) exception EmptyStack is thrown else top element has been removed from the stack */ ~StackListType(); /* Function: destructor deallocates class variables Precondition: none Postcondition: deallocates private variables */ private: struct NodeType { ItemType currentItem; // Variable which hold all the incoming currentItem NodeType* next; // Creates a pointer that points to the next node in the list. }; int size; // Indicates the size of the stack ItemType junk; NodeType* headPtr; // Creates a head pointer that will point to the begining of the list. }; //========================= Implementation ================================// template<class ItemType> StackListType<ItemType>::StackListType() { size = 0; headPtr = NULL; }// End of StackListType template<class ItemType> bool StackListType<ItemType>::IsEmpty() { return (headPtr == NULL); }// End of IsEmpty template<class ItemType> bool StackListType<ItemType>::IsFull() { try { NodeType* tempPtr = new NodeType; delete tempPtr; return false; } catch(std::bad_alloc&) { return true; } }// End of IsFull template<class ItemType> int StackListType<ItemType>::Size() { if(IsEmpty()) { std::cout<<"nSTACK EMPTYn"; } return size; }// End of Size template<class ItemType> void StackListType<ItemType>::MakeEmpty() { size = 0; if (!IsEmpty()) { std::cout << "Destroying nodes ...n"; while (!IsEmpty()) { NodeType* tempPtr = headPtr; //std::cout << tempPtr-> currentItem << 'n'; headPtr = headPtr-> next; delete tempPtr; } } }// End of MakeEmpty template<class ItemType> void StackListType<ItemType>::Push(ItemType newItem) { if(IsFull()) { std::cout<<"nSTACK FULLn"; return; } NodeType* tempPtr = new NodeType; tempPtr-> currentItem = newItem; tempPtr-> next = headPtr; headPtr = tempPtr; ++size; }// End of Push template<class ItemType> ItemType StackListType<ItemType>::Pop() { if(IsEmpty()) { std::cout<<"nSTACK EMPTYn"; return junk; } else { ItemType data = headPtr-> currentItem; NodeType* tempPtr = headPtr; headPtr = headPtr-> next; delete tempPtr; --size; return data; } }// End of Pop template<class ItemType> ItemType StackListType<ItemType>::Top() { if(IsEmpty()) { std::cout<<"nSTACK EMPTYn"; return junk; } else { return headPtr-> currentItem; } }// End of Top template<class ItemType> StackListType<ItemType>::~StackListType() { MakeEmpty(); }// http://programmingnotes.org/ |
QUICK NOTES:
The highlighted lines are sections of interest to look out for.
The code is heavily commented, so no further insight is necessary. If you have any questions, feel free to leave a comment below.
===== DEMONSTRATION HOW TO USE =====
Use of the above template class is the same as its STL counterpart. Here is a sample program demonstrating its use.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 |
#include <iostream> #include "ClassStackListType.h" using namespace std; int main() { // declare variables StackListType<char> charStack; StackListType<int> intStack; StackListType<float> floatStack; // ------ Char Example ------// char charArry[]="My Programming Notes Is Awesome"; int counter=0; while(charArry[counter]!='\0') { charStack.Push(charArry[counter]); ++counter; } cout<<"charStack has "<<charStack.Size()<<" items in itn" <<"and contains the text ""<<charArry<<"" backwards:n"; while(!charStack.IsEmpty()) { cout<<charStack.Pop(); } cout<<endl; // ------ Int Example ------// int intArry[]={1,22,3,46,5,66,7,8,1987}; counter=0; while(counter<9) { intStack.Push(intArry[counter]); ++counter; } cout<<"nintStack has "<<intStack.Size()<<" items in it.n" <<"The sum of the numbers in the stack is: "; counter=0; while(!intStack.IsEmpty()) { counter+=intStack.Pop(); } cout<<counter<<endl; // ------ Float Example ------// float floatArry[]={41.6,2.8,43.9,4.4,19.87,6.23,7.787,68.99,9.6,81.540}; float sum=0; counter=0; while(counter<10) { floatStack.Push(floatArry[counter]); ++counter; } cout<<"nfloatStack has "<<floatStack.Size()<<" items in it.n" <<"The sum of the numbers in the stack is: "; while(!floatStack.IsEmpty()) { sum+=floatStack.Pop(); } cout<<sum<<endl; }// http://programmingnotes.org/ |
Once compiled, you should get this as your output
charStack has 31 items in it
and contains the text "My Programming Notes Is Awesome" backwards:
emosewA sI setoN gnimmargorP yMintStack has 9 items in it.
The sum of the numbers in the stack is: 2145floatStack has 10 items in it.
The sum of the numbers in the stack is: 286.717
C++ || Stack Based Postfix Evaluation (Single Digit)
This page consists of another homework assignment which was presented in a C++ Data Structures course. While the previously discussed program dealt with converting Infix expressions to Postfix, this program will demonstrate exactly how to evaluate them.
NOTE: Want to convert & evaluate multi digit, decimal, and negative numbers? Click here!
REQUIRED KNOWLEDGE FOR THIS PROGRAM
What Is Postfix?
How To Convert Infix To Postfix Equations
Stack Data Structure
Cin.getline
How To Evaluate Postfix Expressions
The Order Of Operations
#include "ClassStackType.h"
The title of this page is called – “Stack Based Postfix Evaluation (Single Digit).” Why “single digit?” The program demonstrated on this page has the ability to evaluate a postfix equation, but it only has the ability to evaluate single digit values. What do I mean by that? Consider the infix equation: 5+2. When that expression is converted to postfix, it will come out to be: 52+, and the answer will be 7 (5+2=7). But what if we have an equation like 12+2? When that expression is converted to postfix, it will come out to be: 122+. The postfix conversion is correct, but when you try to evaluate the expression, we do not know if the math operation should be 12+2 or 1+22, it can be read either way.
Question: So why is this program being displayed if it only works for single digits?
Answer: Because it demonstrates the process of evaluating postfix equations very well.
Want to convert & evaluate multi digit, decimal, and negative numbers? Click here!
Before we get into things, here is a helpful algorithm for evaluating a postfix expression in pseudo code:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
// An algorithm for postfix evaluation. // For example, (1 + 2) / (5 + 6) translates to 1 2 + 5 6 + / // which equals the result of 0.272727 // Valid operands are single digits: 0-9 // Valid operators are: +, -, *, /, ^, $ // Highest precedence: ^, $ // Lowest precedence: +,- // the operators ')' and '('never goes on stack. double EvaluatePostfix(string postfix) { while there is input { if input is a number push current number on stack else if input is a math operator and stack is not empty set operand2 to the top of the operand stack pop the stack set operand1 to the top of the operand stack pop the stack apply the math operation that represents to operand1 and operand2 push the result onto the stack else error } // When the loop is finished, the operand stack will contain one item, // the result of evaluating the expression pop the stack return the answer to the caller }// http://programmingnotes.org/ |
Once you understand the process of converting from infix to postfix, adding the ability to evaluate multiple digits within this program should be doable.
======= POSTFIX EVALUATION =======
This program uses a custom template.h class. To obtain the code for that class, click here.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 |
// ============================================================================ // Author: Kenneth Perkins // Date: Mar 24, 2012 // Taken From: http://programmingnotes.org/ // File: PostfixEvaluation.cpp // Description: Demonstrate the use of a stack based postfix evaluation. // ============================================================================ #include <iostream> #include <cstdlib> #include <cmath> #include "ClassStackType.h" using namespace std; // function prototypes void DisplayDirections(); double EvaluatePostfix(char* postfix); bool IsMathOperator(char token); double DoMath(double op1, double op2, char token); int main() { // declare variables char expression[50]; // array holding the postfix data double answer = 0; // display directions to user DisplayDirections(); // get data from user cout<<"\nPlease enter a postfix expression: "; cin.getline(expression, sizeof(expression)); cout <<"\nThe postfix expression = "<<expression<<endl; cout<<"\nCalculations:\n"; answer = EvaluatePostfix(expression); cout<<"\nFinal answer = "<<answer<<endl; return 0; }// end of main void DisplayDirections() { cout << "\n==== Postfix Evaluation ====\n" <<"\nMath Operators:\n" <<"+ || Addition\n" <<"- || Subtraction\n" <<"* || Multiplication\n" <<"/ || Division\n" <<"% || Modulus\n" <<"^ || Power\n" <<"$ || Square Rootn\n" <<"Sample Postfix Equation: 45^14*232+$2-/12%24*/* \n"; }// end of DisplayDirections double EvaluatePostfix(char* postfix) { // declare function variables int counter = 0; int currentNum = 0; char token = 'a'; double op1 = 0; double op2 = 0; double answer = 0; StackType<double> doubleStack; // loop thru array until there is no more data while(postfix[counter] != '\0') { // push numbers onto the stack if(isdigit(postfix[counter])) { currentNum = postfix[counter] - '0'; doubleStack.Push(currentNum); } else if(isspace(postfix[counter])) { // DO NOTHING } // if expression is a math operator, pop numbers from stack // & send the popped numbers to the 'DoMath' function else if((IsMathOperator(postfix[counter])) && (!doubleStack.IsEmpty())) { token = postfix[counter]; // if expression is square root operation // only pop stack once if(token == '$') { op2 = 0; op1 = doubleStack.Top(); doubleStack.Pop(); answer = DoMath(op1,op2,token); doubleStack.Push(answer); } else { op2 = doubleStack.Top(); doubleStack.Pop(); op1 = doubleStack.Top(); doubleStack.Pop(); answer = DoMath(op1,op2,token); doubleStack.Push(answer); } } else { cout<<"\nINVALID INPUT\n"; exit(1); } ++counter; } // pop the final answer from the stack, and return to main answer = doubleStack.Top(); doubleStack.Pop(); return answer; }// end of EvaluatePostfix bool IsMathOperator(char token) {// this function checks if operand is a math operator switch(token) { case '+': return true; break; case '-': return true; break; case '*': return true; break; case '/': return true; break; case '%': return true; break; case '^': return true; break; case '$': return true; break; default: return false; break; } }// end of IsMathOperator double DoMath(double op1, double op2, char token) {// this function carries out the actual math process double ans = 0; switch(token) { case '+': cout<<op1<<token<<op2<<" = "; ans = op1 + op2; break; case '-': cout<<op1<<token<<op2<<" = "; ans = op1 - op2; break; case '*': cout<<op1<<token<<op2<<" = "; ans = op1 * op2; break; case '/': cout<<op1<<token<<op2<<" = "; ans = op1 / op2; break; case '%': cout<<op1<<token<<op2<<" = "; ans = (int)op1 % (int)op2; break; case '^': cout<<op1<<token<<op2<<" = "; ans = pow(op1, op2); break; case '$': cout<<char(251)<<op1<<" = "; ans = sqrt(op1); break; default: ans = 0; break; } cout<<ans<<endl; return ans; }// http://programmingnotes.org/ |
QUICK NOTES:
The highlighted lines are sections of interest to look out for.
Want to convert & evaluate multi digit, decimal, and negative numbers? Click here!
The code is heavily commented, so no further insight is necessary. If you have any questions, feel free to leave a comment below.
Once compiled, you should get this as your output
(Note: the code was compile three separate times to display different output)
====== RUN 1 ========== Postfix Evaluation ====
Math Operators:
+ || Addition
- || Subtraction
* || Multiplication
/ || Division
% || Modulus
^ || Power
$ || Square RootSample Postfix Equation: 45^14*232+$2-/12%24*/*
Please enter a postfix expression: 1 2 + 5 6 + /
The postfix expression = 1 2 + 5 6 + /Calculations:
1+2 = 3
5+6 = 11
3/11 = 0.272727
Final answer = 0.272727====== RUN 2 ======
==== Postfix Evaluation ====
Math Operators:
+ || Addition
- || Subtraction
* || Multiplication
/ || Division
% || Modulus
^ || Power
$ || Square RootSample Postfix Equation: 45^14*232+$2-/12%24*/*
Please enter a postfix expression: 35*76^+
The postfix expression = 35*76^+Calculations:
3*5 = 15
7^6 = 117649
15+117649 = 117664
Final answer = 117664====== RUN 3 ======
==== Postfix Evaluation ====
Math Operators:
+ || Addition
- || Subtraction
* || Multiplication
/ || Division
% || Modulus
^ || Power
$ || Square RootSample Postfix Equation: 45^14*232+$2-/12%24*/*
Please enter a postfix expression: 45^4*32+$2-/12%24*/*
The postfix expression = 45^4*32+$2-/12%24*/*Calculations:
4^5 = 1024
1024*4 = 4096
3+2 = 5
√5 = 2.23607
2.23607-2 = 0.236068
4096/0.236068 = 17350.9
1%2 = 1
2*4 = 8
1/8 = 0.125
17350.9*0.125 = 2168.87
Final answer = 2168.87
C++ || Stack Based Infix To Postfix Conversion (Single Digit)
This page consists of another homework assignment which was presented in a C++ Data Structures course. No matter which institution you attend, it seems every instructor assigns a program similar to this at one time or another.
Want to evaluate a postfix expression? Click here.
Want to convert & evaluate multi digit, decimal, and negative numbers? Click here!
REQUIRED KNOWLEDGE FOR THIS PROGRAM
What Is Infix?
What Is Postfix?
Stack Data Structure
Cin.getline
How To Convert To Postfix
The Order Of Operations
#include "ClassStackType.h"
The program demonstrated on this page has the ability to convert a normal infix equation to postfix equation, so for example, if the user enters the infix equation of (1*2)+3, the program will display the postfix result of 12*3+.
Before we get into things, here is a helpful algorithm for converting from infix to postfix in pseudo code:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 |
// An algorithm for infix to postfix expression conversion. // For example, a + b - c translates to a b + c - // a + b * c translates to a b c * + // (1 + 2) / (5 + 6) goes to 1 2 + 5 6 + / // Valid operands are single digits: 0-9, a-z, A-Z // Valid operators are: +, -, *, /, (, ), ^, $ // Highest precedence: ^, $ // Lowest precedence: +,- // ) never goes on stack. // ( has lowest precedence on the stack and highest precedence outside of stack. // Bottom of the stack has the lowest precedence than any operator. // Use a prec() function to compare the precedence of the operators based on the above rules. // Note there is little error checking in the algorithm! void ConvertInfixToPostfix(string infix) { while there is input { if input is a number or a letter place onto postfix string else if input is '(' // '(' has lowest precedence in the stack, highest outside push input on stack else if input is ')' while stack is not empty and top of stack is not '(' place item from top of stack onto postfix string pop stack if stack is not empty // pops '(' off the stack pop stack else error // no matching '(' else if input is a math operator if stack is empty push input on stack else if prec(top of stack) >= prec(current math operator) while stack is not empty and prec(top of stack) >= prec(current math operator) place item from top of stack onto postfix string pop stack push current math operator on stack else error } while stack is not empty { place item from top of stack onto postfix string pop stack } }// http://programmingnotes.org/ |
======= INFIX TO POSTFIX CONVERSION =======
This program uses a custom template.h class. To obtain the code for that class, click here.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 |
// ============================================================================ // Author: Kenneth Perkins // Date: Mar 23, 2012 // Taken From: http://programmingnotes.org/ // File: PostfixConversion.cpp // Description: Demonstrate the use of a stack based infix to // postfix conversion. // ============================================================================ #include <iostream> #include <cctype> #include <cstdlib> #include <cstring> #include "ClassStackType.h" using namespace std; // function prototypes void DisplayDirections(); void ConvertInfixToPostfix(char* infix); int OrderOfOperations(char token); bool IsMathOperator(char token); int main() { // declare variables char expression[50]; // array holding the infix data // display directions to user DisplayDirections(); // get data from user cout<<"\nPlease enter an infix expression: "; cin.getline(expression, sizeof(expression)); cout <<"\nThe Infix expression = "<<expression<<endl; ConvertInfixToPostfix(expression); cout<<"The Postfix expression = "<<expression<<endl; return 0; }// end of main void DisplayDirections() { cout << "\n==== Infix to Postfix Conversion ====\n" <<"\nMath Operators:\n" <<"+ || Addition\n" <<"- || Subtraction\n" <<"* || Multiplication\n" <<"/ || Division\n" <<"% || Modulus\n" <<"^ || Power\n" <<"$ || Square Root\n" <<"Sample Infix Equation: (((4^5)*14)/($(23+2)-2))*(1%2)/(2*4)\n"; }// end of DisplayDirections void ConvertInfixToPostfix(char* infix) { // declare function variables int infixCounter = 0; int postfixCounter = 0; char token = 'a'; char postfix[50]; StackType<char> charStack; // loop thru array until there is no more data while(infix[infixCounter] != '\0') { // push numbers/letters onto 'postfix' array if(isdigit(infix[infixCounter]) || isalpha(infix[infixCounter])) { postfix[postfixCounter] = infix[infixCounter]; ++postfixCounter; } else if(isspace(infix[infixCounter])) { // DO NOTHING } else if(IsMathOperator(infix[infixCounter])) { // if stack is empty, place first math operator onto stack token = infix[infixCounter]; if(charStack.IsEmpty()) { charStack.Push(token); } else { // get the current math operator from the top of the stack token = charStack.Top(); charStack.Pop(); // use the 'OrderOfOperations' function to check equality // of the math operators while(OrderOfOperations(token) >= OrderOfOperations(infix[infixCounter])) { // if stack is empty, do nothing if(charStack.IsEmpty()) { break; } // place the popped math operator from above ^ // onto the postfix array else { postfix[postfixCounter] = token; ++postfixCounter; // pop the next operator from the stack and // continue the process until complete token = charStack.Top(); charStack.Pop(); } } // push any remainding math operators onto the stack charStack.Push(token); charStack.Push(infix[infixCounter]); } } // push outer parentheses onto stack else if(infix[infixCounter] == '(') { charStack.Push(infix[infixCounter]); } else if(infix[infixCounter] == ')') { // pop the current math operator from the stack token = charStack.Top(); charStack.Pop(); while(token != '(' && !charStack.IsEmpty()) { // place the math operator onto the postfix array postfix[postfixCounter] = token; ++postfixCounter; // pop the next operator from the stack and // continue the process until complete token = charStack.Top(); charStack.Pop(); } } else { cout<<"\nINVALID INPUT\n"; exit(1); } ++infixCounter; } // place any remaining math operators from the stack onto // the postfix array while(!charStack.IsEmpty()) { postfix[postfixCounter] = charStack.Top(); ++postfixCounter; charStack.Pop(); } postfix[postfixCounter] = '\0'; // copy the data from the postfix array into the infix array // the data in the infix array gets sent back to main // since the array is passed by reference strcpy(infix,postfix); }// end of ConvertInfixToPostfix int OrderOfOperations(char token) {// this function checks priority of each math operator int priority = 0; if(token == '^'|| token == '$') { priority = 4; } else if(token == '*' || token == '/' || token == '%') { priority = 3; } else if(token == '-') { priority = 2; } else if(token == '+') { priority = 1; } return priority; }// end of OrderOfOperations bool IsMathOperator(char token) {// this function checks if operand is a math operator switch(token) { case '+': return true; break; case '-': return true; break; case '*': return true; break; case '/': return true; break; case '%': return true; break; case '^': return true; break; case '$': return true; break; default: return false; break; } }// http://programmingnotes.org/ |
QUICK NOTES:
The highlighted lines are sections of interest to look out for.
Want to convert & evaluate multi digit, decimal, and negative numbers? Click here!
The code is heavily commented, so no further insight is necessary. If you have any questions, feel free to leave a comment below.
Want to evaluate a postfix expression? Click here for sample code.
Once compiled, you should get this as your output
(Note: the code was compile three separate times to display different output)
====== RUN 1 ========== Infix to Postfix Conversion ====
Math Operators:
+ || Addition
- || Subtraction
* || Multiplication
/ || Division
% || Modulus
^ || Power
$ || Square RootSample Infix Equation: (((4^5)*14)/($(23+2)-2))*(1%2)/(2*4)
Please enter an infix expression: ((a+b)+c)/(d^e)
The Infix expression = ((a+b)+c)/(d^e)
The Postfix expression = ab+c+de^/====== RUN 2 ======
==== Infix to Postfix Conversion ====
Math Operators:
+ || Addition
- || Subtraction
* || Multiplication
/ || Division
% || Modulus
^ || Power
$ || Square RootSample Infix Equation: (((4^5)*14)/($(23+2)-2))*(1%2)/(2*4)
Please enter an infix expression: (3*5)+(7^6)
The Infix expression = (3*5)+(7^6)
The Postfix expression = 35*76^+====== RUN 3 ======
==== Infix to Postfix Conversion ====
Math Operators:
+ || Addition
- || Subtraction
* || Multiplication
/ || Division
% || Modulus
^ || Power
$ || Square RootSample Infix Equation: (((4^5)*14)/($(23+2)-2))*(1%2)/(2*4)
Please enter an infix expression: (((4^5)*14)/($(23+2)-2))*(1%2)/(2*4)
The Infix expression = (((4^5)*14)/($(23+2)-2))*(1%2)/(2*4)
The Postfix expression = 45^14*232+$2-/12%24*/*
C++ || Snippet – Array Based Custom Template Stack Sample Code
This page will consist of sample code for a custom array based template stack.
REQUIRED KNOWLEDGE FOR THIS SNIPPET
Classes
Template Classes - What Are They?
Stacks
LIFO - What Is It?
#include < stack>
This template class is a custom duplication of the Standard Template Library (STL) stack class. Whether you like building your own data structures, you simply do not like to use any inbuilt functions, opting to build everything yourself, or your homework requires you make your own data structure, this sample code is really useful. I feel its beneficial building functions such as this, that way you better understand the behind the scene processes.