動(dòng)力節(jié)點(diǎn)小編告訴大家，在 Postfix 表達(dá)式中，運(yùn)算符寫在它們的操作數(shù)之后。例如，給出的表達(dá)式采用后綴符號(hào) ABC + * D /。

考慮點(diǎn)

允許的操作數(shù)：A、B、C、D 表示允許任何實(shí)數(shù)。

允許的運(yùn)算符：+、-、*、/、^(取冪)

表達(dá)式中允許有空格

括號(hào)是允許的

與中綴表達(dá)式相比，前綴和后綴表達(dá)式的計(jì)算速度更快，因?yàn)槲覀儾恍枰幚砣魏卫ㄌ?hào)或遵循運(yùn)算符優(yōu)先規(guī)則。在后綴和前綴表達(dá)式中，無(wú)論其優(yōu)先級(jí)如何，先計(jì)算前面的運(yùn)算符。此外，這些表達(dá)式中沒有括號(hào)。只要我們可以保證使用了有效的前綴或后綴表達(dá)式，就可以對(duì)其進(jìn)行正確評(píng)估。

評(píng)估后綴表達(dá)式的算法

第 1 步：如果字符是操作數(shù)，則將其壓入堆棧

第 2 步：如果字符是運(yùn)算符，則從堆棧中彈出兩個(gè)元素。根據(jù)運(yùn)算符對(duì)這些元素進(jìn)行操作，并將結(jié)果推回堆棧

第 3 步：將重復(fù)第 1 步和第 2 步，直到結(jié)束。

第 4 步：結(jié)果存儲(chǔ)在Java堆棧頂部，返回

第 5 步：結(jié)束

后綴評(píng)估的復(fù)雜性

Postfix 評(píng)估算法具有線性復(fù)雜度 O(N)。由于我們掃描表達(dá)式一次并執(zhí)行需要恒定時(shí)間的推送和彈出操作。