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與之前的中綴表達式相同。