在严蔚敏教授的《数据结构》(人民邮电出版社,2015年2月第2版)案例 3.3:表达式求值(第78页)中,对后缀表达式求值有详细叙述,但其内容令部分基础不足够好的学习者费解,为此,本节先以简单的形式对后缀表达式求值方法给予介绍,而后解释书中的难点。
1. 初步理解
后缀表达式的求值过程是:从左到右扫描后缀表达式 postexp
:
- 若读取的是一个操作数,将它压入操作数栈;
- 若读取的是一个运算符
op
,从操作数栈中连续出栈两个操作数,假设为a
(第 1个出栈元素)和b
(第 2 个出栈元素),计算b op a
的值,并将计算结果进操作数栈。 - 当整个后缀表达式扫描结束时,操作数栈中的栈顶元素就是表达式的计算结果。
以中缀表达式 (56 - 20) / (4 + 2)
为例,它对应的后缀表达式为 56 20 - 4 2 + /
,如果利用栈,扫描这个后缀表达式 56 20 - 4 2 + /
,求值过程如下(Opnd 是操作数栈):
操作 | Opnd 栈(栈底→栈顶) |
---|---|
遇到 56,将其进栈 | 56 |
遇到 20,将其进栈 | 56, 20 |
遇到 -,依次将 20、56 出栈,计算 56-20=36,将结果 36 进栈 | 36 |
遇到 4,将其进栈 | 36, 4 |
遇到 2,将其进栈 | 36, 4, 2 |
遇到 +,依次将 2、4 出栈,计算 4+2=6,将结果 6 进栈 | 36, 6 |
遇到 /,依次将 6, 36 出栈,计算 36/6=6,将结果 6 进栈 | 6 |
postexp 扫描完毕,算法结束,栈顶数值 6 即为所求。 |
【算法步骤】
while(从 postexp 读取字符 ch,ch != '\0'){ch 为 + : 从 Opnd 中出栈两个数值 a 和 b,计算 b+a=c; 将 c 进栈;ch 为 - : 从 Opnd 中出栈两个数值 a 和 b,计算 b-a=c; 将 c 进栈;ch 为 * : 从 Opnd 中出栈两个数值 a 和 b,计算 b*a=c; 将 c 进栈;ch 为 / : 从 Opnd 中出栈两个数值 a 和 b,若 a 不为零,计算 b/a=c; 将 c 进栈;ch 为数字字符 : 将连续的数字串转换成整数 d,将 d 进栈;
}
【算法描述】
double comp_value(char * postexp){double d, a, b, c, e;SqStack * Opnd; //操作数栈,顺序栈InitStack(Opnd); while(*postexp != '\0'){//postexp字符未扫描完毕,循环switch(*postexp){case '+':Pop(Opnd, a);Pop(Opnd, b);c = b + a;Push(Opnd, c);break;case '-':Pop(Opnd, a);Pop(Opnd, b);c = b - a;Push(Opnd, c);break;case '*':Pop(Opnd, a);Pop(Opnd, b);c = b * a;Push(Opnd, c);break;case '/':Pop(Opnd, a);Pop(Opnd, b);if(a != 0){c = b / a;Push(Opnd, c);break;} else {printf("\n\t零不能做分母\n");exit(0);}break;default:d = 0; //将连续的数字字符转换成对应的数值存放到 dwhile(*postexp >= '0' && *postexp <= '9'){d = 10 * d + *postexp - '0';postexp++;}Push(Opnd, d);break;}postexp++;}GetTop(Opnd, e);DestroyStack(Opnd);return e;
}
由上可知:
- 栈自动记录中间结果,容易对任意复杂的表达式求值。
- 后缀表达式中不需要括号,只需按照表达式顺序求值,让栈自动记录中间结果;也不需要指定操作符的优先级。
- 机器状态永远是一个栈状态,栈里是需要运算的操作数,栈内不会有操作符。
2. 理解教材的案例
严蔚敏教授在《数据结构》(人民邮电出版社,2015年2月第2版)案例 3.3 中,给出了一个运算符优先关系表,如下表所示:
表中显示了运算符之间的三种关系:
- θ 1 < θ 2 \theta_1\lt\theta_2 θ1<θ2 , θ 1 \theta_1 θ1 的优先权低于 θ 2 \theta_2 θ2 ,例如: ′ + ′ < ′ ∗ ′ ; ′ + ′ < ′ / ′ ; '+'\lt'*';~'+'\lt'/';~ ′+′<′∗′; ′+′<′/′; 即“先乘除、后加减”的运算规则。
- θ 1 = θ 2 \theta_1=\theta_2 θ1=θ2 , θ 1 \theta_1 θ1 的优先权等于 θ 2 \theta_2 θ2 。注意:先出现的运算符优先级高,所以有: ′ + ′ > ′ + ′ ; ′ − ′ > ′ − ′ ; '+'\gt'+';~'-'\gt'-';~ ′+′>′+′; ′−′>′−′; 等。
- θ 1 > θ 2 \theta_1\gt\theta_2 θ1>θ2 , θ 1 \theta_1 θ1优先权高于 θ 2 \theta_2 θ2 ,括号内的优先级高,
+、-、*、/
为 θ 1 \theta_1 θ1 时的优先性均低于(
,但高于)
。 - 表中的“
( = )
”表示当左右括号相遇时,括号内的运算已经完成。 - 为了便于实现,假设每个表达式均以
#
开始,以#
结束。所以# = #
表示整个表达式求值完毕。 - 表中空白的部分,即
)
与(
、#
与)
、以及(
与#
之间无优先关系,这是因为表达式中不允许它们相继出现,一旦遇到这种情况,则可以认为出现了语法错误。
为了实现上述算符优先算法,设置两个栈:
- 寄存运算符的栈,命名为
Optr
; - 寄存操作数或运算结果的栈,命名为
Opnd
。
【算法步骤】
- 初始化
Optr
栈和Opnd
,将表达式起始符#
压入Optr
栈。 - 扫描表达式,读入第一个字符
ch
,如果表达式没有扫描完毕至#
或Optr
的栈顶元素不为#
时,则循环执行以下操作:- 若
ch
不是运算符,则压入Opnd
栈,读入下一字符ch
; - 若
ch
是运算符,则根据Optr
的栈顶元素和ch
的优先级比较结果,做不同的处理:- 若是小于,则
ch
压入Optr
栈,读入下一字符ch
; - 若是大于,则弹出
Optr
栈顶的运算符,从Opnd
栈弹出两个数,进行相应运算,结果压入Opnd
栈; - 若是等于,则
Optr
的栈顶元素是(
且 ch 是)
,这时弹出Optr
栈顶的(
,相当于括号匹配成功,然后读入下一字符ch
。
- 若是小于,则
- 若
Opnd
栈顶元素即为表达式求值结果,返回此元素。
【算法描述】
char EvaluateExpression(){//算术表达式求值的算符优先算法,设 OPTR 和 OPND 分别为运算符栈和操作数栈Initstack(Opnd); //初始化 Opnd 栈Initstack(Optr); //初始化 Optr 栈Push(Optr, '#'); //将表达式起始符 '#' 压入 Optr 栈cin>>ch;while(ch !='#' || GetTop(Optr) !='#'){//表达式没有扫描完毕或 Optr 的栈顶元素不为 '#'if(!In(ch)){ //ch 不是运算符则进 Opnd 栈Push(Opnd, ch);cin>>ch;} else{switch(Precede(GetTop(Optr), ch)) //比较 Optr 的栈顶元素和 ch 的优先级case '<':Push(Optr, ch);//当前字符 ch 压入 Optr 栈,cin>>ch; //读入下一字符 chbreak;case '>':Pop(Optr, theta); //弹出 Optr 栈顶的运算符Pop(Opnd, b); //弹出 Opnd 栈顶的两个操作数Pop(Opnd, a);Push(Opnd, Operate(a, theta, b)); //将运算结果压入 Opnd 栈break;case '=': //Optr 的栈顶元素是 '(' 且 ch 是 ')'Pop(Optr, x); //弹出 Optr 栈顶的 '('cin>>ch; //读入下一字符 chbreak;}}return GetTop(OPND); //Opnd 栈顶元素即为表达式求值结果
}
上述算法描述中使用到了三个函数:
- 第 9 行出现的函数
In()
,用于判定读入的字符ch
是否为运算符; - 第 13 行出现的函数
Precede()
,用于判定运算符栈的栈顶元素与读入的运算符之间优先关系; - 第 22 行出现的函数
Operate()
用于进行二元运算。
【算法分析】
- 时间复杂度: O ( n ) O(n) O(n) ;
- 空间复杂度: O ( n ) O(n) O(n) 。