11599: 【原1599】Brackets Stack

题目

题目描述

author: 2017-data-structure TA 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1599

Description

模拟一个括号栈，其元素是三种括号()、[]、{}。

给出长为n的操作序列，按序列要求完成以下几种操作：

1. push
2. pop（栈空则忽略此操作）
3. 输出栈顶元素（栈空则忽略此操作）
4. 询问当前括号是否匹配（栈空则认为匹配）

Input Format

第1行一个整数n，代表总共有n次操作。

第2~n+1行，每行1个整数，第一个数代表操作种类，对于操作1，在同行给定一个入栈元素。

Output Format

对于每次询问操作，输出一行代表答案。

操作3：输出栈顶元素

操作4：匹配输出“YES”,否则输出“NO”

e.g.

{[()]} 匹配

{[}] 不匹配

Sample Input

6
1 (
1 )
3
4
2
4

Sample Output

)
YES
NO

Limits

对于\(40\%\)的数据，只有前三种操作。

对于\(60\%\)的数据，元素只有小括号。

对于\(80\%\)的数据，n < 1000.

对于\(100\%\)的数据, n < 10^6.

BugenZhao's solution

//
// Created by BugenZhao on 2019/3/25.
//

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <map>
#include <cstring>

using namespace std;

template<typename Item>
class Stack {
    class Node {
    public:
        Item val;
        Node *next = nullptr;
    };

    int size;
    Node *top;

public:
    Stack() {
        top = nullptr;
        size = 0;
    }

    void push(const Item &item) {
        top = new Node{item, top};
    }

    Item peek() {
        return top->val;
    }

    Item pop() {
        Node *tmp = top;
        Item ret = top->val;
        top = top->next;
        delete tmp;
        return ret;
    }

    bool isEmpty() {
        return top == nullptr;
    }

    virtual ~Stack() {
        Node *tmp;
        while (top) {
            tmp = top;
            top = top->next;
            delete tmp;
        }
    }
};

using Bracket=int;

class BracketsStack {
    Stack<Bracket> s;
    Stack<Bracket> t;

private:
    inline static bool isLeft(const Bracket &bracket) {
        int j = bracket % 6;
        return j == 0 || j == 2 || j == 4;
    }

    void pushT(const Bracket &bracket) {
        Bracket tmp;
        if (t.isEmpty()) {
            t.push(bracket);
        } else {
            tmp = t.peek();
            if (!isLeft(bracket) && (bracket - tmp - 1) % 6 == 0) {
                t.pop();
            } else {
                t.push(bracket);
            }
        }
    }

public:
    void push(const Bracket &bracket) {
        s.push(bracket);
        pushT(bracket);
    }

    void pop() {
        if (s.isEmpty()) return;
        Bracket bracket = s.pop();
        if (isLeft(bracket)) {
            t.pop();
        } else {
            Bracket tmp;
            if (t.isEmpty() || t.peek() != bracket) {
                t.push(bracket - 1);
            } else {
                t.pop();
            }
        }
    }

    Bracket peek() {
        return s.peek();
    }

    bool match() {
        return t.isEmpty();
    }

    bool isEmpty() {
        return s.isEmpty();
    }
};

