構建表達式樹

Question

給定像4 * 5 + 9這樣的表達式，我們該如何構建一個表達式樹？
我在求職門戶網站閱讀這個面試問題，並試圖嘗試它。

的問題是，如果這已被加上括號，就已經有點容易建立

例如（（4 * 5）+ 9）。
然後隨着左括號的打開，我們知道我們必須向左走，其中數字將是葉節點並且操作符將是父親，並且一旦我們打右括號，我們就會返回並上升到關卡。

我們如何構建這樣的表達樹？

Answer 1

您可以從BNF開始，並以您的方式工作。 在括號簡單表達式的情況下，這將是

EXPR ::= TERM [ ('+'|'-') TERM ] 
TERM ::= MUL [ ('*'|'/') MUL ] 
MUL ::= NUMBER | '(' EXPR ')' 
NUMBER ::= DIGIT [ DIGIT ] 
DIGIT ::= '0' ... '9' 

只寫函數解析每個部分（或使用boost ::精神），你會得到你的樹