# 14037 - DS_2023_HW2_Stack&Queue
>author: Utin
###### tags: `Data Structure`

---

## Brief
Note that **segment** is a special string for storing the input string.

For example:

if **s** is "()))())()()))", then **segment** will be "-2))-2)-4))".

## Solution 0 (Self-defined Stack)

#include <iostream>

template <class T>
class stack {
    private:
        T* head;
        int len;
        int capacity;
    public:
        stack() : head(new T[100]), len(0), capacity(100) {}
        void push(T in) {
            if (len == capacity) {
                T* newStack = new T[capacity + 100];
                for (int i = 0; i < len; i++) {
                    newStack[i] = head[i];
                }
                delete [] head;
                head = newStack;
                capacity += 100;
            }
            head[len++] = in;
        }
        void pop() {
            if (len) {
                head[--len].~T();
                capacity--;
            }
        }

        T top() {
            if (len) return head[len - 1];
            else return 0;
        }

        int size() {
            return len;
        }
};

int main() {

    int n;
    std::cin >> n;
    
    while (n--) {

        // declaration
        int min = 0;
        std::string s;
        stack<char> process;
        stack<int> segment;

        // get the input string
        std::cin >> s;

        for (int i = 0; i < s.size(); i++) {

            if (s[i] == '(') {
                process.push(s[i]);
                segment.push(s[i]);
            }

            else if (s[i] == ')' && process.size() && process.top() == '(') {

                // if there are continuous valid strings
                if (segment.top() < 0) {

                    // get the continuous length
                    int tmp = segment.top() - 2;
                    segment.pop();

                    // pop the '(' in segment
                    segment.pop();

                    // combine the continuous valid strings
                    while (segment.size() && segment.top() < 0) {
                        tmp += segment.top();
                        segment.pop();
                    }

                    // push back the result of combination
                    segment.push(tmp);

                }

                // if there aren't continuous valid strings
                else {

                    // length of a set of "()" is 2
                    int tmp = -2;

                    // pop the '(' in segment
                    segment.pop();

                    // combine the continuous valid strings before '('
                    while (segment.size() && segment.top() < 0) {
                        tmp += segment.top();
                        segment.pop();
                    }

                    // push back the result of combination
                    segment.push(tmp);

                }

                // pop the '(' in process
                process.pop();

            }

            else if (s[i] == ')') {
                process.push(s[i]);
                segment.push(s[i]);
            }

        }

        // get the longest length of the valid strings
        while (segment.size()) {
            if (min > segment.top()) min = segment.top();
            segment.pop();
        }

        // output
        printf("%c", ((-min) / 2) % 26 + 'a');

    }

    printf("\n");

}

// By Utin

## Solution 1 (STL Stack)

#include <iostream>
#include <stack>

const int debug = 0; // set debug to 1 to turn on debug mode

int main() {

    int n;
    std::cin >> n;
    
    while (n--) {

        // declaration
        int min = 0;
        std::string s;
        std::stack<char> process;
        std::stack<int> segment;

        // get the input string
        std::cin >> s;

        for (int i = 0; i < s.size(); i++) {

            if (s[i] == '(') {
                process.push(s[i]);
                segment.push(s[i]);
            }

            else if (s[i] == ')' && process.size() && process.top() == '(') {

                // if there are continuous valid strings
                if (segment.top() < 0) {

                    // get the continuous length
                    int tmp = segment.top() - 2;
                    segment.pop();

                    // pop the '(' in segment
                    segment.pop();

                    // combine the continuous valid strings
                    while (segment.size() && segment.top() < 0) {
                        tmp += segment.top();
                        segment.pop();
                    }

                    // push back the result of combination
                    segment.push(tmp);

                }

                // if there aren't continuous valid strings
                else {

                    // length of a set of "()" is 2
                    int tmp = -2;

                    // pop the '(' in segment
                    segment.pop();

                    // combine the continuous valid strings before '('
                    while (segment.size() && segment.top() < 0) {
                        tmp += segment.top();
                        segment.pop();
                    }

                    // push back the result of combination
                    segment.push(tmp);

                }

                // pop the '(' in process
                process.pop();

            }

            else if (s[i] == ')') {
                process.push(s[i]);
                segment.push(s[i]);
            }

            /******** debug mode ********/
            if (debug) {

                std::cout << "i = " << i << '\n';

                std::cout << "string:  ";
                for (int j = 0; j <= i; j++) std::cout << s[j];
                std::cout << '\n';

                std::stack<int> st;
                while (segment.size()) {
                    st.push(segment.top());
                    segment.pop();
                }
                std::cout << "segment: ";
                while (st.size()) {
                    if (st.top() < 0) printf("%d", st.top());
                    else printf("%c", st.top());
                    segment.push(st.top());
                    st.pop();
                }
                std::cout << '\n';

            }
            /****************************/

        }

        // get the longest length of the valid strings
        while (segment.size()) {
            if (min > segment.top()) min = segment.top();
            segment.pop();
        }

        // debug mode
        if (debug) std::cout << "min: " << min << '\n';

        // output
        printf("%c", ((-min) / 2) % 26 + 'a');

    }

    printf("\n");

}

// By Utin

## Reference