给出下述表达式的DAG，并基于值编码给出对应的记录数组：a+b+a+b

DAG如下：

    +-----+
    |  +  |
    +--+--+
       |
    +--+--+
    |  a  |
    +--+--+
       |
    +--+--+
    |  b  |
    +--+--+
       |
    +--+--+
    |  a  |
    +--+--+
       |
    +--+--+
    |  b  |
    +-----+

基于值编码的记录数组为：[a, b, +, 0, 1, +, 2, 3]，其中0、1、2、3表示的是对应节点在数组中的索引。

相关问题

给出下面表达式的语法树和有向无环图DAG。 （2）c=a*(b-c)+ d* (b-c) （3）c=(a+b)*(c+d)-(a+b+c)

（2）c=a*(b-c)+ d* (b-c) 的语法树如下：

       =
      / \
     c   +
        / \
       *   *
      / \ / \
     a   -   d
        / \
       b   c

（2）c=a*(b-c)+ d* (b-c) 的有向无环图DAG如下：

   b     c
    \   /
     \ /
      -
     / \
    a   \
         \
          *
         / \
        /   \
       /     \
      *       +
     / \     / \
    a   b   c   d

（3）c=(a+b)*(c+d)-(a+b+c) 的语法树如下：

       -
      / \
     =   +
    / \ / \
   c   *   c
      / \   \
     +   d   a+b
    / \     / \
   a   b   a   b

（3）c=(a+b)*(c+d)-(a+b+c) 的有向无环图DAG如下：

   a     b
    \   /
     \ /
      +
     / \
    c   d
     \ /
      *
     / \
    /   \
   /     \
  /       \
 +         c
/ \       / \
a   b     a   b

写出表达式：A+B*（C-D）-E/F|G逆波兰，四元组表示，语法抽象树和DAG图表示

表达式 A+B*(C-D)-E/F|G 的逆波兰表达式为：

A B C D - * + E F / G | -

其中，每个操作数和运算符都是一个单独的元素。

四元组表示如下：

(1, A, _, _)
(2, B, _, _)
(3, C, _, _)
(4, D, _, _)
(5, -, C, D)
(6, *, B, 5)
(7, +, A, 6)
(8, E, _, _)
(9, F, _, _)
(10, /, E, F)
(11, |, 10, G)

其中第一列为序号，第二列为元素值，第三列为左操作数，第四列为右操作数。

语法抽象树的表示如下：

         |
         |
         |
         |
         |
         |
         |
         |
         |
         |
         |
         |
         |
         |
         |
         |
         |
         |
      _______
     |       |
     A       |
             |
             |
          ___|___
         |       |
         +       |
        / \      |
       /   \     |
      *     |    |
     / \    |    |
    B   -   |    |
         / \   / \
        C   D  E  F
                |
                |
                G

DAG图的表示如下：

          |
          |
          |
          |
          |
          |
          |
          |
          |
          |
          |
          |
          |
          |
          |
          |
          |
          |
          |
          |
          |
          |
          |
          |
          |
          |
          |
          |
          |
   _________
  |         |
  A         |
            |
            |
      _____|_____
     |          |
     B          |
               |
             __|__
            |     |
            C     D
            |
          __|__
         |     |
         -     |
        | |    |
        | |    |
        | |    |
        * +    F
        | |    |
        | |    |
        | |    |
        | |    |
        | |    |
        E /    G

其中，每个节点表示一个操作数或运算符，箭头表示依赖关系。节点可以重复利用，例如图中的“-”节点就被多个运算使用。