int main() {
    BracketsStack bracketsStack;
    int n;
    cin >> n;

    int op;
    char c;
    Bracket b;
    int count = 0;

    while (n--) {
        scanf("%d", &op);
        switch (op) {
            case 1:
                scanf(" %c", &c);
                switch (c) {
                    case '(':
                        b = 6 * count;
                        break;
                    case ')':
                        b = 6 * count + 1;
                        break;
                    case '[':
                        b = 6 * count + 2;
                        break;
                    case ']':
                        b = 6 * count + 3;
                        break;
                    case '{':
                        b = 6 * count + 4;
                        break;
                    case '}':
                        b = 6 * count + 5;
                        break;
                }
                bracketsStack.push(b);
                ++count;
                break;
            case 2:
                bracketsStack.pop();
                break;
            case 3:
                if (bracketsStack.isEmpty()) break;
                b = bracketsStack.peek();
                switch (b % 6) {
                    case 0:
                        c = '(';
                        break;
                    case 1:
                        c = ')';
                        break;
                    case 2:
                        c = '[';
                        break;
                    case 3:
                        c = ']';
                        break;
                    case 4:
                        c = '{';
                        break;
                    case 5:
                        c = '}';
                        break;
                }
                printf("%c\n", c);
                break;
            case 4:
                if (bracketsStack.match()) {
                    printf("YES\n");
                } else {
                    printf("NO\n");
                }
                break;
        }
    }
    return 0;
}

FineArtz's solution

/* Brackets Stack */
#include <iostream>
using namespace std;

char full[1000005], inco[1000005];
bool isco[1000005] = {0};
int n, fsize = 0, isize = 0;

inline bool isLeft(char ch){
    return (ch == '(' || ch == '[' || ch == '{');
}

inline char getRight(char ch){
    if (ch == '(') return ')';
    else if (ch == '[') return ']';
    else if (ch == '{') return '}';
    else return ' ';
}

inline char getLeft(char ch){
    if (ch == ')') return '(';
    else if (ch == ']') return '[';
    else if (ch == '}') return '{';
    else return ' ';
}

int main(){
    ios::sync_with_stdio(false);
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    while (n--){
        int op;
        char ch;
        cin >> op;
        switch(op){
        case 1:
            cin >> ch;
            full[fsize++] = ch;
            if (isLeft(ch)){
                inco[isize++] = ch;
                isco[fsize - 1] = true;
            }
            else{
                if (isize != 0 && isLeft(inco[isize - 1]) && ch == getRight(inco[isize - 1])){
                    --isize;
                    isco[fsize - 1] = true;
                }
                else{
                    inco[isize++] = ch;
                    isco[fsize - 1] = false;
                }
            }
            break;
        case 2:
            if (fsize == 0)
                break;
            ch = full[fsize - 1];
            if (isLeft(ch))
                --isize;
            else{
                if (isco[fsize - 1])
                    inco[isize++] = getLeft(ch);
                else
                    --isize;
            }
            --fsize;
            break;
        case 3:
            if (fsize != 0)
                cout << full[fsize - 1] << '\n';
            break;
        case 4:
            if (isize)
                cout << "NO\n";
            else
                cout << "YES\n";
            break;
        }
    }
    return 0;
}

LuminousXLB's solution

// 1599. Brackets Stack
// #643652 正确 / 分数：100 / 时间：170ms / 内存：9188kb
#include <cstdio>
#include <stack>
#include <vector>
#include <string>

using namespace std;

inline bool paired(char a, char b)
{
    int diff = b - a;
    return diff == 1 || diff == 2;
}

const char *isPaired(const vector<char> &context)
{
    const char *base = context.data();
    const char *ptr = base + context.size() - 1;
    stack<char> to;

    while (ptr >= base)
    {
        if (!to.empty() && paired(*ptr, to.top()))
        {
            ptr--;
            to.pop();
        }
        else
        {
            to.push(*ptr);
            ptr--;
        }
    }

    return to.empty() ? "YES" : "NO";
}

int main()
{
    // freopen("sample.input", "r", stdin);

    int num_of_rounds;
    scanf("%d\n", &num_of_rounds);

    vector<char> context;
    context.reserve(1000);
    int operation;
    char payload;

    for (int i = 0; i < num_of_rounds; i++)
    {
        scanf("%d", &operation);
        switch (operation)
        {
        case 1:
            scanf(" %c\n", &payload);
            context.push_back(payload);
            break;
        case 2:
            if (!context.empty())
            {
                context.pop_back();
            }
            break;
        case 3:
            if (!context.empty())
            {
                printf("%c\n", context.back());
            }
            break;
        case 4:
            printf("%s\n", isPaired(context));
            break;
        }
    }
}

