Twitter Challenge Question 2

////////////////////////////////////////
//Code Written By: Sergio A. Nuñez    //
//Date of Final Revision: 1/20/2017   //
///////////////////////////////////////////////////////////////////////////////////////////////
//Summary of Code:                                                                           //
//This program will utilize a modular programming approach to make a rather complex          //
//program simpler. The Driver Program will get input from the system and seperate            //
//it into two seperete deques, one for the expression, and one for the operations.           //
//This program will push character by character to a deque until it encounters a slash, '/'. //
//while parsing it will ignore spaces and call a function to manage the operations           //
//gathered from the input. Once the '/' is encountered it will then push characters          //
//to a different deque that will only store the operations. When there is no more input      //
//The program will then read Operation by operation applying the changes to the expression   //
//deque. 'R' will reverse the string, and 'S' will simplify the expression removing any      //
//redundant parentheses. Once all operations are complete the expression deque will then     //
//be displayed and the next input will be read in, if there is no more input the program     //
//will terminate.                                                                            //
//-------------------------------------------------------------------------------------------//
//Simplify idea:                                                                             //
//Parentheses are only neccessary when you need to break the order of operations             //
//for this reason if there is a variable to the left of the opening parenthesis it will make //
//the parentheses necessary, and if there's only a variable to the right it will make them   //
//redundant and can be taken away. Since in all these inputs there are only multiplication we//
//can assume this rule to simplify the expression.                                           //
///////////////////////////////////////////////////////////////////////////////////////////////
#include <map>
#include <set>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <string>
#include <bitset>
#include <cstdio>
#include <limits>
#include <vector>
#include <climits>
#include <cstring>
#include <cstdlib>
#include <fstream>
#include <numeric>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <unordered_map>

using namespace std;

//------------------------------------------------------
//Prototypes for operation functions
//Used for Modular Programming
//------------------------------------------------------
void reverse(deque<char>& str);
void simplify(deque<char>& str);
void Process_Commands(deque<char>& cmd, deque<char>& str);
void dispDeque(deque<char> str);

int main() {
    //------------------------------------------------------------------------------
    //Variable Set up
    //------------------------------------------------------------------------------

    string input;             //String to handle input
    bool inputover = false;   //Boolean used to determine if theres no more input

    deque<char> str;          //Deques used for easier Stack, and Queue Functionality
    deque<char> cmd;          //*Note: These deques will be used to split input and  *
                              //*differentiate between Expression Tree and operations*

    //---------------------------------------------------------------------------
    //This simply makes the program work for Hackerrank's Input Methods
    ///-----------------------------------------------------------------------------

    //Cycle until no more input is left
    while(!inputover)
    {
        //Get input and Assign to input string
        getline(cin,input);

        //Clear for next input
        cin.clear();

        //Check for end of input
        if(input.empty())
        {
            break;
        }

        //===========================================================
        //Implementation Begins Here
        //===========================================================

        //Iterate though Input and seperate Expression from Operations
        while(input.length() > 0)
        {
            //If Statement to detect slash to indicate operations
            if(input[0]=='/')
            {
                input.erase(input.begin());
                //Iterate through remaining input and add input to Operations Deque
                while(input.length() > 0)
                {
                    cmd.push_back(input[0]);
                    input.erase(input.begin());
                }
            }
            //If statement Used to ignore Spaces
            else if(input[0] == ' ')
            {
                input.erase(input.begin());
            }
            //Add input, one character at a time, to the Expression Deque
            else
            {
                str.push_back(input[0]);
                input.erase(input.begin());
            }
        }

        //================================================================================
        //Begin Modular Programming for easier Debugging, Implementation, and Maintenece
        //================================================================================

        //Execute Operation Commands
        Process_Commands(cmd,str);

        //Display Expression
        dispDeque(str);

        //Clear deques for next input
        str.clear();
        cmd.clear();
    }

    return 0;
}

//Fonction for Reverse Operation
void reverse(deque<char>&str)
{
    //Create Temporary stack
    stack<char> temp;

    //Cycle until Expression Deque is empty
    while(!str.empty())
    {
        //In order to maintain readability we
        //want to push in the opposite parentheses
        //since the string is reverse example below
        //
        //Straight Push: (AB)C => C)BA(
        //Reverse Parentheses: (AB)C = > C(BA)
        if(str.front() == '(')
        {
            temp.push(')');
        }
        //Same Reverse Parentheses procedure as before
        else if(str.front() == ')')
        {
            temp.push('(');
        }
        //Push any other character into the stack
        else
        {
            temp.push(str.front());
        }
        //Pop from expression Deque to move on to next
        //character
        str.pop_front();
    }
    //Simultaniously Push contents of stack into expression
    //Deque that will result in a reverse order
    while(!temp.empty())
    {
        str.push_back(temp.top());
        temp.pop();
    }
}

