检查一段C语言代码的小括号( )、 中括号 [ ] 和大括号{ } 是否匹配。

输入格式:

在一行中输入一段C语言代码,长度不超过1000个字符(行末以换行符结束)。

输出格式:

第一行输出左括号的数量和右括号的数量,中间以一个空格间隔。
若括号是匹配的,在第二行打印YES,否则打印NO

输入样例1:

1
for(int i=0; i<v; i++){ visited[i] = 0; for(int j=0; j<v; j++) scanf("%d",&(g->Adj[i][j])); }

输出样例1:

1
2
8 8
YES

输入样例2:

1
for(int i=0; i<v; i++) a(i]=0;

输出样例2:

1
2
2 2
NO
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <iostream>
#include <stack>

using namespace std;

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

bool is_right_kuohao(char ch)
{
return ch == ')' ch == ']' ch == '}';
}

bool match(char left, char right)
{
return (left == '(' && right == ')')
(left == '[' && right == ']')
(left == '{' && right == '}');
}

int main()
{
string line;
getline(cin, line);

int left_kuohao_count = 0;
int right_kuohao_count = 0;

for (int i = 0; i < line.length(); i++)
{
if (is_left_kuohao(line[i]))
left_kuohao_count += 1;
if (is_right_kuohao(line[i]))
right_kuohao_count += 1;
}

cout << left_kuohao_count << " "
<< right_kuohao_count << endl;

stack<char> left_kuohaos;

for (int i = 0; i < line.length(); i++)
{
if (is_left_kuohao(line[i]))
left_kuohaos.push(line[i]);
if (is_right_kuohao(line[i]))
{
if (!left_kuohaos.empty() && match(left_kuohaos.top(), line[i]))
left_kuohaos.pop();
else
{
cout << "NO" << endl;
return 0;
}
}
}
if (left_kuohaos.empty())
cout << "YES" << endl;
else
cout << "NO" << endl;

return 0;
}

假设以SX分别表示入栈和出栈操作。如果根据一个仅由SX构成的序列,对一个空堆栈进行操作,相应操作均可行(如没有出现删除时栈空)且最后状态也是栈空,则称该序列是合法的堆栈操作序列。请编写程序,输入SX序列,判断该序列是否合法。

输入格式:

输入第一行给出两个正整数N和M,其中N是待测序列的个数,M(≤50)是堆栈的最大容量。随后N行,每行中给出一个仅由SX构成的序列。序列保证不为空,且长度不超过100。

输出格式:

对每个序列,在一行中输出YES如果该序列是合法的堆栈操作序列,或NO如果不是。

输入样例:

1
2
3
4
5
4 10
SSSXXSXXSX
SSSXXSXXS
SSSSSSSSSSXSSXXXXXXXXXXX
SSSXXSXXX

输出样例:

1
2
3
4
YES
NO
NO
NO
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
#include<iostream>
#include<string>
using namespace std;

#define MAXSIZE 100
#define ADDSIZE 10
typedef int Status;
typedef char SElemType;

typedef struct {
SElemType *base;
SElemType *top;
int stacksize;
} SqStack;

Status Initstack(SqStack &s,int e=MAXSIZE)
{
s.base=new SElemType[e];
s.top=s.base;
s.stacksize=e;
return 1;
}


Status push(SElemType e,SqStack &s)
{
if(s.top-s.base>=s.stacksize)
{
/*s.base=(SElemType*)realloc(s.base,(s.stacksize+ADDSIZE)* sizeof(SElemType));
if(!s.base)
exit(EOVERFLOW);
s.top=s.base+s.stacksize;
s.stacksize+=ADDSIZE;*/
return 0;
}
*s.top++=e;
return 1;
}

Status pop(SElemType &e,SqStack &s)
{
if(s.top==s.base)return 0;
e=*--s.top;
return 1;
}

Status GetTop(SElemType &e,SqStack &s)
{
if(s.top==s.base)return 0;
e=*(s.top-1);
return 1;
}

bool Isright(string s,int e)
{
int i=0,f=1;
SqStack sq;
Initstack(sq,e);
while (s[i] != '\0')
{
if(s[i]=='S') {
if (push(s[i],sq) == 1)
i++;
else
{
f = 0;
break;
}
}
else {
if (pop(s[i],sq) == 1)
i++;
else {
f = 0;
break;
}
}
}
if(sq.top==sq.base&&s[i]=='\0')
f=1;
else
f=0;
return f == 1;
}
bool IsRight(string s,int L)
{
int i=0,flag=1;
SqStack sq;
Initstack(sq,L);
while(s[i]!='\0')
{
if(s[i]=='S')
{
if(push(s[i],sq)==1)
i++;
else
{
flag=0;
break;
}
}
else
{
if(pop(s[i],sq)==1)
i++;
else
{
flag=0;
break;
}
}
}
if((sq.top==sq.base) && s[i]=='\0')
flag=1;
else
flag=0;
return flag == 1;
}

