Skip to content

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;
}