#include <bits/stdc++.h>

using namespace std;

template<typename Type>
class SeqStack {
public:
//    构造函数
    SeqStack(int size) : top(-1), maxSize(size) {
        data = new Type[size];
        if (data == NULL) {
            cout << "Error:初始化失败！" << endl;
            exit(1);
        }
    }

    ~SeqStack() {
        delete[] data;
    }

    bool getResult();

    bool getResult2();

public:

    void Push(const Type item); //push data
    Type Pop();                 //pop data
    Type GetTop() const;        //get data
    void Print();               //print the stack
    void MakeEmpty() {           //make the stack empty
        top = -1;
    }

//判断是否为空
    bool IsEmpty() const {
        return top == -1;
    }

//判断是否满栈
    bool IsFull() const {
        return top == maxSize - 1;
    }


private:
    int top;
    Type *data;
    int maxSize;

};

template<typename Type>
void SeqStack<Type>::Push(const Type item) {
    if (IsFull()) {
        cout << "Error: 栈满" << endl;
        return;
    }
    data[++top] = item;
}

template<typename Type>
Type SeqStack<Type>::Pop() {
    if (IsEmpty()) {
        cout << "Error: 空栈" << endl;
        exit(1);
    }
    return data[top--];
}

template<typename Type>
Type SeqStack<Type>::GetTop() const {
    if (IsEmpty()) {
        cout << "Error: 空栈" << endl;
        exit(1);
    }
    return data[top];
}

template<typename Type>
void SeqStack<Type>::Print() {
    cout << "栈底";
    for (int i = 0; i <= top; i++) {
        cout << "--->" << data[i];
    }
    cout << "--->栈顶" << endl << endl << endl;
}

/**
 * 判断一个表达式中的括号（仅有一种括号，小、中或大括号）是否配对。编写并实现它的算法
 * @tparam Type
 * @return
 */
template<typename Type>
bool SeqStack<Type>::getResult() {
    int left = 0;
    int right = 0;
    for (int i = 0; i <= top; ++i) {
        if (data[i] == '(') {
            cout << "left " << data[i] << endl;
            left++;
        } else if (data[i] == ')') {
            cout << "right " << data[i] << endl;
            right++;
        }
    }
    return left == right;
}

template<typename Type>
bool SeqStack<Type>::getResult2() {
    int left = 0;
    int right = 0;
    for (int i = 0; i <= top; ++i) {
        if (data[i] == '(' || data[i] == '[' || data[i] == '{') {
            cout << "left " << data[i] << endl;
            left++;
        } else if (data[i] == ')' || data[i] == ']' || data[i] == '}') {
            cout << "right " << data[i] << endl;
            right++;
        }
    }
    return left == right;
}

int main() {
    //基本操作
    SeqStack<int> stack(10);
    int init[10] = {1, 2, 6, 9, 0, 3, 8, 7, 5, 4};
    for (int i = 0; i < 10; i++) {
        stack.Push(init[i]);
    }
    stack.Print();

    stack.Push(88);

    cout << stack.Pop() << endl;
    stack.Print();

    stack.MakeEmpty();
    stack.Print();

    stack.Pop();


    //判断表达式的括号是否匹配 只含一种括号
    SeqStack<char> myStack(20);
    string str = "(2*(2+3))";
    for (int i = 0; i < str.length(); ++i) {
        myStack.Push(str.at(i));
    }
    cout << "+++++++++++" << endl;
    cout << myStack.getResult();

    //判断表达式的括号是否匹配 含有多种括号
    string str2 = "2+3*(4-{5+2}*3)";
    string str3 = "2+3*(4-{5+2*3}";
    SeqStack<char> myStack2(str3.length());
    for (int i = 0; i < str3.length(); ++i) {
        myStack2.Push(str3.at(i));
    }
    cout << "+++++++++++" << endl;
    cout << myStack2.getResult2();

    return 0;
}