Skip to content

11605: 【原1605】Brackets Stack

题目

题目描述

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

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.

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;

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

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

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

ligongzzz's solution

#include "iostream"
#include "cstdio"
using namespace std;

constexpr auto maxNum = 1000000;

class myStack {
    int num = 0, acNum = 0;
    char data[maxNum] = { 0 };
    bool flag[maxNum] = { 0 };
    char ac[maxNum] = { 0 };
public:
    void push(char b) {
        if (b == '(' || b == '[' || b == '{')
            ac[acNum++] = b;
        else if (b == ')'&&acNum > 0 && ac[acNum - 1] == '(') {
            acNum--;
            flag[num] = true;
        }
        else if (b == ']'&&acNum > 0 && ac[acNum - 1] == '[') {
            acNum--;
            flag[num] = true;
        }
        else if (b == '}'&&acNum > 0 && ac[acNum - 1] == '{') {
            acNum--;
            flag[num] = true;
        }
        else
            ac[acNum++] = b;
        data[num++] = b;
    }
    bool empty() {
        return num == 0;
    }
    char pop() {
        if (num == 0)
            return  0;
        num--;
        char temp = data[num];
        data[num] = 0;

        //回退
        if (flag[num]) {
            if (temp == ')')
                ac[acNum++] = '(';
            else if (temp == ']')
                ac[acNum++] = '[';
            else if (temp == '}')
                ac[acNum++] = '{';
        }
        else
            acNum--;
        flag[num] = false;
        return temp;
    }
    char back() {
        if (num == 0)
            return 0;
        return data[num - 1];
    }
    bool match() {
        return acNum == 0;
    }
};

int main() {
    int num;
    myStack data;
    cin >> num;
    for (int i = 0; i < num; i++) {
        int temp;
        scanf("%d", &temp);
        if (temp == 1) {
            char c;
            scanf(" %c", &c);
            data.push(c);
        }
        else if (temp == 2) {
            data.pop();
        }
        else if (temp == 3) {
            if (!data.empty())
                printf("%c\n", data.back());
        }
        else if (temp == 4) {
            if (data.match())
                printf("YES\n");
            else
                printf("NO\n");
        }
    }

    return 0;
}

Neight99's solution

#include <iostream>

using namespace std;

char input1[1001000], save[1001000];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int N, choice, inputCount = 0, saveCount = 0, wrong = 0;
    char ch;

    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> choice;

        if (choice == 1) {
            cin >> ch;
            input1[++inputCount] = ch;
            if (wrong) {  //如果已经有问题就直接跳过下面的部分
                continue;
            } else if (ch == ')' || ch == ']' || ch == '}') {
                if ((saveCount == 0) || (ch == ')' && save[saveCount] != '(') ||
                    (ch == ']' && save[saveCount] != '[') ||
                    (ch == '}' && save[saveCount] != '{')) {
                    wrong = inputCount;  //记录下有问题的位置
                } else {  //如果新输入的和之前的左括号配对了就直接把第二个栈的左括号删去
                    saveCount--;
                }
            } else {  //如果输入进来的是左括号就直接将其存入第二个栈
                save[++saveCount] = ch;
            }
        } else if (choice == 2) {
            if (inputCount) {
                if (wrong) {
                    inputCount--;
                    if (wrong >
                        inputCount) {  //如果有问题的部分已经被pop则直接重置错误位置
                        wrong = 0;
                    }
                } else {
                    if (input1[inputCount] == '(' ||
                        input1[inputCount] == '[' ||
                        input1[inputCount] == '{') {
                        saveCount--;
                    } else if (input1[inputCount] == ')') {
                        save[++saveCount] = '(';
                    } else if (input1[inputCount] == ']') {
                        save[++saveCount] = '[';
                    } else if (input1[inputCount] == '}') {
                        save[++saveCount] = '{';
                    }
                    inputCount--;
                }
            }
        } else if (choice == 3) {
            if (inputCount) {
                cout << input1[inputCount] << '\n';
            }
        } else if (choice == 4) {
            if (wrong == 0 &&
                saveCount == 0) {  //没有错误同时第二个栈没东西了才输出YES
                cout << "YES\n";
            } else {
                cout << "NO\n";
            }
        }
    }
    return 0;
}

WashSwang's solution

#include <iostream>
#include <cstdio>
using namespace std;
char rstack[1000001],istack[1000001],c;
int rtop,itop,n,x;
bool match[1000001];
void push(char c){
    if (rstack[rtop-1]=='('&&c==')') {
        rtop--;
        match[itop]=true;
    }
    else if (rstack[rtop-1]=='['&&c==']') {
        rtop--;
        match[itop]=true;
    }

    else if (rstack[rtop-1]=='{'&&c=='}') {
        rtop--;
        match[itop]=true;
    }
    else rstack[rtop++]=c;
}
void raw_push(char c){
    if (rstack[rtop-1]=='('&&c==')') rtop--;
    else if (rstack[rtop-1]=='['&&c==']') rtop--;
    else if (rstack[rtop-1]=='{'&&c=='}') rtop--;
    else rstack[rtop++]=c;
}
void pop(){
    switch (istack[itop-1]) {
        case '(':
            raw_push(')');
            break;
        case ')':
            if (match[itop-1]) {raw_push('('); match[itop-1]=false;}
            else rtop--;
            break;
        case '[':
            raw_push(']');
            break;
        case ']':
            if (match[itop-1]) {raw_push('['); match[itop-1]=false;}
            else rtop--;
            break;
        case '{':
            raw_push('}');
            break;
        case '}':
            if (match[itop-1]) {raw_push('{'); match[itop-1]=false;}
            else rtop--;
            break;
    }
    itop--;
}
int main() {
    scanf("%d",&n);
    for (int i=0;i<n;++i)
    {
        scanf("%d",&x);
        if (x==1){
            scanf(" %c",&c);
            push(c);
            istack[itop++]=c;
        }
        if (x==2&&itop>=1) pop();
        if (x==3&&itop>=1) printf("%c\n",istack[itop-1]);
        if (x==4){
            if (!rtop) printf("YES\n");
            else printf("NO\n");}
    }
    return 0;
}