int main()
{
int m,n;
string ss;
cin>>m>>n;
for (int u = 0; u < m; ++u) {
cin>>ss;
if (IsRight(ss,n)== true)
cout<<"YES"<<endl;
else
cout<<"NO"<<endl;
}
}

下面以(a+b)*c为例子进行说明:(a+b)*c的逆波兰式为ab+c*,假设计算机把ab+c*按从左到右的顺序压入栈中,并且按照遇到运算符就把栈顶两个元素出栈,执行运算,得到的结果再入栈的原则来进行处理,那么ab+c*的执行结果如下:1)a入栈(0位置)2)b入栈(1位置)3)遇到运算符“+”,将a和b出栈,执行a+b的操作,得到结果d=a+b,再将d入栈(0位置)4)c入栈(1位置)5)遇到运算符“*”,将d和c出栈,执行d*c的操作,得到结果e,再将e入栈(0位置)经过以上运算,计算机就可以得到(a+b)*c的运算结果e了。逆波兰式除了可以实现上述类型的运算,它还可以派生出许多新的算法,数据结构,这就需要灵活运用了。逆波兰式只是一种序列体现形式。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
int precede(char op)
{ int x;
switch(op)
{
case '*': x=2; break;
case '/': x=2; break;
case '+': x=1; break;
case '-': x=1; break;
default : x=0;
}
return x;
}
char *RPExpression(char *e)
{/* 返回表达式e的逆波兰式 */
char *c;
c=(char*)malloc(sizeof(char)*20); //不能用char c[]
Stack s1;
InitStack(s1);
int i=0,j=0;
char ch;
Push(s1,'@');
ch=e[i++];
while(ch!= 0)
{
if(ch=='(')
{
Push(s1,ch);
ch=e[i++];
}
else if(ch==')')
{
while(Top(s1)!='(')
{
Pop(s1,c[j++]);
}
/* to[j++]=pop(&s1);*/
Pop(s1,ch);
ch=e[i++];
}
else if(ch=='+'ch=='-'ch=='*'ch=='/')
{
char w;
w=Top(s1);
while(precede(w)>=precede(ch))
{
Pop(s1,c[j++]);
w=Top(s1);
}
Push(s1,ch);
ch=e[i++];
}
else
{
//while((ch<='z'&&ch>='a')(ch<='Z' && ch>='A')){
c[j++]=ch;
ch=e[i++];
//}
//c[j++]=' ';
}
}
Pop(s1,ch);
while(ch!='@')
{
c[j++]=ch;
Pop(s1,ch);
}
//c[j++]=;
c[j++]=0;
return c;
}

已知两个非降序链表序列S1与S2,设计函数构造出S1与S2合并后的新的非降序链表S3。

输入格式:

输入分两行,分别在每行给出由若干个正整数构成的非降序序列,用−1表示序列的结尾(−1不属于这个序列)。数字用空格间隔。

输出格式:

在一行中输出合并后新的非降序链表,数字间用空格分开,结尾不能有多余空格;若新链表为空,输出NULL

输入样例:

1
2
1 3 5 -1
2 4 6 8 10 -1

输出样例:

1
1 2 3 4 5 6 8 10
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
#include <iostream>
#include <malloc.h>
using namespace std;
typedef int Status;
typedef int Elemtype;
typedef struct LNode
{
Elemtype data;
LNode *next;
}LNode,*LinkList;

LinkList endCreate()
{
LinkList L,p,s;
Elemtype e;
L=(LinkList)malloc(sizeof(LNode));
L->next=NULL;
p=L;
cin>>e;
while (e!=-1)
{
s=(LinkList)malloc(sizeof(LNode));
s->data=e;
p->next=s;
p=s;
cin>>e;
}
p->next=NULL;
return L;
}

LinkList headCreate()
{
LinkList L,s;
Elemtype e;
L=(LinkList)malloc(sizeof(LNode));
L->next=NULL;
cin>>e;
while (e!=-1)
{
s=(LinkList)malloc(sizeof(LNode));
s->data=e;
s->next=L->next;
L->next=s;
cin>>e;
}
return L;
}

void print(LinkList list)
{
LinkList e;
e=list->next;
if(!e)
{
cout<<"NULL";
} else {
while (e->next) {
cout << e->data << " ";
e = e->next;
}
cout << e->data;
}
}
void merge(LinkList L1,LinkList L2,LinkList &L3)
{
LinkList l1=L1->next,l2=L2->next,l3;
l3=L3=L1;
while (l1&&l2)
{
if (l1->data<=l2->data)
{
l3->next=l1;
l3=l1;
l1=l1->next;
} else
{
l3->next=l2;
l3=l2;
l2=l2->next;
}
}
l3->next=l1?l1:l2;
}
int main()
{
LinkList L1,L2,L3;
L1=endCreate();
L2=endCreate();
merge(L1,L2,L3);
print(L3);
}

这道题两点重点,第一是实现merge操作。传进去两个链表和第三个的引用,然后一直判断直到某一个结束,如果L3后边是L1说明L1还有剩下的,如果不是说明剩下的都是L2后边;

第二个是输出,需要注意如果是空就输出NULL,他是让打印出NULL而不是return。。。