外观
3.6 栈的应用:中缀表达式转后缀表达式
算一个式子
计算器要算3+4*2-1。人一眼就看出先算乘法,再从左往右算加和减:
text
3 + 4 * 2 - 1
\___/ 第1步:4*2 = 8
\_______/ 第2步:3+8 = 11
\___________/ 第3步:11-1 = 10可程序是从左往右一个字符一个字符读的。读到3+4,它能马上算出7吗?不能。后面还有一个*,它比+先算,4要先给*用。
读到3+4*2,能先算4*2吗?这回可以,可程序得先读到后面的-,才知道没有比*更先算的了。
再看(3+4)*2。这一回得跳进括号里,先算3+4。
同样是加和乘,先算哪一步,要看后面还有什么运算符、有没有括号。计算的顺序和读的顺序不一样,程序读到一半,不知道手上的数能不能先算。
学完这一节,你能把平常写的式子改写成一种程序好算的写法:先用手改,再写成函数让程序来改。
本节问题能不能换一种写法,让读的顺序就是计算的顺序?
后缀表达式
有一种写法能做到:把运算符写在它的两个运算对象后面。这样写的式子,叫后缀表达式,简称后缀式。
3+4*2-1写成后缀式是:
text
3 + 4 * 2 - 1 → 3 4 2 * + 1 -逐个运算符看,它的两个运算对象都在它前面:
*的两个运算对象是4和2;+的两个运算对象是3和4 2 *;-的两个运算对象是3 4 2 * +和1。
这样一来,从左往右读,每读到一个运算符,它前面最近的两个数就是它的两个运算对象,马上就能算。算出的数替换掉它们,又成了后面运算符的运算对象。
读3 4 2 * + 1 -:*前面最近的是4和2,得8,式子变成3 8 + 1 -;+算3和8,得11;-算11和1,得10。和3+4*2-1一样。
后缀式里,运算符出现的顺序,就是计算的顺序,读到哪就算到哪。这就回答了本节问题。
我们平常写的、运算符夹在两个运算对象中间的式子,叫中缀表达式,简称中缀式。两种写法的区别在运算符的位置,先算谁也就靠不同的东西来定:
| 中缀式 | 后缀式 | |
|---|---|---|
| 运算符写在 | 两个运算对象中间 | 两个运算对象后面 |
| 先算谁,靠 | 优先级和括号 | 运算符出现的顺序 |
| 读的顺序就是计算的顺序 | 不是 | 是 |
拿3+4*2和(3+4)*2对照:
text
3 + 4 * 2 → 3 4 2 * +
(3 + 4) * 2 → 3 4 + 2 *两个中缀式要靠括号分出先算谁。两个后缀式没有括号:*排在前面的,先算乘;+排在前面的,先算加。
后缀式好算,可人平常写的是中缀式。怎么把中缀式变成后缀式?
后缀式也叫逆波兰式
后缀表达式又叫逆波兰表达式,因为把运算符写在前面的"前缀表达式"是波兰数学家卢卡西维茨提出的。一些老式计算器就是让人按后缀式输入的。
手工转换:加括号法
把中缀式变成后缀式,就是把每个运算符从它的两个运算对象中间,挪到它们后面。关键是分清每个运算符的两个运算对象是谁,也就是它管到哪。这要按优先级来定。
人手工转换,常用加括号法:用一对括号把每个运算符和它的两个运算对象圈起来,谁是谁的运算对象,一眼就看清了。一共三步:
- 按先乘除、后加减,一样高的从左往右,给每个运算符和它的两个运算对象加一对括号;
- 把每个运算符挪到它那对括号的右括号后面;
- 去掉所有括号。
拿3+4*2-1来做。
第1步,加括号。*最先算,它的两个运算对象是4和2,圈起来:3+(4*2)-1。接着是+,它左边是3,右边是刚圈好的(4*2),圈起来:(3+(4*2))-1。最后是-,它左边是整个(3+(4*2)),右边是1,圈起来:((3+(4*2))-1)。现在每对括号里,正好是一个运算符和它的两个运算对象。
**第2步,挪运算符。**一次挪一个:
text
((3 + (4 * 2)) - 1)
((3 + (4 2)*) - 1) 挪 *
((3 (4 2)*)+ - 1) 挪 +
((3 (4 2)*)+ 1)- 挪 -**第3步,去括号。**得3 4 2 * + 1 -,和前面写的一样。
再做(3+4)*2。第1步,原来的括号已经管住了3+4,再给乘法加一对,得((3+4)*2);第2步,得((3 4)+ 2)*;第3步,得3 4 + 2 *。
验算一下:照后缀式的读法,+算3和4得7,*算7和2得14。(3+4)*2也是14。
加括号法好用,是因为人一眼能看见整个式子:先找到*,再回头处理+,最后才轮到-。程序不行。它从左往右一个字符一个字符读,读到+时,还不知道后面有没有*,括号没法一次加好。
练习1:哪个是它的后缀式?
单选
中缀式9-4/2+1写成后缀式是哪一个?
A
9 4 2 / - 1 +/最高,先算4/2;-和+一样高,左边的-先算,最后加1。等于8。
B
9 4 2 / 1 + -这是先把4/2和1加起来,再用9减,也就是9-(4/2+1),等于6。-和+一样高,要从左往右,-先加括号。
C
9 4 - 2 / 1 +这是先算9-4,也就是(9-4)/2+1。/的优先级比-高,要先给/加括号。
用加括号法:/最先算,圈起来,得9-(4/2)+1;-和+一样高,从左往右,先圈-再圈+,得((9-(4/2))+1)。挪运算符、去括号,得9 4 2 / - 1 +。
程序转换:从左往右读
和手工转换不同,程序只能从左往右,一个字符一个字符地读。相同的是要做的事:数字的顺序不变,只把每个运算符写到它的两个运算对象后面。
先看数字。3+4*2-1的数字是3、4、2、1,后缀式3 4 2 * + 1 -里还是3、4、2、1。数字的顺序一点没变,读到就能写出去。
难的是运算符:+在中缀式里是第一个,到了后缀式里却排在*后面。程序读到+的时候,它怎么知道+要往后挪、挪到哪?
从左往右读3+4*2-1。
读到3:数字,顺序不变,直接写出去。
读到+:左边是3,右边还没读到。不能写,先放着。
读到4:写出去。那+的第二个运算对象是4吗?还不一定,要看4后面跟的是什么。
读到*:*和/比+和-先算,我们说它们的优先级高。4要先给*用,所以+的第二个运算对象不是4,而是4*2算出来的数。照规定,+要写在4 2 *后面,现在还不能写,接着等。
*自己呢?左边是4,右边还没读到,也不能写,也放着。
现在有两个运算符在等:先放下的+,后放下的*。将来谁先写出去?*。+要用*算出来的数,*不先写出去,+的运算对象就不齐。后放下的先写出去,又是后进先出,所以用一个栈放还没写出去的运算符:
读到2:写出去。输出是3 4 2。
读到-:*在等它的右边。*比-高,2要先给*用,所以*的第二个运算对象就是2。*的两个运算对象4和2都齐了,弹出,写出去。
新的栈顶是+,它在等4*2。+和-一样高,一样高的从左往右算,+先算,所以+的第二个运算对象就是4*2,也齐了。弹出,写出去。
栈空了。-的左边是3+4*2整个算出来的数,右边还没读到,入栈等着。
读到1:写出去。读完了:后面再没有数,-的两个运算对象都齐了,弹出,写出去。
得到3 4 2 * + 1 -,和加括号法得到的一样。
注意读到-这一步:弹出一个还不够。弹完*,要拿新的栈顶+接着和-比,一直比到栈空,或者栈顶比新来的低为止。栈顶比新来的低,就一个也不弹,比如读到*时栈顶是+。一样高也要弹:要是+接着等,就成了3 4 2 * 1 - +,算的是3+(8-1)。在这个式子里碰巧也是10,换成8-2-1就不对了:8 2 1 - -算的是8-(2-1) = 7,应该是5。
把做过的事收拢成三条:
- 读到数字:直接写出去。
- 读到运算符:栈顶比它高或一样高,就弹出写出去,再看新的栈顶;直到栈空,或者栈顶比它低,再把它入栈。
- 读完了:栈里剩下的依次弹出写出去。
第2条保证了:每个运算符入栈时,栈顶都比它低。所以栈里从下往上,优先级一个比一个高,栈顶永远是最该先写出去的那个。用栈是对的。
写成伪代码("输出"就是写到后缀式的末尾):
text
InitStack(S)
for 中缀式里的每个字符 c:
if c 是数字:
输出 c
else: // c 是运算符
while 栈不空 且 栈顶优先级 >= c 的优先级:
Pop(S, &t); 输出 t // 栈顶的两个运算对象齐了,写出去
Push(S, c) // c 放着,等它右边的数
while not StackEmpty(S): // 读完了,剩下的依次写出去
Pop(S, &t); 输出 twhile也是循环:条件成立就一直做,不成立就停。和for不同,它事先不知道要做几次,读到-时弹了两次,读到*时一次也没弹。
和3.5节对照:括号匹配的栈里放的是"还没配上的左括号",这里放的是"还没写出去的运算符"。
程序转换:括号
再加上括号。拿(3+4)*2看:括号里的3+4本身就是一个没有括号的小式子,前面的办法就能转,得3 4 +。整个式子是它的结果再乘2,写成3 4 + 2 *。所以括号不用新办法,只要让括号里的小式子单独转一遍。
读到(:一个小式子开始了。把(入栈,当一堵墙。墙上面就像一个新的空栈:括号里的运算符入栈前只和墙上面的比,碰到(就停,好像墙下面什么都没有。
读到):小式子读完了。照前面第3条,读完了就把栈里剩下的依次弹出写出去,只是这回只弹到墙为止。再把(弹掉,它不写出去,后缀式里没有括号。
拿规定核对一下:*的左边是(3+4)整个,所以*之前,+必须已经写出去。读到)时弹出+,正好做到了。
读到),找的是最近的那个(,就是3.5节括号匹配的做法。
把括号加进伪代码:
text
InitStack(S)
for 中缀式里的每个字符 c:
if c 是数字:
输出 c
else if c 是 '(':
Push(S, c) // 小式子开始:当墙
else if c 是 ')':
while 栈顶不是 '(':
Pop(S, &t); 输出 t // 小式子读完:弹到墙为止
Pop(S, &t) // 弹出 '(',不输出
else: // c 是运算符
while 栈不空 且 栈顶不是 '(' 且 栈顶优先级 >= c 的优先级:
Pop(S, &t); 输出 t
Push(S, c)
while not StackEmpty(S):
Pop(S, &t); 输出 t写成程序
栈里放的是'+'、'('这些字符。不用像3.5节那样把栈改成char:字符在C里就是一个小整数('+'是43),int放得下,3.3节的顺序栈原样拿来用。
为了把力气花在栈上,约定每个数只有一位,也就是0到9。这样后缀式里不用空格分开,342*+1-就是3 4 2 * + 1 -。
先写优先级,数越大越先算:
c
int Prec(int op) {
if (op == '*' || op == '/') return 2;
if (op == '+' || op == '-') return 1;
return 0;
}再照伪代码,在main里把3+4*2-1转一遍。伪代码里的"输出",就是用printf打印一个字符(%c表示按字符打印):
c
int main(void) {
char in[] = "3+4*2-1";
SeqStack S;
int t;
InitStack(&S);
for (int i = 0; in[i] != '\0'; i++) {
char c = in[i];
if (c >= '0' && c <= '9') {
printf("%c", c); /* 数字:直接输出 */
} else if (c == '(') {
Push(&S, c); /* 左括号:入栈当墙 */
} else if (c == ')') {
while (GetTop(&S, &t) && t != '(') { /* 弹到左括号为止 */
Pop(&S, &t);
printf("%c", t);
}
Pop(&S, &t); /* 弹出左括号,不输出 */
} else { /* 运算符 */
while (GetTop(&S, &t) && t != '(' && Prec(t) >= Prec(c)) {
Pop(&S, &t); /* 栈顶一样高或更高:先写出去 */
printf("%c", t);
}
Push(&S, c); /* 自己入栈等着 */
}
}
while (Pop(&S, &t)) /* 读完了:剩下的依次写出去 */
printf("%c", t);
printf("\n");
return 0;
}伪代码里的"栈不空"和"栈顶",用一个GetTop就都有了:栈空它返回0,while停下;不空就把栈顶放进t。
运行结果:
text
342*+1-把in换成"(3+4)*2",输出34+2*,和前面手工转换的一样。
完整的程序放在下面,可以直接复制运行:
c
#include <stdio.h>
#define MAXSIZE 100
typedef struct {
int data[MAXSIZE];
int top;
} SeqStack;
void InitStack(SeqStack *S) {
S->top = 0;
}
int StackEmpty(SeqStack *S) {
return S->top == 0;
}
int Push(SeqStack *S, int x) {
if (S->top == MAXSIZE) return 0;
S->data[S->top] = x;
S->top++;
return 1;
}
int Pop(SeqStack *S, int *x) {
if (S->top == 0) return 0;
S->top--;
*x = S->data[S->top];
return 1;
}
int GetTop(SeqStack *S, int *x) {
if (S->top == 0) return 0;
*x = S->data[S->top - 1];
return 1;
}
int Prec(int op) {
if (op == '*' || op == '/') return 2;
if (op == '+' || op == '-') return 1;
return 0;
}
int main(void) {
char in[] = "3+4*2-1";
SeqStack S;
int t;
InitStack(&S);
for (int i = 0; in[i] != '\0'; i++) {
char c = in[i];
if (c >= '0' && c <= '9') {
printf("%c", c); /* 数字:直接输出 */
} else if (c == '(') {
Push(&S, c); /* 左括号:入栈当墙 */
} else if (c == ')') {
while (GetTop(&S, &t) && t != '(') { /* 弹到左括号为止 */
Pop(&S, &t);
printf("%c", t);
}
Pop(&S, &t); /* 弹出左括号,不输出 */
} else { /* 运算符 */
while (GetTop(&S, &t) && t != '(' && Prec(t) >= Prec(c)) {
Pop(&S, &t); /* 栈顶一样高或更高:先写出去 */
printf("%c", t);
}
Push(&S, c); /* 自己入栈等着 */
}
}
while (Pop(&S, &t)) /* 读完了:剩下的依次写出去 */
printf("%c", t);
printf("\n");
return 0;
}练习2:栈里是什么?
填空
把中缀式2*(3+4)-5转成后缀式,从左往右读。
- 读完
)之后,已经输出的是 - 这时栈里只剩一个运算符
- 最后得到的后缀式是
2写出去,*和(入栈。3写出去;+来时栈顶是(,入栈。4写出去。读到),弹出+写出去,再弹出(,输出是234+,栈里只剩*。读到-,栈顶*比它高,弹出写出去,-入栈。5写出去。读完,弹出-。结果是234+*5-。
到这里你有了后缀表达式:运算符写在两个运算对象后面,没有优先级和括号,读的顺序就是计算的顺序。中缀转后缀,就是给每个运算符找它的两个运算对象:人能看见整个式子,用加括号法;程序从左往右读,运算符先放进栈里等,新运算符来时,把栈顶优先级一样高或更高的依次弹出写出去;括号里是一个小式子,(入栈当墙,)就是小式子读完了,弹到(为止。下一步后缀式拿到了。程序怎么从左往右读一遍,就算出它的值?