如何估算將中綴表達式轉換爲後綴表達式所需的堆棧空間

有一個着名的shunting-yard algorithm可用於將中綴表達式（例如1 + 2 * 3）轉換爲後綴表達式（例如1 2 2 * +）。分流碼算法需要一個堆棧來存儲即將被移動的元素。如何估算將中綴表達式轉換爲後綴表達式所需的堆棧空間

是否可以預先估計在線性時間和常量內存中執行將特定輸入轉換爲後綴形式所需的堆棧長度？

2013-03-12 fuz

會在輸入中運行分流碼算法，但是計數而不是推送和彈出操作符有資格作爲答案嗎？ – 2013-03-12 21:37:25

@groovy IIRC你需要知道堆棧的內容，以便可能運行分流場地，比方說，如果你有穴位。 – fuz 2013-03-12 21:38:24

好點.. :) – 2013-03-12 21:42:01

當然。 shunting-yard algorithm只將運算符（包括括號）推入堆棧，因此一階近似值是表達式中運算符的數量。多一點智能，你可以掃描表達式，並尋找關聯和分組。但是到你完成的時候，你可能會寫一個基於堆棧的算法來確定表達式所需堆棧大小的最佳估計值，並且會使執行成本增加一倍。

2013-03-12 21:41:14

謝謝你的答案。我想做這個估計，因爲我想避免遞歸算法。我之前必須通過中綴表達式來估計別的東西，所以我認爲這是一個簡單的優化，通過預先計算我需要的堆棧大小來保存對malloc的調用。 – fuz 2013-03-12 21:51:31

分流碼算法是非遞歸的。算法不是遞歸的，僅僅因爲它使用堆棧作爲數據結構。與使用遞歸調用相比，使用堆棧作爲數據結構的內存密集程度要低很多。 – 2013-03-13 11:04:50

是的，我知道。這就是爲什麼我使用Shunting代碼而不是推出遞歸解析器。我只是想預先避免重複調用malloc所需的堆棧數量。 – fuz 2013-03-13 11:09:35

在舊的HP-45計算器上，我們總是掃描嵌套最深的括號，然後開始評估。這應該是輸入中N個令牌的快速O（N）算法。

在實踐中，創建一個表達式來激活HP-45的4個高堆棧是一件非常具有挑戰性的事情。

2013-03-12 21:52:42

謝謝你的答案，但我真的不明白這是如何與分流碼算法相關的。 – fuz 2013-03-12 21:57:45

回答