11
\$\begingroup\$

Introduction

An abstract syntax tree (AST) is a tree of tokens that shows their connection to each other and syntactical meaning. They are commonly used in compilers and static analysis tools, as parsing a language into an AST helps remove any ambiguity and can be helpful for optimizations. Many ASTs are large and complex, but in this thread, your task is to create a basic parser to convert an arithmetic expression into a basic AST.

Challenge

The main part of this challenge is resolving the order of operations. In this challenge, assume PEMDAS so that multiplication is before division and addition is before subtraction. Also, assume left associativity. Every node in the tree should either be an operator or a number. Operators with other operators as children resolve their children first, so nodes at the bottom of the tree resolve first. Number nodes should have no children. Your solution may assume the input is valid, all numbers are positive, and that the input contains no parentheses (unless you'd like to add support for fun).

The input will be a string with only the characters 0123456789+-*/ (and optionally ()). Your program/function may return nested objects/dictionaries, nested arrays/lists, or even a built-in data structure; as long as your output can be interpreted as a tree you're OK (note: if you are going to abuse this rule by using weird formats, then explain how it represents a tree).

Test cases

1+2+3*5-7 -> ['-', ['+', ['+', 1, 2], ['*', 3, 5]], 7], where the first element of the array is the operator, and the second and third are the children.

13*7+9-4+1 -> {op: '-', left: {op: '+', left: {op: '*', left: 13, right: 7}, right: 9}, right: {op: '+', left: 4, right: 1}}

8/2*6+4-1 -> ['-', ['+', ['/', 8, ['*', 2, 6]], 4], 1]

This is , so the shortest code wins!

\$\endgroup\$
10
  • 5
    \$\begingroup\$ Why 13*7+9-4+1 is ((13*7)+9)-(4+1)? \$\endgroup\$
    – l4m2
    Jan 22 at 16:47
  • 1
    \$\begingroup\$ Welcome to Code Golf! From next time, please note that it is recommended to use the Sandbox so you can get feedback before you post your challenge. \$\endgroup\$
    – The Thonnu
    Jan 22 at 16:49
  • 6
    \$\begingroup\$ @MichaelM. Actually, Addition and Subtraction are on the same level in the Order of Operations: they should be executed left to right. So, if you do decide to make Addition go before Subtraction, you should probably make that clear in the challenge. \$\endgroup\$
    – The Thonnu
    Jan 22 at 17:06
  • 6
    \$\begingroup\$ Yep, PEMDAS is really P E M/D A/S - multiplication and division have the same precedence, as do addition and subtraction, so 13*7+9-4+1 = (((13*7)+9)-4)+1. (See Wolfram.) \$\endgroup\$ Jan 22 at 17:07
  • 2
    \$\begingroup\$ Maybe include a test case that has division in it? \$\endgroup\$
    – mousetail
    Jan 22 at 18:08

9 Answers 9

7
\$\begingroup\$

Python, 69 68 bytes

f=lambda x:[*([i,*map(f,x.split(i,1))]for i in'-+/*'if i in x),x][0]

Attempt This Online!

\$\endgroup\$
1
  • 2
    \$\begingroup\$ I think you forgot f=. \$\endgroup\$
    – Jiří
    Jan 23 at 11:16
5
\$\begingroup\$

sed, 96 bytes

s/^/x_/
:a
s/([^*/+-]*)\*([^*/+-]*)/['_',\1,\2]/
ta
y#/+-_SAD#*/+SADM#
/xM/!ba
s///
y#MDAS#*/+-#

Attempt This Online!

\$\endgroup\$
5
\$\begingroup\$

Wolfram Language 99 bytes

Wolfram Language have built-in tools for working with AST, for example

FullForm@MakeExpression@"1-(4/2)+3*(5+7)"

produce

HoldComplete[Plus[1,Times[-1,Times[4,Power[2,-1]]],Times[3,Plus[5,7]]]]

and

TreeForm@MakeExpression@"1-(4/2)+3*(5+7)"

produce

enter image description here

But firstly it looks like cheating. Secondly, it's a bit difficult to obtain the required form from WL output.
Maybe someone can do it, it will be interesting.
Here is a solution based on more common functions.

If[StringLength@#1 == 1,#1,#0/@StringSplit[#1, x__ ~~ # ~~ y__ :> {#,x,y}&/@ {"-", "+", "/", "*"}, 2][[2]]]&
\$\endgroup\$
1
  • \$\begingroup\$ this converts to +-*/, but doesn't discriminate between a-b and a+-1*b (and still loses the ordering of terms of +*) \$\endgroup\$
    – att
    Jan 25 at 12:14
5
\$\begingroup\$

JavaScript (Node.js), 82 bytes

f=(x,i=5,b,j=x.split(b=' */+-'[--i]))=>i?j[1]?[f(j.pop()),b,f(j.join(b))]:f(x,i):x

Try it online!

Seem not that golfed but anyway

Output is reversed

\$\endgroup\$
3
  • \$\begingroup\$ 95 using regex \$\endgroup\$
    – l4m2
    Jan 22 at 19:44
  • \$\begingroup\$ [["1","+",[["4","-","9"],"+","7"]],"*","13"] it is not the 13*7+9-4+1 it is (1 + ((4 - 9) + 7)) * 13 \$\endgroup\$
    – EzioMercer
    Jan 24 at 15:29
  • \$\begingroup\$ ["4","-","9"] - isn't that the first thing to be done? And it is 4-9 or 9-4? \$\endgroup\$
    – EzioMercer
    Jan 24 at 16:41
4
\$\begingroup\$

Vyxal 44 23 bytes

λ`+-:*`(n~ḟ0>[:∇ẇWfvx|_

Thanks to @emanresuA for full refactoring, I began to understand better how lambda works.

    λ        # Open lambda
    `+-:*`(  # Open loop over operators  
    n~ḟ0> [  # If there is such operator   
    :∇ẇWf   # Split and wrap into list  
    vx       # Recursive call lambda as map
    |_       # If there is no continue
             # ]); Closing If, loop and lambda   
                 expected but not required
\$\endgroup\$
4
  • \$\begingroup\$ I don't understand how this works but 23 \$\endgroup\$
    – emanresu A
    Jan 27 at 23:12
  • \$\begingroup\$ Also string input \$\endgroup\$
    – emanresu A
    Jan 28 at 4:18
  • \$\begingroup\$ @emanresuA You should post your answer as separated and better! Or of couse I add it \$\endgroup\$
    – lesobrod
    Jan 28 at 5:36
  • 1
    \$\begingroup\$ Feel free to take it yourself - I just rewrote your thing to use a lambda and autocompletion. \$\endgroup\$
    – emanresu A
    Jan 28 at 6:09
3
\$\begingroup\$

Charcoal, 63 bytes

≔⟦S⟧θ⊞υθF-+/*FΦυ№§κ⁰ι«≔E⮌⪪⊟κι⟦λ⟧ζFζ⊞υλW⊖Lζ⊞ζ⟦ι⊟ζ⊟ζ⟧F⊟ζ⊞κλ»⁻⭆¹θ'

Try it online! Link is to verbose version of code. Outputs values in one-element sublists and operators in three-element sublists. Explanation:

≔⟦S⟧θ

Wrap the input string in a list.

⊞υθ

Push it to the list of lists to be processed.

F-+/*

Loop over the operators in ascending order of precedence.

FΦυ№§κ⁰ι«

Loop over the terms that contain this operator.

≔E⮌⪪⊟κι⟦λ⟧ζ

Remove the term from its list, split it on the operator, and wrap all of the resulting terms in lists.

Fζ⊞υλ

Push all of those lists to the list of lists to be processed.

W⊖Lζ⊞ζ⟦ι⊟ζ⊟ζ⟧

Build up consecutive terms into a nested structure.

F⊟ζ⊞κλ

Re-insert the top-level terms back into the original list.

»⁻⭆¹θ'

Pretty-print the final list.

\$\endgroup\$
2
\$\begingroup\$

Retina, 53 bytes

+0`(\w+)\*(\w+)
aUb$1b$2c
4}T`V*/+-`_o
T`abcV`[,]*/+-

Try it online! Link includes test cases. Explanation: Port of @Jiří's sed answer.

(\w+)\*(\w+)
aUb$1b$2c

Replace (parameter)*(parameter) with [*,(parameter),(parameter)], except encoding * with U, [ with a, , with b and ] with c as they are all letters and will therefore be treated as part of the same parameter in subsequent replacements (both with the current operator and with subsequent operators of lower precedence).

0`

Only perform one replacement at a time.

+`

Repeat the above replacement until no more changes can be made.

T`V*/+-`_o

Step the operators and their encodings in sequence so that - becomes + etc. allowing each operator in turn to be encoded as a U, but those then in turn get stepped to previous vowels.

4}`

Repeat the whole of the above four times, once for each operator.

T`abcV`[,]*/+-

Translate all of the letter placeholders back to the characters they represent.

\$\endgroup\$
2
\$\begingroup\$

Haskell + hgl, 61 bytes

z#y=Fe<Rv<sQ[y<*χ z,z#y,p3 z]++y
gk$bkw$rF(#)(p<rv<dg_)"-+/*"

Explanation

This takes input as a string and outputs as a Free List String. In haskell a list can only contain one type of thing. A free list of strings is basically a list that is allowed to contain strings or other free lists of strings. That makes it the perfect sort of structure for this challenge.

A good deal of the machinery here is devoted to making things left associative. Right associativity would be quite easy, but if we naively modify the algorithm to be left associative it creates recursion without a base case. So what we do instead is that we actually just do right associativity but parse the entire thing backwards. Of course this means we have to do a bunch of extra reversing things, but that's how it goes.

For reference here's a right associative version:

z#y=Fe<sQ[pp[z],y<*χ z,z#y]++y
gk$rF(#)(p<dg_)"-+/*"

It's 9 bytes shorter.

The actual code is quite extensible. We do a fold over a list of operations, and adding new operations is as simple as adding their symbol in the right spot (later entries have higher precedence).

Reflection

This is pretty alright, there could be some improvements.

  • m p should get a shorthand. I keep thinking it already exists, but I can't find it, so I should make it.
  • I wasn't able to use (*:*), but if it had a prefix version I could.
  • Although I use p3, I did at one point have a chain of 4 ps, so I guess p4 has a potential use.
  • bkw doesn't save any bytes here over just using Rv. It's a nice little function and I was excited to use it here, but it seems of limited use. Probably not deserving of a 2 byte name though.
\$\endgroup\$
1
\$\begingroup\$

Go, 79 bytes

import(."go/parser";."go/ast")
func f(s string)Expr{e,_:=ParseExpr(s)
return e}

Attempt This Online!

Returns an ast.Expr from go/ast in Go's standard library, which represents a Go expression.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.