#include <iostream>
#include <string>
#include <stack>

using namespace std;


/* removeToken
 *  parameters:
 *      const string& -- a constant input string by reference to be changed
 *      out -- the string that is being changed
 *  return value: out (the changed string in its final format
 *
 *  This function is used to remove the Opening XML tags from a token and is
 *  used for the oput of errors.
 */
string removeTokens(const string& IN){
    string out = IN;
    out.erase(out.begin()); // remove '<'
    out.erase(out.size()-1); // remove '>'
    return out;
}


/* checkTags
 *  parameters:
 *              one -- the first input string to be checked
 *         tokenOne -- local variable that can be changed without changing
 *                    the original value
 *         tokenTwo -- local variable that can be changes without changing
 *                    the original value. Used for pulling a string off the
 *                    stack.
 *       checkToken -- bool returning value used to check the two strings
 *            level -- used to keep track of which level the stack is on
 *  return value: 0 -- everything ran correctly, XML okay
 *  return value: 1 -- error found, return and xit program
 *  return value: 2 -- no errors found, check for more input
 *
 *  This function will recursively check the XML tags for correct open and
 *  Closing tags. If the tags are not properly formatted then an error will
 *  be displayed.
 */
int checkTags(const string& ONE,stack<string> &stk){
    int level = 1; // sets the level of the stack to first level of the stack
    string tokenOne, tokenTwo; //creates a string value for the input strings
    tokenOne = ONE; // local variable of input string one
    int size = (tokenOne.size()-1); //Last letter or symbol of string

    // Base Case 1 - CLOSE tag used first with no OPEN Tags
    // If there user has inputed a CLOSE tag without an OPEN tag
    // then display error "Invalid XML document; Closing tag CLOSE
    // when no tags are open.
    if(stk.size() == 0){ //GOOD
        // Base Case 2 - user inputs OPEN tag
        // If the user inputs an OPEN tag, it is pusched on to stack and
        // returns and waits for further input. Ignores all tags that are not
        // complete. ie: <open or open>
        if(tokenOne[0] == '<' && tokenOne[1] != '/'&& tokenOne[size] == '>'){

            cout << "I tried Base Case 2" << endl;
            stk.push(tokenOne); //push that tag onto the stack
            return 2;
        }

        // Base Case 3 - CLOSE tag used after OPEN Tag has been used
        // If the user inputs a CLOSE tag after there has been at least
        // one OPEN tag, then check to see if they match. If the Tags
        // Match then wait for more input untill stack is equal to Zero.
        // If the CLOSE and OPEN tag do not match at any time, display
        // error stating "Invalid XML document; trying to close tag
        // CLOSE with tag OPEN at level LEVEL. Ignores all tags that are not
        // Complete. ie </bob or /bob>
        if(tokenOne[0] == '<' && tokenOne[1] == '/'&& tokenOne[size] == '>'){
            cout << "I tried Base Case 3" << endl;
            tokenOne = removeTokens(tokenOne); // Clear XML tags
            tokenOne.erase(tokenOne.begin()); // remove '/' char
            cout << "Invalid XML document; closing tag \"" << tokenOne
            <<"\" when no tags are open"; //display error
            return 1; // close program
        }
    }


    //The stack is not EMPTY
    if(stk.size() != 0){
        tokenTwo = stk.top(); // sets tokenTwo to top of the stack
        stk.pop(); //pop the previously stacked token
        int size2 = (tokenTwo.size()-1);
        bool checkToken = false;

        if(tokenOne[0] == '/0'){
            cout << "Invalid XML document; tag /"<< tokenTwo <<"/was not"
            << "closed at level " << level;
            return 1;
        }

        // Base Case 4 - There was a previous OPEN tag placed on the stack
        // with out being closes. This will push the new open tag to the top
        // of the stack untill it has been removed by a close tag. Ignores
        // all tags that are not Complete. ie </bob or /bob>
        if(tokenOne[0] == '<' && tokenOne[1] != '/' && tokenOne[size] == '>'
        && tokenTwo[0] == '<' && tokenTwo[1] != '/' && tokenTwo[size2] == '>'){
            cout << "I tried Base Case 4" << endl;
            stk.push(tokenTwo); // push tokenTwo back on
            stk.push(tokenOne); // push tokenOne on top of tokenTwo
            return 2;
        }

        // Base Case 5 - a CLOSE token was used. This if statment will check
        // and see if the CLOSE token that was used matches the last inputed
        // OPEN token. If the Tags do not match it will return an error, else
        // it will return a continue statment.
        if(tokenOne[0] == '<' && tokenOne[1] == '/' && tokenOne[size] == '>'
        && tokenTwo[0] == '<' && tokenTwo[1] != '/' && tokenTwo[size2] == '>')
        {
            cout << "I tried Base Case 5" << endl;
            tokenOne = removeTokens(ONE); // emoves 'ML chars on 1st string
            tokenTwo = removeTokens(tokenTwo); // emoves XML chars on 2nd string
            tokenOne.erase(tokenOne.begin()); // if it is remove '/'
            checkToken = strcmp(tokenOne.c_str(), tokenTwo.c_str());// compare
            //checkToken = quickCmp(tokenOne,tokenTwo);
            // If the Tokens do not match or returns fasle then the program
            // will display error
            if(checkToken = false){
                cout << "let me check this out" << endl;
                level += stk.size();//calculate level
                cout << "Invalid XML document; trying to close tag\"" <<
                tokenTwo << "\" with tag \"" <<tokenOne << "\" at level " <<
                level;
                //then display error
                cout << "returning 1" << endl;
                return 1; //end program
            }

            // If the Tokens Match it will return a true statment then
            // continue checking the rest of the stack
            if(checkToken = true && stk.size() != 0){
                checkToken = false;
                cout << "returning 2" << endl;
                return 2;
            }

            //if stack is now clear return valid XML code
            if(checkToken = true && stk.size() == 0){
                checkToken = false;
                cout << "returning 0" << endl;
                return 0;
            }
        }
        cout << "did i get here by chance?" << endl;
        stk.push(tokenTwo); // else just push it back on the stack for next try
        return 2;
    }
}
/* main
 *  parameters:
 *      argc -- the number of arguments from the command line
 *      argv -- the command line argument values
 *      token -- Is a inputed XML token that needs to be check for correctness
 *      token2 -- Is a previously imputed XML token that will test agains the
 *                current XML tag.
 *      check -- IS an integer returning value that checks to see if it was a
 *               Valid XML tag
 *      tagStack -- Is a Stack that has been implemented for storage purposes
 *                  within the confines of this program.
 *  return value: 0 (indicating a successful run)
 *
 *  PUT YOUR COMMENTS FOR THIS FUNCTION HERE
 */
int main(int argc, char **argv){
    string token;   //token to be tested
    string token2;  //token to test against
    int check = 0;  //check function
    stack<string> tagStack;
    // the tagStack is used for storing opening tags so they can be matched
    // later
    //stack<string> tagStack;

    /* Each time we go through this while loop, we read a space-delimited word
    // into "token". Also, each time the while loop checks the result of "cin"
    // -- if cin has reached the end of the file, it will return false and the
    // loop will exit. Otherwise, it will return true and the loop will
    // continue.*/
    while (cin >> token){

        if(token[0] != '/0'){
            check = checkTags(token,tagStack);

            switch(check){
                case 0:
                cout << endl << "Valid XML document" << endl;
                return 0;
                break;

                case 1: //end program
                return 1;
                break;

                default:;
            }
        }
    }

    // if check returned with an error close the program without letting the
    // user know it was a false positive
    if(check == 1){
        return 0;
    }

    // Base case 1 - Nothing inputed/blank document (Valid XML Document)
    // Base case 2 - No XML Tags were used (Valid XML Document)
    cout << "Valid XML document" << endl; //if document is blank it is valid
    return 0; // end program
}