为字母方程创建一个二叉树

Question

我必须创建一个二叉树来从标记列表中获取有效句子。

示例：- 我有一组标记 - ['(', 'one', '.', 'two', '.', '(', 'zero', '|', 'o', ')', '.', 'six', ')']

我想从中获得如下句子的结果：-

一二零六

这里是“.”表示串联连接运算符，“()” - 需要分组运算符，“|”或连接运算符，[] - 可选分组运算符

我已经根据字母顺序创建了记号 equation.But 我无法创建合适的二叉树结构，因此我无法创建一棵树，无论何时遍历树，我都会从中获取这些句子代币

我可以写二叉树的代码，但我一直在为它创建逻辑

另一个例子是：-

输入-['(', '(', '(', 'one', '.', 'two', ')', '|', 'twelve', ')', '.', '(', 'zero', '|', 'o', ')', '.', 'six', ')']

输出-

一二零六

十二点六

Answer 1

将其视为方程解析器很有用。你得到的是这个等式：

(("one" . "two") | "twelve") . (("zero" | "0") . "six")

然后您可以从底部构建树。 ("one" . "two") 看起来像这样：

            .
         /     \
      "one"   "two"

"twelve"当然是一个单独的节点。为了完成第一部分，你把“|”作为父节点，像这样：

             |
         /       \
       .       "twelve" 
    /     \
 "one"   "two"

这给了你 (("one" . "two") | "twelve")。

你对等式的另一半做同样的事情，加上一个“。”运算符作为根节点。

有一种在解析时构建树的正式方法，使用对 Shunting-yard algorithm.

的修改

create a binary tree for alphabetical equation