{"id":224,"date":"2018-10-29T12:19:39","date_gmt":"2018-10-29T12:19:39","guid":{"rendered":"https:\/\/books.compclassnotes.com\/elementarycomputing\/?page_id=224"},"modified":"2018-10-30T12:28:09","modified_gmt":"2018-10-30T12:28:09","slug":"converting-from-prefix-notation-to-abstract-syntax-trees","status":"publish","type":"page","link":"https:\/\/books.compclassnotes.com\/elementarycomputing\/converting-from-prefix-notation-to-abstract-syntax-trees\/","title":{"rendered":"Converting from prefix notation to Abstract Syntax Trees"},"content":{"rendered":"

To convert from prefix notation to an AST, we simply follow this algorithm:<\/p>\n

    \n
  1. The operator becomes a parent<\/li>\n
  2. The first argument becomes the left child<\/li>\n
  3. The second argument becomes the right child<\/li>\n<\/ol>\n

    If either or both of those arguments are expressions, then we just do the same thing for them. For example, if we have the expression\u00a0(+ (- 4 1) 3)<\/strong>, then the\u00a0+\u00a0<\/strong>will be the parent, and the left child will be the AST made up from\u00a0(- 4 1)<\/strong>, so\u00a0–<\/strong> is the parent and 4 and 1 the children. Finally, we have\u00a03<\/strong> as the right hand child of\u00a0+.<\/strong><\/p>\n

    \"\"

    The AST for (+ (- 4 1) 3)<\/p><\/div>\n

    What if we want to go the opposite way and create a prefix expression from an AST? We just start with the root note and apply this algorithm:<\/p>\n

      \n
    1. Write out the operator<\/li>\n
    2. If the first child is an operator, apply the algorithm to that child, otherwise write it out<\/li>\n
    3. If the second child is an operator, apply the algorithm to that child, otherwise write it out<\/li>\n<\/ol>\n

      Using the AST above, we would first encounter\u00a0+<\/strong>, followed by\u00a0–\u00a0<\/strong>meaning we would apply the algorithm to that subtree, giving us (+ (- 4 1) ..)<\/strong>. Next we would apply the final step to\u00a03<\/strong>, which is not an operator, so we write it out.<\/p>\n

      The exercises below will give you a chance to practice this. Type in your prefix expression and it will calculate the corresponding AST and infix expression.<\/p>\n\n\n