外观
3.7 栈的应用:后缀表达式求值
读到哪算到哪
3.6节说过,后缀式读的顺序就是计算的顺序,人从左往右就能读出它的值。现在让程序来算。
学完这一节,你能写出一个函数,读进一个后缀式,算出它的值。接上3.6节的ToPostfix,就是一个计算器。
本节问题程序怎么从左往右读一遍后缀式,就算出它的值?
从左往右读3 4 2 * +,看看程序怎么算。
读到3、4、2,都是数,先放着。读到*,它要用哪两个数?是4和2,最后放下的那两个。算出8,放回去,等着后面用。读到+,要用的是3和8,又是最后放下的那两个。算出11。
每个运算符要用的,总是最近放下的两个数。最近的先用,就是后进先出。所以用一个栈放数:
读完了,栈里只剩一个数11,它就是结果。
写成伪代码:
text
InitStack(S)
for 后缀式里的每个字符 c:
if c 是数字:
Push(S, c 代表的数)
else: // c 是运算符
Pop(S, &b) // 先弹出的是右边的数
Pop(S, &a) // 再弹出左边的数
Push(S, a c b) // 算好放回去
Pop(S, &result)
return result和3.5节对照:括号匹配的栈里放的是"还没配上的左括号",这里放的是"还没用上的数"。都是先放着,等后面的东西来取最近的那一个。3.6节转换时,栈里放的是"还没写出去的运算符"。
先弹出的是右边的数
加法和乘法,两个数谁在左谁在右都一样。减法和除法不一样。算8 2 -:
8先入栈,2后入栈,2在栈顶。先弹出来的是2,它是减号右边的数;后弹出来的8是左边的数。所以是8 - 2 = 6,不是2 - 8。伪代码里先Pop(S, &b)、再Pop(S, &a),算的是a c b,就是这个原因。
再看式子写错的两种情况。
运算符多了,比如3 +:读到+时栈里只有一个3,第二次Pop弹不出来。
数字多了,比如3 4:读完了,栈里还剩两个数,没有运算符把它们合起来,不知道哪个是结果。
把这两处检查加进伪代码:
text
InitStack(S)
for 后缀式里的每个字符 c:
if c 是数字:
Push(S, c 代表的数)
else:
if 弹不出 b 或弹不出 a: return 写错了 // 运算符多了
Push(S, a c b)
Pop(S, &result)
if not StackEmpty(S): return 写错了 // 数字多了
return result写成函数
照伪代码写成C。栈里放的是数,3.3节的顺序栈原样拿来用,元素就是int。
照3.6节的约定,每个数只有一位,也就是0到9。字符'7'和整数7不一样,c - '0'把数字字符变成它代表的数:字符'0'到'9'在编码里是连着的,'7' - '0'正好是7。除法用C的整数除法,9 / 2得4。
式子写错了,函数要能说出来,所以结果用参数带回,返回值说算没算成,和3.2节的Pop一个道理:
c
int Eval(char *s, int *result) {
SeqStack S;
int a, b;
InitStack(&S);
for (int i = 0; s[i] != '\0'; i++) {
char c = s[i];
if (c >= '0' && c <= '9') {
if (!Push(&S, c - '0')) return 0; /* 数字:入栈 */
} else {
if (!Pop(&S, &b)) return 0; /* 先弹出的是右边的数 */
if (!Pop(&S, &a)) return 0; /* 再弹出左边的数;弹不出就是运算符多了 */
int v;
if (c == '+') v = a + b;
else if (c == '-') v = a - b;
else if (c == '*') v = a * b;
else if (c == '/' && b != 0) v = a / b;
else return 0; /* 除以0,或者不认识的字符 */
Push(&S, v); /* 算出的数放回去 */
}
}
if (!Pop(&S, result)) return 0; /* 空串:没有结果 */
return StackEmpty(&S); /* 还剩数,就是数字多了 */
}比伪代码多了两处:除数是0不能算;读到不认识的字符,也当写错了。
用几个式子试一试:
c
int main(void) {
char *tests[] = {"342*+", "34+2*", "82-", "92/3+", "512+4*+3-", "3+", "34", ""};
int v;
for (int i = 0; i < 8; i++) {
if (Eval(tests[i], &v)) printf("\"%s\" = %d\n", tests[i], v);
else printf("\"%s\" 写错了\n", tests[i]);
}
return 0;
}运行结果:
text
"342*+" = 11
"34+2*" = 14
"82-" = 6
"92/3+" = 7
"512+4*+3-" = 14
"3+" 写错了
"34" 写错了
"" 写错了完整的程序放在下面,可以直接复制运行:
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 Eval(char *s, int *result) {
SeqStack S;
int a, b;
InitStack(&S);
for (int i = 0; s[i] != '\0'; i++) {
char c = s[i];
if (c >= '0' && c <= '9') {
if (!Push(&S, c - '0')) return 0; /* 数字:入栈 */
} else {
if (!Pop(&S, &b)) return 0; /* 先弹出的是右边的数 */
if (!Pop(&S, &a)) return 0; /* 再弹出左边的数;弹不出就是运算符多了 */
int v;
if (c == '+') v = a + b;
else if (c == '-') v = a - b;
else if (c == '*') v = a * b;
else if (c == '/' && b != 0) v = a / b;
else return 0; /* 除以0,或者不认识的字符 */
Push(&S, v); /* 算出的数放回去 */
}
}
if (!Pop(&S, result)) return 0; /* 空串:没有结果 */
return StackEmpty(&S); /* 还剩数,就是数字多了 */
}
int main(void) {
char *tests[] = {"342*+", "34+2*", "82-", "92/3+", "512+4*+3-", "3+", "34", ""};
int v;
for (int i = 0; i < 8; i++) {
if (Eval(tests[i], &v)) printf("\"%s\" = %d\n", tests[i], v);
else printf("\"%s\" 写错了\n", tests[i]);
}
return 0;
}接成计算器
3.6节的ToPostfix把中缀式变成后缀式,Eval算后缀式。两个接起来,就是计算器:
c
int main(void) {
char *tests[] = {"3+4*2-1", "(3+4)*2", "8-2-1", "9/(1+2)", "2*(3+4)-5", "(3+4", "3+4)", "3++4"};
char post[MAXSIZE];
int v;
for (int i = 0; i < 8; i++) {
if (!ToPostfix(tests[i], post)) printf("%-10s 括号不配对\n", tests[i]);
else if (!Eval(post, &v)) printf("%-10s → %-8s 写错了\n", tests[i], post);
else printf("%-10s → %-8s = %d\n", tests[i], post, v);
}
return 0;
}运行结果:
text
3+4*2-1 → 342*+1- = 10
(3+4)*2 → 34+2* = 14
8-2-1 → 82-1- = 5
9/(1+2) → 912+/ = 3
2*(3+4)-5 → 234+*5- = 9
(3+4 括号不配对
3+4) 括号不配对
3++4 → 3+4+ 写错了3++4转换得出3+4+,Eval读到第一个+时栈里只有一个3,报出写错了。
教材里的"两个栈"
严蔚敏《数据结构》里的表达式求值,用一个运算符栈、一个数栈,读一遍就算出结果。它就是把3.6节和这一节的两步并成一步:本来要把运算符"写出去",改成马上从数栈弹出两个数算好,结果放回数栈。
完整的程序放在下面,可以直接复制运行:
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 Eval(char *s, int *result) {
SeqStack S;
int a, b;
InitStack(&S);
for (int i = 0; s[i] != '\0'; i++) {
char c = s[i];
if (c >= '0' && c <= '9') {
if (!Push(&S, c - '0')) return 0; /* 数字:入栈 */
} else {
if (!Pop(&S, &b)) return 0; /* 先弹出的是右边的数 */
if (!Pop(&S, &a)) return 0; /* 再弹出左边的数;弹不出就是运算符多了 */
int v;
if (c == '+') v = a + b;
else if (c == '-') v = a - b;
else if (c == '*') v = a * b;
else if (c == '/' && b != 0) v = a / b;
else return 0; /* 除以0,或者不认识的字符 */
Push(&S, v); /* 算出的数放回去 */
}
}
if (!Pop(&S, result)) return 0; /* 空串:没有结果 */
return StackEmpty(&S); /* 还剩数,就是数字多了 */
}
int Prec(int op) {
if (op == '*' || op == '/') return 2;
if (op == '+' || op == '-') return 1;
return 0; /* 不是运算符 */
}
int ToPostfix(char *in, char *out) {
SeqStack S;
int t, k = 0;
InitStack(&S);
for (int i = 0; in[i] != '\0'; i++) {
char c = in[i];
if (c >= '0' && c <= '9') {
out[k++] = c; /* 数字:直接输出 */
} else if (c == '(') {
if (!Push(&S, c)) return 0; /* 左括号:入栈当墙 */
} else if (c == ')') {
while (GetTop(&S, &t) && t != '(') { /* 弹到左括号为止 */
Pop(&S, &t);
out[k++] = t;
}
if (!Pop(&S, &t)) return 0; /* 弹不到左括号:右括号多了 */
} else if (Prec(c) > 0) {
while (GetTop(&S, &t) && t != '(' && Prec(t) >= Prec(c)) {
Pop(&S, &t); /* 栈顶一样高或更高:先写出去 */
out[k++] = t;
}
if (!Push(&S, c)) return 0; /* 自己入栈等着 */
} else {
return 0; /* 不认识的字符 */
}
}
while (Pop(&S, &t)) { /* 读完了:剩下的依次写出去 */
if (t == '(') return 0; /* 还剩左括号:左括号多了 */
out[k++] = t;
}
out[k] = '\0';
return 1;
}
int main(void) {
char *tests[] = {"3+4*2-1", "(3+4)*2", "8-2-1", "9/(1+2)", "2*(3+4)-5", "(3+4", "3+4)", "3++4"};
char post[MAXSIZE];
int v;
for (int i = 0; i < 8; i++) {
if (!ToPostfix(tests[i], post)) printf("%-10s 括号不配对\n", tests[i]);
else if (!Eval(post, &v)) printf("%-10s → %-8s 写错了\n", tests[i], post);
else printf("%-10s → %-8s = %d\n", tests[i], post, v);
}
return 0;
}练习1:栈里是什么?
填空
用栈算后缀式512+4*+3-,从左往右读。
- 读完
*(第6个字符)之后,栈里从栈底到栈顶是 、 - 最后的结果是
5、1、2依次入栈。+弹出2和1,算出3入栈,栈里是5、3。4入栈后,*弹出4和3,算出12入栈,栈里是5、12。+弹出12和5,得17。3入栈,-弹出3和17,算17 - 3 = 14。
练习2:先弹出的是哪一边?
单选
用栈算后缀式8 2 1 - -,结果是多少?
A
7
第一个-先弹出1、再弹出2,算2 - 1 = 1;第二个-弹出1和8,算8 - 1 = 7。
B
5
这是把它当成8-2-1从左往右算了。后缀式里第一个-作用在2和1上。
C
-9
这是把先弹出的数当成了左边:1 - 2 = -1,-1 - 8 = -9。
读到-时,先弹出的是右边的数,后弹出的是左边的数。8 2 1 - -就是8-(2-1)。
到这里你有了后缀式求值:用一个栈放数,读到运算符就弹出两个,算好放回,先弹出的是右边的数。3.6节的转换接上求值,就是一个计算器。下一步栈还藏在程序运行的背后。先来认识一种新的写法:函数调用它自己。