单选题 与算数表达式“(a+(b-c))*d”对应的树是______。
A.
B.
C.
D.
【正确答案】 B
【答案解析】[解析] 逆波兰式(或称为后缀表达式)是将运算符写在操作数之后的表达式表示方法。结合各种运算符的优先级和结合性等常识,算术表达式(a+(b-c))*d的后缀式是abc-+d*。
一个表达式可用一棵二叉树表示,其中的叶子节点表示操作数,内部节点表示操作符或中间结果,根节点表示整个表达式的值。对该二叉树分别进行后序遍历恰好为表达式的后缀表示(逆波兰式)。对后缀表达式从左到右求值,则每当扫描到一个运算符号时,其操作数是最近刚得到的。后缀式abc-+d*对应的二叉树为选项B。
选项A的二叉树所表示的后缀式是ab+cd-*,其算术表达式为(a+b)*(c-d);
选项C的二叉树所表示的后缀式是abc+-d*,其算术表达式为(a-(b+c))*d;
选项D的二叉树所表示的后缀式是abc+d-*,其算术表达式为a*((b+c)-d)。