CSP真题

白二娃

这是一道关于后缀表达式的CSP 选择题，涉及知识为中缀表达式转换成后缀表达式。

表达式a*（b+c）*d 的后缀表达式为（ ），其中“*”和“+”是运算符。

A. **a+bcd B. abc+*d*

C. abc+d** D. *a*+bcd

中缀表达式（中缀记法） 是一种通用的算术或逻辑公式表示方法，操作符处于操作数的中间，我们日常用的四则运算就是这种算术表示方法。其主要特点是用括号来规定运算优先顺序。

虽然人的大脑很容易理解与分析中缀表达式，但对计算机来说中缀表达式却是很复杂的，早年计算机中使用栈进行运算，并没有括号来规定其运算顺序，于是波兰逻辑学家Jan Lukasiewicz 发明了一种没有括号的后缀表达式来解决这个问题，后缀表达式没有括号，所有的运算符号都标注在数字后面。

计算机在计算表达式的值时，通常需要先将中缀表达式转换为前缀或后缀表达式，然后再进行求值。

将中缀表达式转化为后缀表达式分三步：第一步，先按照运算符的优先级对中缀表达式加括号：

{[a* （b+c）]*d}

第二步，将运算符移到括号的后面（右侧括号外）：

{[a （bc）+]*d}*

第三步，把所有括号去掉所得即为后缀表达式。因此选择答案B：

abc+*d*

对计算机来说，计算前缀或后缀表达式的值就非常简单，比如后缀表达式就使用栈依照规则计算，对于后缀表达式abc+*d*：

1. 先从左到右依次入栈

2. 当是数字的时候直接入栈

栈中a，b，c

3. 当是运算符号的时候，就将栈的最上面两个数拿出进行运算后，再将结果进栈。

4.记住栈顶元素永远在运算符号的右边。

遇到+ 号，c 和b 出栈， 进行运算

b+c，结果进栈，栈中a，（b+c）遇到* 号， （b+c） 和a 出栈，进行运

算a*（b+c），结果进栈，栈中（a*（b+c））

遇到d，進栈，栈中（a*（b+c）），d

遇到* 号，d 和（a*（b+c）） 出栈， 进行运算（a*（b+c））*d与之前的中缀表达式相同。