白二娃

這是一道關(guān)于后綴表達(dá)式的CSP 選擇題，涉及知識(shí)為中綴表達(dá)式轉(zhuǎn)換成后綴表達(dá)式。

表達(dá)式a*（b+c）*d 的后綴表達(dá)式為（ ），其中“*”和“+”是運(yùn)算符。

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

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

中綴表達(dá)式（中綴記法） 是一種通用的算術(shù)或邏輯公式表示方法，操作符處于操作數(shù)的中間，我們?nèi)粘Ｓ玫乃膭t運(yùn)算就是這種算術(shù)表示方法。其主要特點(diǎn)是用括號(hào)來規(guī)定運(yùn)算優(yōu)先順序。

雖然人的大腦很容易理解與分析中綴表達(dá)式，但對計(jì)算機(jī)來說中綴表達(dá)式卻是很復(fù)雜的，早年計(jì)算機(jī)中使用棧進(jìn)行運(yùn)算，并沒有括號(hào)來規(guī)定其運(yùn)算順序，于是波蘭邏輯學(xué)家Jan Lukasiewicz 發(fā)明了一種沒有括號(hào)的后綴表達(dá)式來解決這個(gè)問題，后綴表達(dá)式?jīng)]有括號(hào)，所有的運(yùn)算符號(hào)都標(biāo)注在數(shù)字后面。

計(jì)算機(jī)在計(jì)算表達(dá)式的值時(shí)，通常需要先將中綴表達(dá)式轉(zhuǎn)換為前綴或后綴表達(dá)式，然后再進(jìn)行求值。

將中綴表達(dá)式轉(zhuǎn)化為后綴表達(dá)式分三步：第一步，先按照運(yùn)算符的優(yōu)先級對中綴表達(dá)式加括號(hào)：

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

第二步，將運(yùn)算符移到括號(hào)的后面（右側(cè)括號(hào)外）：

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

第三步，把所有括號(hào)去掉所得即為后綴表達(dá)式。因此選擇答案B：

abc+*d*

對計(jì)算機(jī)來說，計(jì)算前綴或后綴表達(dá)式的值就非常簡單，比如后綴表達(dá)式就使用棧依照規(guī)則計(jì)算，對于后綴表達(dá)式abc+*d*：

1. 先從左到右依次入棧

2. 當(dāng)是數(shù)字的時(shí)候直接入棧

棧中a，b，c

3. 當(dāng)是運(yùn)算符號(hào)的時(shí)候，就將棧的最上面兩個(gè)數(shù)拿出進(jìn)行運(yùn)算后，再將結(jié)果進(jìn)棧。

4.記住棧頂元素永遠(yuǎn)在運(yùn)算符號(hào)的右邊。

遇到+ 號(hào)，c 和b 出棧， 進(jìn)行運(yùn)算

b+c，結(jié)果進(jìn)棧，棧中a，（b+c）遇到* 號(hào)， （b+c） 和a 出棧，進(jìn)行運(yùn)

算a*（b+c），結(jié)果進(jìn)棧，棧中（a*（b+c））

遇到d，進(jìn)棧，棧中（a*（b+c）），d

遇到* 號(hào)，d 和（a*（b+c）） 出棧， 進(jìn)行運(yùn)算（a*（b+c））*d與之前的中綴表達(dá)式相同。