//Function for Simplify Operation
void simplify(deque<char>& str)
{
    //------------------------------------------------------------------------------
    //Variable Set up
    //------------------------------------------------------------------------------
    int count = 0;    //Variable used to keep track of parentheses pairs
    int skip = 0;     //Variable used to Group parentheses
    string input;     //String used in parallel with deque to find parentheses pairs

    //Check if VERY FIRST ELEMENT is enclosed in parentheses
    if (str[0] == '(')
    {
        //Pass value of expression Deque to string to be manipulated
        for (int i = 0; i < str.size(); i++)
        {
            input += str[i];
        }
        //clear expression deque so simplified output can be pushed in.
        str.clear();
        //Iterate though entire length of string
        for (int i = 0; i < input.length(); i++)
        {
            //Check if current position is an Open parentheses
            if (input[i] == '(')
            {
                //Once open parentheses is found begin another iterator loop
                //starting 1 character in front of the open parentheses
                //to find it's matching closing parentheses
                for (int j = i + 1; j < input.length(); j++)
                {
                    //If closing parentheses is found and there are no skips
                    //replace both characters with the count of parentheses groups
                    //and increase count by one
                    if (input[j] == ')' && skip == 0)
                    {
                        input.erase(input.begin() + i);
                        input.insert(i, to_string(count));
                        input.erase(input.begin() + j);
                        input.insert(j, to_string(count));
                        count++;
                        skip = 0;
                        j = input.length();
                    }
                    //if a closed parentheses is found and the skip counter
                    //does not == 0, move on and reduce skip counter by one
                    else if (input[j] == ')' && skip > 0) skip--;
                    //if an open parentheses is encountered increase skip counter
                    //by one, and move on.
                    else if (input[j] == '(') skip++;
                }
            }
        }

        //to compensate for the last parentheses pair increasing count by one
        //reduce it by one to keep the count at the actuall number of parentheses pair
        count--;

        //Iterate though expression string to find a number indicating a parentheses
        for (int j = 0; j < input.length(); j++)
        {
            //Check to see if a number is found indicating a parentheses
            if (isdigit(input[j]))
            {
                //Once the first number indicating a parentheses is found
                //begin another iterator loop starting 1 character
                //in front of the number just found to find it's matching
                //number indicating a closing parentheses
                for (int k = j + 1; k < input.length(); k++)
                {
                    //if both numbers match, parentheses pair has been found
                    if (input[k] == input[j])
                    {
                        //==============================================================
                        //Insert Cases to check if Parentheses Redundant or not below
                        //==============================================================
                        //*Could not figure out what was wrong with the last hidden case,
                        //but had the input been revealed tweeks would more than likely
                        //need to go in the code below here*
                        //--------------------------------------------------------------

                        //if there is a variable to the left of an open parentheses
                        //then Order of operations is broken and parentheses are not
                        //redundant, therefore must be kept.
                        //Replace Numbers in string with parentheses character.
                        if (isalpha(input[j - 1]))
                        {
                            input[j] = '(';
                            input[k] = ')';

                        }
                        //Otherwise, since the only operation in the expression tree is
                        //multiplication then parentheses are redundant if there's not a
                        //variable on it's left side, since order of operations will be
                        //respected weather or not the parentheses are there.
                        //erase numbers leaving no parentheses behind.
                        //-------------------------------------------------------------------
                        //*Note that if more operations are going be added to the expression*
                        //*besides multiplication these cases must be changed.              *
                        //-------------------------------------------------------------------
                        else
                        {
                            input.erase(input.begin() + k);
                            input.erase(input.begin() + j);
                            j--;
                        }
                        //Once closing parentheses has been found and proper action has been
                        //taken, break out of second itterator loop to find another parentheses
                        //pair
                        break;
                    }
                }
            }
        }
        //iterate though string adding
        //each character to the deque
        for (int i = 0; i < input.length(); i++)
        {
            str.push_back(input[i]);
        }
    }
}

//Function to process all Operations
void Process_Commands(deque<char>& cmd, deque<char>& str)
{
    //Itterate through every Operation until none is left.
    while(!cmd.empty())
    {
        //Execute Reverse Operation if R is up next
        if(cmd.front() == 'R')
        {
            reverse(str);
        }
        //Execute Simplify Operation if S is up next
        else if(cmd.front() =='S')
        {
            simplify(str);
        }
        //Once Command has been processed, or no command
        //is read, pop for next Operation.
        cmd.pop_front();
    }
}

//Custom Function to display Deque
void dispDeque(deque<char> str)
{
    for (int i = 0; i < str.size(); i++)
        {
            cout << str[i];
        }
        cout << endl;
}