Pangbo13's solution

/*
这道题用cin&cout会超时
*/
#include<iostream>
using namespace std;

template <class elemType>
class stack{
    public:
        virtual bool isEmpty() const = 0; //判栈空
        virtual void push(const elemType&x) = 0; // 进栈
        virtual elemType pop() = 0; // 出栈
        virtual elemType top() const = 0; // 取栈顶元素
        virtual ~stack() {} //虚析构函数
};
template <class elemType>
class seqStack: public stack<elemType>{
    private:
        elemType *elem;
        int top_p;
        int maxSize;
        void doubleSpace();
    public:
        seqStack(int initSize = 1000);
        ~seqStack();
        bool isEmpty() const;
        void push(const elemType &x);
        elemType pop();
        elemType top() const;
};

template <class elemType>
seqStack<elemType>::seqStack(int initSize){
    elem = new elemType[initSize];
    maxSize = initSize ;
    top_p = -1;
}
template <class elemType>
seqStack<elemType>::~seqStack(){
    delete[] elem;
}
template <class elemType>
bool seqStack<elemType>::isEmpty() const{
    return top_p == -1;
}
template <class elemType>
void seqStack<elemType>::push(const elemType &x){
    if(top_p == maxSize -1) doubleSpace();
    elem[++top_p] = x;
}
template <class elemType>
elemType seqStack<elemType>::pop(){
    return elem[top_p--];
}
template <class elemType>
elemType seqStack<elemType>::top() const{
    return elem[top_p];
}
template <class elemType>
void seqStack<elemType>::doubleSpace(){
    elemType *tmp = elem;
    elem = new elemType[2 * maxSize ];
    for (int i = 0; i < maxSize; ++i) elem[i] = tmp[i];
    maxSize *= 2;
    delete [] tmp;
}
//顺序栈定义结束
class BracketsStack{
    private:
        seqStack<char> input,brackets;
        int char_since_unblance;    //保存距离第一个未配对闭括号的字符数
    public:
        BracketsStack();
        void push(const char &x);
        void pop();
        char top() const;
        bool isEmpty() const;
        bool CheckBalance() const;
};

BracketsStack::BracketsStack():char_since_unblance(0){}

void BracketsStack::push(const char &x){
    input.push(x);
    if(char_since_unblance > 0) char_since_unblance++;  //如果前面存在未配对闭括号，后面无论如何都不可能配对，因此不用操作括号栈
    else{
        switch(x){
            case '(': case '[': case '{':
                brackets.push(x);
                break;
            //判断新入栈的闭括号是否配对
            case ')':
                if(brackets.isEmpty()||brackets.top()!='(') char_since_unblance = 1;
                else brackets.pop();
                break;
            case ']':
                if(brackets.isEmpty()||brackets.top()!='[') char_since_unblance = 1;
                else brackets.pop();
                break;
            case '}':
                if(brackets.isEmpty()||brackets.top()!='{') char_since_unblance = 1;
                else brackets.pop();
                break;

        }
    }
}
char BracketsStack::top() const{
    if(input.isEmpty()) return 0;
    else return input.top();
}
bool BracketsStack::CheckBalance() const{
    return (char_since_unblance == 0 && brackets.isEmpty());
}
void BracketsStack::pop(){
    if(input.isEmpty()) return;
    if(char_since_unblance > 0) char_since_unblance--;
    else{
        switch(input.top()){
            case '(': case '{': case '[':
                brackets.pop();
                break;
            //删除已经配对的闭括号时，需要重新入栈一个未配对的开括号
            case ')':
                brackets.push('(');
                break;
            case ']':
                brackets.push('[');
                break;
            case '}':
                brackets.push('{');
                break;
        }
    }
    input.pop();
}
bool BracketsStack::isEmpty() const{
    return input.isEmpty();
}
int main(){
    int n,choice;
    BracketsStack bracketsstack;
    scanf("%d",&n);
    for(int i = 0;i<n;i++){
        scanf("%d",&choice);
        switch(choice){
            case 1:
                char x;
                scanf(" %c",&x);
                bracketsstack.push(x);
                break;
            case 2:
                bracketsstack.pop();
                break;
            case 3:
                if(!bracketsstack.isEmpty()) printf("%c\n",bracketsstack.top());
                break;
            case 4:
                if(bracketsstack.CheckBalance()) printf("YES\n");
                else printf("NO\n");
                break;
        }
    }
}

