## 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.

``` Multi Digit Infix To Postfix Conversion & Evaluation C++ // ============================================================================ // 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/ 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473 // ============================================================================//   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 prototypesvoid 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 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: 12/3*9 The Infix expression = 12/3*9 The Postfix expression = 12 3 /9* Calculations: 12/3 = 4 4*9 = 36 Final 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 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: -150.89996 - 87.56643 The Infix expression = -150.89996 - 87.56643 The Postfix expression = ~150.89996 87.56643- Calculations: -150.9-87.5664 = -238.466 Final 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 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: ((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.00855389 Final 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 = -3978 Final 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:

``` * 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 123456789101112131415161718192021222324252627282930 * 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.

``` #include 'LinkedList.h' C++ // ============================================================================ // 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/ 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452 // ============================================================================//    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.

``` How To Use #include 'LinkedList.h' C++ #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/ 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859 #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 Tomato There is currently 4 items in the list ** Here is the same list with the word 'Plum' deleted using the 'Delete()' function: Apple Orange Tomato There 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 Tomato There 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 Tomato There 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 Tomato ```

```There 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).

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.

``` #include 'SingleQueue.h' C++ // ============================================================================ // 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/ 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214 // ============================================================================//    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.

``` How To Use #include 'SingleQueue.h' C++ #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/ 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263 #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: -2817 ```

```doubleQueue 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.

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.

``` #include 'DoubleQueue.h' C++ // ============================================================================ // 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/ 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210 // ============================================================================//    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.

``` How To Use #include 'DoubleQueue.h' C++ #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/ 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263 #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: -2145 ```

```floatQueue 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.

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.

``` #include 'ClassStackListType.h' C++ // ============================================================================ // 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/ 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178 // ============================================================================//    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.

``` How To Use #include 'ClassStackListType.h' C++ #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/ 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960 #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 yM```

``` intStack has 9 items in it. The sum of the numbers in the stack is: 2145 ```

```floatStack 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:

``` // 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/ 1234567891011121314151617181920212223242526272829 // 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.

``` Postfix Evaluation (Single Digit) C++ // ============================================================================ // 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/ 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194 // ============================================================================//    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 prototypesvoid 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 Root Sample 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 Root Sample 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 Root Sample 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 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:

``` // 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/ 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647 // 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.

``` Infix To Postfix Conversion (Single Digit) C++ // ============================================================================ // 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/ 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216 // ============================================================================//    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 prototypesvoid 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.

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 Root Sample 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 Root Sample 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 Root Sample 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.

``` #include 'ClassStackType.h' C++ // ============================================================================ // Author: K Perkins // Date: Mar 22, 2012 // Taken From: http://programmingnotes.org/ // File: ClassStackType.h // Description: This is a class which implements various functions // demonstrating the use of a stack. // ============================================================================ #include <iostream> template <class ItemType> class StackType { public: StackType(); /* 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 */ ~StackType(); /* Function: destructor deallocates class variables Precondition: none Postcondition: deallocates private variables */ private: int top; // indicates which element is on top int MAX_ITEMS; // max number of items in the list ItemType stack[200]; // array holding the popped/pushed data }; //========================= Implementation ================================// template<class ItemType> StackType<ItemType>::StackType() { top = -1; MAX_ITEMS = 200; }// End of StackType template<class ItemType> bool StackType<ItemType>::IsEmpty() { return (top == -1); }// End of IsEmpty template<class ItemType> bool StackType<ItemType>::IsFull() { return (top==(MAX_ITEMS-1)); }// End of IsFull template<class ItemType> int StackType<ItemType>::Size() { if(IsEmpty()) { std::cout<<"nSTACK EMPTYn"; return('?'); } return top+1; }// End of Size template<class ItemType> void StackType<ItemType>::MakeEmpty() { top = -1; }// End of MakeEmpty template<class ItemType> void StackType<ItemType>::Push(ItemType newItem) { if(IsFull()) { std::cout<<"nSTACK FULLn"; return; } stack[++top]=newItem; }// End of Push template<class ItemType> ItemType StackType<ItemType>::Pop() { if(IsEmpty()) ```