时间戳

首页 > 解决方案 > 为字母方程创建二叉树

data-structures - 为字母方程创建二叉树

问题描述

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

例如：- 我有一组标记 - ['(', 'one', '.', 'two', '.', '(', 'zero', '|', 'o', ')' ， '。'， '六'， '）']

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

一二零六

一二六六

这里 ”。” 表示连接运算符，“（）” - 需要分组运算符，“|” 或连接运算符，[] - 可选分组运算符

我已经从字母方程式创建了标记。但是我无法创建正确的二叉树结构，因此我可以创建一棵树，这样每当我遍历树时，我就可以从标记中获取这些句子

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

另一个例子是：-

输入 - ['(', '(', '(', 'one', '.', 'two', ')', '|', '12', ')', '.', '(' , '零', '|', 'o', ')', '.', '六', ')']

输出-

一二零六

一二六六

十二点六

标签： data-structuresbinary-treebinary-search-tree

解决方案

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

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

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

            .
         /     \
      "one"   "two"

当然，“十二”本身就是一个节点。为了完成第一部分，你把“|” 作为父节点，像这样：

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

那给你(("one" . "two") | "twelve")。

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

在解析时有一种正式的构建树的方法，使用的是Shutting-yard algorithm的修改。

推荐阅读