十月一日快到了，LittleX想了个国庆节的娱乐节目——拆包装盒大赛。这礼物可没那么简单，为了娱乐大众，LittleX准备了一堆盒子，其中有的盒子里有装礼物，有的盒子里面可以再放零个或者多个盒子。假设放礼物的盒子里不再放其他盒子。用()表示一个盒子，B表示礼物，LittleX想让你帮他算出最少需要拆多少个盒子才能拿到礼物。
本题目包含多组测试，请处理到文件结束。 每组测试包含一个长度不大于1000，只包含'('、')'和'B'三种字符的字符串，代表LittleX设计的礼物透视图。 你可以假设，每个透视图画的都是合法的。
对于每组测试，请在一行里面输出最少需要拆多少个盒子。
用链栈实现：
#include <iostream> #include<stdio.h> #include<string.h> const int MAX=1001; using namespace std; class Stack { private: struct node { char data; node* next; node() { next=NULL; } }; node* head; public: Stack() { head=new node; } void push(char c) { node* s=new node; s->data=c; s->next=head; head=s; } char pop() { char c='\0'; if(head!=NULL) { node* temp=head; c=head->data; head=head->next; delete temp; } return c; } int Length() { int length=0; node* p=head; while(p->next&&++length) { // length++; p=p->next; } return length; } bool isEmpty() { return head->next==NULL?true:false; } }; int main() { char str[MAX]; while(cin>>str) { Stack* stack=new Stack(); for(int i=0; i<strlen(str); i++) { if(str[i]=='(') stack->push(str[i]); else if(str[i]==')') stack->pop(); else if(str[i]=='B') break; } cout<<stack->Length()<<endl; delete stack; } return 0; }
用顺序栈实现：
#include <iostream> #include<stdio.h> #include<string.h> const int MAX=1001; using namespace std; class Stack{ private: int top; char data[MAX]; public: Stack(){ top=-1; } void push(char c){ if(top!=MAX-1){ data[++top]=c; } } char pop(){ char c='\0'; if(top!=-1){ c=data[top--]; } return c; } int getTop(){ return top; } bool isEmpty(){ return top==-1?true:false; } }; int main(){ char str[MAX]; while(cin>>str){ Stack* stack=new Stack(); for(int i=0;i<strlen(str);i++){ if(str[i]=='(') stack->push(str[i]); else if(str[i]==')') stack->pop(); else if(str[i]=='B') break; } cout<<stack->getTop()+1<<endl; delete stack; } return 0; }
