构建表达式树

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 ::精神），你会得到你的树