# 11599: 【原1599】Brackets Stack

### 题目描述

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

# Description

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

e.g.

{[()]} 匹配

{[}] 不匹配

## Sample Input

``````6
1 (
1 )
3
4
2
4
``````

## Sample Output

``````)
YES
NO
``````

## 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() {
}

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

bool isEmpty() {
}

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

}

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;

for (int i = 0; i < num_of_rounds; i++)
{
scanf("%d", &operation);
switch (operation)
{
case 1:
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

``````/*

*/
#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{
}
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;
}
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 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(){
}
void solve(){
char ord[3];
while(n--){
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;
}
``````