q4x3's solution

/**
 * 括号栈模拟
 * 优化？
 **/
#include <iostream>
#include <stdio.h>
using namespace std;

char a[100233], b[100233], tmp;
int cura, curb, n, op;

int main() {
    scanf("%d", &n);
    for(int i = 0;i < n;++ i) {
        scanf("%d", &op);
        if(op == 1) {
            scanf(" %c", &tmp);
            a[cura ++] = tmp;
            continue;
        }
        if(op == 2) {
            if(cura == 0) continue;
            -- cura;
            continue;
        }
        if(op == 3) {
            if(cura == 0) continue;
            printf("%c\n", a[cura - 1]);
            continue;
        }
        if(op == 4) {
            curb = 0;
            for(int i = 0;i < cura;++ i) {
                b[++ curb] = a[i];
                if((b[curb] == ')' && b[curb - 1] == '(')||(b[curb] == ']' && b[curb - 1] == '[')||(b[curb] == '}' && b[curb - 1] == '{'))
                    curb -= 2;
            }
            if(curb) printf("NO \n");
            else printf("YES \n");
        }
    }
}

skyzh's solution

#include <iostream>
#include <cstdio>
using namespace std;


template <typename T>
class Stack {
public:
    T *data;
    int ptr;
    Stack(int cap) : data(new T[cap]), ptr(0) {}
    ~Stack() { delete[] data; }
    void push(const T& d) { data[ptr++] = d; }
    T pop() { return data[--ptr]; }
    T top() { return data[ptr - 1]; }
    bool empty() { return ptr == 0; }
    void print() { for (int i = 0; i < ptr; i++) cout << data[i]; printf("\n"); }
    void clear() { ptr = 0; }
};

int main() {
    Stack <char> d(1000000);
    Stack <int> a(1000000), tmp(1000000);
    char ch[100], t, _c;
    int N, op;
    scanf("%d", &N);
    for (int i = 0; i < N; i++) {
        scanf("%d", &op);
        if (op == 1) {
            scanf(" %s", ch);
            _c = ch[0];
            switch(_c) {
                case '(': case '[': case '{':
                a.push(d.ptr);
                break;
                case ')':
                if (!a.empty() && d.data[a.top()] == '(') tmp.push(a.pop()); else a.push(d.ptr);
                break;
                case ']':
                if (!a.empty() && d.data[a.top()] == '[') tmp.push(a.pop()); else a.push(d.ptr);
                break;
                case '}':
                if (!a.empty() && d.data[a.top()] == '{') tmp.push(a.pop()); else a.push(d.ptr);
                break;
            }
            d.push(_c);
        } else if (op == 2) {
            if (!d.empty()) {
                char ch = d.pop();
                if (a.top() == d.ptr) a.pop();
                else a.push(tmp.pop());
            }
        } else if (op == 3) {
            if (!d.empty()) printf("%c\n", d.top());
        } else if (op == 4) {
            if (a.empty()) printf("YES\n"); else printf("NO\n");
        }
    }
    return 0;
}

victrid's solution

