外观
3.5 栈的应用:括号匹配
括号配对吗
写程序时,括号总是成对出现:圆括号()、方括号[]、花括号{}。编辑器会把配成一对的括号标出来;少了一个、多了一个,编译器就报错。
比如这一行:
text
a [ ( b + c ) * d ]
│ └───────┘ │
└───────────────┘圆括号配圆括号,方括号配方括号,里面的一对整个套在外面那一对里。这一行是配对的。
下面三行都不配对,错法各不相同:
(]:类型对不上,圆括号碰上了方括号。()):右括号多了一个,最后那个)找不到左括号。(():左括号多了一个,第一个(一直没等到右括号。
学完这一节,你能写出一个函数,读进一行字,判断里面的括号配不配对。
本节问题程序从左往右读一行字,怎么判断括号配不配对?
方法一:数个数
先只看圆括号。读(()()),它配对吗?
一个直接的想法:数一数还有几个左括号没配上。读到左括号,个数加1;读到右括号,配掉一个,个数减1。把读完每个字符之后的个数,写在这个字符下面:
text
字符 ( ( ) ( ) )
个数 1 2 1 2 1 0读完时个数是0,所有左括号都配上了,配对。
再看两个错例。先看()):
text
字符 ( ) )
个数 1 0 ?读到第二个)时,个数已经是0,前面没有还没配上的左括号,这个)配不上。右括号多了,表现为减之前个数已经是0。
再看(():
text
字符 ( ( )
个数 1 2 1读完时个数是1,还有一个左括号没配上。左括号多了,表现为读完时个数不是0。
于是得到方法一:用一个数count,记还没配上的左括号有几个。
text
count = 0
for s 里的每个字符 c:
if c 是 '(':
count = count + 1
else if c 是 ')':
if count == 0: return 不配对 // 右括号多了
count = count - 1
return count == 0 // 不是0,就是左括号多了这是伪代码:有循环、if和return,结构和C一样,但条件用中文说,先不管C怎么写。
只有圆括号时,这个办法完全够用。
方法二:配给最近的那一个
现在加上方括号。读([)],照方法一,圆括号、方括号各数各的:
text
字符 ( [ ) ]
圆括号个数 1 1 0 0
方括号个数 0 1 1 0两个数都没有在0的时候再减,读完也都是0。照方法一,这一行配对。可它不配对:)来的时候,(和它之间还夹着一个没配上的[。
问题出在哪?个数只说了"还有几个没配上",没说"最近一个没配上的是哪种括号"。而)该配谁,恰恰要看这个。
那就看看,读到右括号时,它到底该配谁。读a[(b+c)*d],把还没配上的左括号按读到的先后摞起来,后读到的放上面:
读到)时,摞着的是[和(。)配的是(,也就是上面那个、最近读到的那个。配上就拿走。再读到],最上面剩下[,正好配上。
括号一层套一层,里面的一对必须先合上,外面的才能合上。所以:
右括号总是和最近一个还没配上的左括号配
最近的先配,就是后进先出。刚才那一摞,就是一个栈:还没配上的左括号入栈;读到右括号,出栈一个,看是不是一对。
写成伪代码:
text
InitStack(S)
for s 里的每个字符 c:
if c 是左括号:
Push(S, c) // 等着配
else if c 是右括号:
if StackEmpty(S): return 不配对 // 右括号多了
Pop(S, &left) // 最近一个没配上的左括号
if left 和 c 不是一对: return 不配对 // 类型对不上
return StackEmpty(S) // 栈不空,就是左括号多了和方法一对照着看:count加1换成了Push,count减1换成了Pop,count == 0换成了StackEmpty。方法一的count,其实就是栈的高度。只有一种括号时,栈里放的都一样,记住高度就够了;括号一多,就得记住每一层放的是什么。
三种错,在哪一步发现
再看开头的三行错例。每一种错,都对应伪代码里的一个return:
类型对不上,在读到右括号、出栈之后发现:(]里,]让(出栈,两个不是一对。对应if left 和 c 不是一对那一行。
右括号多了,在读到右括号、栈却是空的时候发现:())里,第一个)已经把(配掉了,第二个)来时栈里什么都没有。对应if StackEmpty(S)那一行。
左括号多了,要读完才发现:(()里,读到最后,栈里还剩一个(。读的过程中看不出来,因为后面也许还会有右括号。对应最后一行return StackEmpty(S)。
三种错各有一个return把守,一种都不会漏。
写成函数
照方法二的伪代码,一行一行写成C。
栈要放的是括号,也就是字符。3.3节的顺序栈放的是int,要把元素换成char:结构体里的data,Push、Pop、GetTop的参数x,一共四处,把int改成char。五个函数的写法一个字都不用动。
只改一处:typedef
如果当初写typedef int ElemType;,所有放元素的地方都写ElemType,换类型时只要把这一行改成typedef char ElemType;。很多教材就这样写。
先写一个小函数,判断两个括号是不是一对:
c
int Pair(char left, char right) {
return (left == '(' && right == ')') ||
(left == '[' && right == ']') ||
(left == '{' && right == '}');
}再照伪代码写Match,每一行都对得上。"c 是左括号"写成三个比较,"left 和 c 不是一对"交给Pair。配对返回1,不配对返回0:
c
int Match(char *s) {
SeqStack S;
char left;
InitStack(&S);
for (int i = 0; s[i] != '\0'; i++) {
char c = s[i];
if (c == '(' || c == '[' || c == '{') {
if (!Push(&S, c)) return 0; /* 左括号:入栈(栈满就当不配对) */
} else if (c == ')' || c == ']' || c == '}') {
if (!Pop(&S, &left)) return 0; /* 栈空:右括号多了 */
if (!Pair(left, c)) return 0; /* 出栈的左括号和它不是一对 */
}
}
return StackEmpty(&S); /* 读完栈空,才算配对 */
}Match只调用了InitStack、Push、Pop、StackEmpty,没有碰过data和top。所以把顺序栈换成3.4节的链栈,Match也一个字都不用改。
用几行字试一试:
c
int main(void) {
char *tests[] = {"a[(b+c)*d]", "(]", "())", "(()", "{[()()]}", "([)]", ""};
for (int i = 0; i < 7; i++)
printf("\"%s\" %s\n", tests[i], Match(tests[i]) ? "配对" : "不配对");
return 0;
}运行结果:
text
"a[(b+c)*d]" 配对
"(]" 不配对
"())" 不配对
"(()" 不配对
"{[()()]}" 配对
"([)]" 不配对
"" 配对没有括号的空串也算配对:栈从头到尾都是空的。
栈会满
栈只有MAXSIZE个格子。左括号一口气套了100层以上,Push就放不下了,Match会把它当成不配对。真要处理这么深的嵌套,把MAXSIZE改大,或者换成链栈。
完整的程序放在下面,可以直接复制运行:
c
#include <stdio.h>
#define MAXSIZE 100
typedef struct {
char data[MAXSIZE];
int top;
} SeqStack;
void InitStack(SeqStack *S) {
S->top = 0;
}
int StackEmpty(SeqStack *S) {
return S->top == 0;
}
int Push(SeqStack *S, char x) {
if (S->top == MAXSIZE) return 0;
S->data[S->top] = x;
S->top++;
return 1;
}
int Pop(SeqStack *S, char *x) {
if (S->top == 0) return 0;
S->top--;
*x = S->data[S->top];
return 1;
}
int GetTop(SeqStack *S, char *x) {
if (S->top == 0) return 0;
*x = S->data[S->top - 1];
return 1;
}
int Pair(char left, char right) {
return (left == '(' && right == ')') ||
(left == '[' && right == ']') ||
(left == '{' && right == '}');
}
int Match(char *s) {
SeqStack S;
char left;
InitStack(&S);
for (int i = 0; s[i] != '\0'; i++) {
char c = s[i];
if (c == '(' || c == '[' || c == '{') {
if (!Push(&S, c)) return 0; /* 左括号:入栈(栈满就当不配对) */
} else if (c == ')' || c == ']' || c == '}') {
if (!Pop(&S, &left)) return 0; /* 栈空:右括号多了 */
if (!Pair(left, c)) return 0; /* 出栈的左括号和它不是一对 */
}
}
return StackEmpty(&S); /* 读完栈空,才算配对 */
}
int main(void) {
char *tests[] = {"a[(b+c)*d]", "(]", "())", "(()", "{[()()]}", "([)]", ""};
for (int i = 0; i < 7; i++)
printf("\"%s\" %s\n", tests[i], Match(tests[i]) ? "配对" : "不配对");
return 0;
}练习1:在哪一步停下?
填空
用Match判断{[(])},从左往右读。
- 读第4个字符
]时,出栈的是 - 所以这一行
- Match在第 个字符就返回了,后面的
)}没有再读
前三个字符{[(都是左括号,依次入栈,栈顶是(。第4个字符]让(出栈,(和]不是一对,Match马上返回0,后面两个字符不再读。
练习2:哪些配对?
多选
下面哪些是配对的?
A
([]{})(入栈;[入栈又被]配掉;{入栈又被}配掉;最后)配掉(,栈空。
B
(()读完栈里还剩一个(,左括号多了。
C
([)]读到)时,出栈的是[,不是一对。左右括号个数虽然相等,也不配对。
D
{}[]()三对挨着排,每对都是刚入栈就被配掉。
E
)(第一个字符)来时栈是空的,右括号多了。
判断的办法:右括号总是和最近一个还没配上的左括号配,读完栈要空。只数个数不够,([)]就是反例。
到这里你有了用栈判断括号配对:左括号入栈,右括号出栈配对,读完栈空才算配对。三种错各在固定的地方被发现。Match只调用栈的操作,换哪种栈都不用改。下一步用栈算出一个式子的值。