Build && evaluate

build 和 evaluate本质上是非常类似的:

一、都与AST相关

"evaluate"的过程其实是对AST的traversal

二、两个方向:

1、自底向上

2、自顶向下

build、construct

如何根据expression构建expression tree？参考文章:

一、wikipedia Binary expression tree

二、geeksforgeeks Expression Tree

reverse polish postfix notation expression、自底向上(使用stack)构建expression tree的示例代码。

三、geeksforgeeks Building Expression tree from Prefix Expression

polish prefix notation expression、递归、自顶向下

evaluate

evaluation of expression tree

一、geeksforgeeks Expression Tree

递归、自顶向下、binary tree-DFS-post order后序-return value

二、geeksforgeeks Evaluation of Expression Tree

递归、自顶向下、binary tree-DFS-post order后序-return value

evaluation of expression

一、infogalactic Polish notation

自右向左、自底向上(使用stack)

二、infogalactic Reverse Polish notation

自右向左、自底向上(使用stack)

三、leetcode 150. 逆波兰表达式求值

Post-order traversal、dependency、stack

表达式树也是树，既然是树，那么它的结构就具备递归性

表达式树**的evaluation一定是**深度优先**的，不可以是**广度优先；因为只有子树的结果都计算出来了，才能够计算得到这些子树的父节点的值；如果从遍历的角度来看的话，它所对应的是深度优先遍历的后序遍历。

Evaluation TODO

geeksforgeeks Evaluation of Expression Tree

stackoverflow Evaluating expression trees

geeksforgeeks Expression Evaluation

geeksforgeeks Stack | Set 4 (Evaluation of Postfix Expression)

codechef Expression Tree Construction and Evaluation

codeproject Binary Tree Expression Solver