#include <cstdio>
#include <iostream>
//cstdio有幸埋printf，iostream无辜铸cin
using namespace std;
inline bool pairing(char c1, char c2) {
    return (c1 == '(' && c2 == ')') || (c1 == '[' && c2 == ']') || (c1 == '{' && c2 == '}');
}
template <typename T>
class basestack {
private:
    T container[100002];
    T* top_ptr;
    int total;

public:
    basestack() {
        top_ptr = container;
        total   = 0;
    }
    int height() { return total; }
    T push(T p) {
        *top_ptr = p;
        top_ptr++;
        total++;
        return *(top_ptr - 1);
    }
    T* top() { return total ? (top_ptr - 1) : nullptr; }
    T pop() {
        if (total == 0)
            return *top_ptr;
        top_ptr--;
        total--;
        return *top_ptr;
    }
};

class bracketstack {
private:
    basestack<char> container;
    basestack<char*> brstack;
    basestack<char*> trashbin;

public:
    bracketstack(){};
    bool balance() { return (brstack.height() == 0); }
    void operate() {
        int operation;
        char proc;
        scanf("%d", &operation);
        char* ans;
        switch (operation) {
        case 1:
            scanf(" %c", &proc);
            container.push(proc);
            if (brstack.height() != 0 && pairing(**(brstack.top()), proc)) {
                trashbin.push(brstack.pop());
            } else {
                brstack.push(container.top());
            }
            break;
        case 2:
            if (container.height() != 0) {
                if (brstack.height() != 0 && *(brstack.top()) == container.top()) {
                    brstack.pop();
                } else {
                    brstack.push(trashbin.pop());
                }
                //! here change the container at the last.
                container.pop();
            }
            break;
        case 3:
            ans = container.top();
            if (ans == nullptr)
                break;
            printf("%c\n", *(ans));
            break;
        case 4:
            printf(balance() ? "YES\n" : "NO\n");
            break;
        }
    }
};

bracketstack b;

int main() {
    int m;
    scanf("%d", &m);
    for (int i = 0; i < m; i++) {
        b.operate();
    }
    return 0;
}

zqy2018's solution

/*
    See the solution at https://github.com/zqy1018/sjtu_oj_solutions/blob/master/solutions/sjtu1599.md
*/
#include <bits/stdc++.h>
#define INF 2000000000
using namespace std;
typedef long long ll;
int read(){
    int f = 1, x = 0;
    char c = getchar();
    while(c < '0' || c > '9'){if(c == '-') f = -f; c = getchar();}
    while(c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
    return f * x; 
}
int n, tp = 0;
int st[1000005] = {0};
char st2[1000005];
void init(){
    n = read();
}
void solve(){
    char ord[3];
    while(n--){
        int opt = read();
        if(opt == 1){
            scanf("%s", ord);
            if(ord[0] == '(' || ord[0] == '[' || ord[0] == '{'){
                tp++, st[tp] = tp, st2[tp] = ord[0];
            }else {
                if(!tp) tp++, st[tp] = tp, st2[tp] = ord[0];
                else{
                    tp++, st2[tp] = ord[0];
                    if(ord[0] == ')'){
                        if(st2[st[tp - 1]] == '(')
                            st[tp] = st[st[tp - 1] - 1];
                        else st[tp] = tp;
                    }else if(ord[0] == ']'){
                        if(st2[st[tp - 1]] == '[')
                            st[tp] = st[st[tp - 1] - 1];
                        else st[tp] = tp;
                    }else if(ord[0] == '}'){
                        if(st2[st[tp - 1]] == '{')
                            st[tp] = st[st[tp - 1] - 1];
                        else st[tp] = tp;
                    }
                }
            }
        }
        if(opt == 2)
            if(tp) tp--;
        if(opt == 3){
            if(tp) putchar(st2[tp]), putchar('\n');
        }
        if(opt == 4){
            if(!tp) printf("YES\n");
            else printf("%s\n", st[tp] == 0 ? "YES": "NO");
        }
    }
}
int main(){
    init();
    solve();
    return 0;
}