利用栈求表达式的值时，设立运算数栈 OPEN。假设 OPEN 只有两个存储单元，则在下列表达式中，不会发生溢出的是（ ）。

A. A-B*(C-D) B. (A-B)C-D C. (A-BC)-D D. (A-B)*(C-D)

栈

[tag_link]

正确答案：B

在利用栈求表达式值时，运算数栈 OPEN 用于存储运算数和中间计算结果。 > 由于 OPEN 只有两个存储单元，栈最多能同时容纳两个运算数，若在求值过程中尝试压入第三个运算数，就会发生溢出。 > 因此，需要分析每个表达式在求值过程中运算数栈的最大深度是否超过2。 >

通过将中缀表达式转换为后缀表达式并模拟求值过程，可以计算栈的最大深度：

• 表达式 A: A-B*(C-D)，后缀为 A B C D - * -。 > 求值时，压入 A、B、C 后栈深度达到3，发生溢出。 >
• 表达式 B: (A-B)*C-D，后缀为 A B - C * D -。 > 求值时，栈中最多同时存在两个运算数（如中间结果和 C 或最终结果和 D），最大深度为2，不会溢出。 >
• 表达式 C: (A-B*C)-D，后缀为 A B C * - D -。 > 求值时，压入 A、B、C 后栈深度达到3，发生溢出。 >
• 表达式 D: (A-B)*(C-D)，后缀为 A B - C D - *。 > 求值时，压入中间结果、C、D 后栈深度达到3，发生溢出。 >

因此，只有表达式 B 在求值过程中运算数栈的最大深度不超过2，不会发生溢出。 >