6
\$\begingroup\$

This expression actually has an omitted pair of parentheses.

1 + 2 * 3

To make things clear, it should be,

1 + (2 * 3)

Even this has its parentheses missing.

1 + 2 + 3

It actually means,

(1 + 2) + 3

People often assume left-to-right evaluation to such an arithmetic expression, but I want to make everything very clear.

Given an arithmetic expression, add parentheses until the order of evaluation is clear without any assumption, and don't remove any pre-existing parentheses.

Here are some examples of possible inputs and their expected output.

IN  
OUT 

IN  1
OUT 1

IN  (((1)))
OUT (((1)))

IN  1+2+3+4+5
OUT (((1+2)+3)+4)+5

IN  1/2/3/4/5
OUT (((1/2)/3)/4)/5

IN  1/2/((3/4))/5
OUT ((1/2)/((3/4)))/5

IN  1+2-3*4/5+6-7*8/9
OUT (((1+2)-((3*4)/5))+6)-((7*8)/9)

IN  1+(2-3*4/5+6-7)*8/9
OUT 1+(((((2-((3*4)/5))+6)-7)*8)/9)

The expression will be composed of single-digit numbers, operators (+, -, *, /), and parentheses. The typical rules of evaluation apply; left-to-right, parentheses first, multiplication first.

The input may have whitespaces, which has no effect, but your program should be able to handle them. The output must have no whitespace and have the same format as given in the examples. The input should be read either as a command line argument or from stdin, and the code should be runnable with no additional code.

This is a code-golf challenge.

Here's a rather formal definition of an arithmetic expression.

primary-expression
  [0-9]
  (arithmetic-expression)

multiplicative-expression
  primary-expression
  multiplicative-expression (* | /) primary-expression

additive-expression
  multiplicative-expression
  additive-expression (+ | -) multiplicative-expression

arithmetic-expression
  additive-expression

This is a python script that you can use to validate your output (in a very manual way..).

I had fun writing Lisp in Python.

def addop(op):
    return op == '+' or op == '-'

def match(l):
    if l[1:] == []:
        return [1, l]
    elif addop(l[1]):
        if l[3:] == [] or addop(l[3]):
            return [3, l[0:3]]
        else:
            m = match(l[2:])
            return [m[0] + 2, l[0:2] + [m[1]]]
    else:
        if l[3:] == [] or addop(l[3]):
            return [3, l[0:3]]
        else:
            m = match([l[0:3]] + l[3:])
            return [m[0] + 2, m[1]]

def tree__(l):
    m = match(l)
    if l[m[0]:] == []:
        return m[1]
    else:
        return tree__([m[1]] + l[m[0]:])

def tree_(l):
    if l == []:
        return []
    elif isinstance(l[0], list):
        return [tree_(tree__(l[0]))] + tree_(l[1:])
    else:
        return [l[0]] + tree_(l[1:])

def tree(l):
    return tree_(tree__(l))

def afterParen(s, n):
    if s == '':
        return '';
    if s[0] == '(':
        return afterParen(s[1:], n + 1)
    if s[0] == ')':
        if n == 0:
            return s[1:]
        else:
            return afterParen(s[1:], n - 1)
    else:
        return afterParen(s[1:], n)

def toList(s):
    if s == '' or s[0] == ')':
        return []
    elif s[0] == '(':
        return [toList(s[1:])] + toList(afterParen(s[1:], 0))
    elif s[0].isspace():
        return toList(s[1:])
    elif s[0].isdigit():
        return [int(s[0])] + toList(s[1:])
    else:
        return [s[0]] + toList(s[1:])

def toString(l):
    if l == []:
        return ''
    elif isinstance(l[0], list):
        return '(' + toString(l[0]) + ')' + toString(l[1:])
    elif isinstance(l[0], int):
        return str(l[0]) + toString(l[1:])
    else:
        return l[0] + toString(l[1:])

def addParen(s):
    return toString(tree(toList(s)))

exp = "1+2*3+4+2+2-3*4/2*4/2"
print(exp)
print(addParen(exp))
exp = "((1+2*(3+4)+(((((2))+(2-3*4/2)*4)))/2))"
print(exp)
print(addParen(exp))
\$\endgroup\$
7
  • 3
    \$\begingroup\$ Maybe add some test cases, e.g. 1/2/3 \$\endgroup\$
    – Adám
    Jan 4 at 10:35
  • \$\begingroup\$ @Adám Due to left-to-right evaluation, that should be (1/2)/3 \$\endgroup\$
    – xiver77
    Jan 4 at 10:36
  • 5
    \$\begingroup\$ Best if you have some test cases listed on their own in the OP. This makes it all so much clearer. \$\endgroup\$
    – Noodle9
    Jan 4 at 11:46
  • \$\begingroup\$ can 1*2 give (1*2) \$\endgroup\$
    – Fmbalbuena
    Jan 4 at 18:10
  • \$\begingroup\$ @Noodle9 I made a big edit to make things clear, but even before the edit it had the example that 1+2*3+4+2+2-3*4/2*4/2 should output ((((1+(2*3))+4)+2)+2)-((((3*4)/2)*4)/2), and I thought it was clear enough. \$\endgroup\$
    – xiver77
    Jan 4 at 19:02
5
\$\begingroup\$

Pip 1.0, 20 19 bytes

a&TM(ST V"{}"Ja)DCs

Attempt This Online!

Verify all test cases

Explanation

Episode 2 in the "Hey, my language happens to do exactly that!" saga...

In Pip 1.0, the string representation of a function is derived by "unparsing" the function's parse tree. Because I was lazy, I decided to just put parentheses around every subexpression, rather than trying to eliminate the parentheses that weren't necessary. Also, because I was lazy, redundant layers of parenthesization are kept in the parse tree, so they also remain in the string representation.

Thus, all this program does is convert the input to a function, get that function's string representation, and delete a few extra characters. The empty string is a corner case that costs +2 bytes.

a&TM(ST V"{}"Ja)DCs
a                    First command-line argument
 &                   If it is truthy (not empty or 0), then:
         "{}"          This string
             Ja        Joined on the argument (essentially, wrap the arg in {})
        V              Eval the resulting string as a Pip expression
                       The string will always be a valid function literal, so
                       the result is a Pip function
     ST                Stringify
  TM(          )       Trim off the curly braces
                DCs    Delete all spaces
                     If the arg is falsey, use the arg itself ("" or "0")
\$\endgroup\$
0
1
\$\begingroup\$

Retina 0.8.2, 237 bytes

\s

+1`(?<=(^|\()?)(\d|\(((\()|(?<-4>\))|[^()])+(?(4)$)\))[*/](\d|\(((\()|(?<-7>\))|[^()])+(?(7)$)\))(?(1)(?!$|\)))
($&)
+1`(?<=(^|\()?)(\d|\(((\()|(?<-4>\))|[^()])+(?(4)$)\))[-+](\d|\(((\()|(?<-7>\))|[^()])+(?(7)$)\))(?(1)(?!$|\)))
($&)

Try it online! Link includes test cases. Explanation:

\s

Delete white space.

+`

Repeat until no more replacements can be made.

1`

Make only one replacement at a time.

(?<=(^|\()?)

See whether this subexpression begins at the beginning of the string or after a (.

(\d|\(((\()|(?<-4>\))|[^()])+(?(4)$)\))

Match either a digit or a balanced subexpression (using a .NET balancing group).

[*/]

Match either a * or a / sign.

(\d|\(((\()|(?<-7>\))|[^()])+(?(7)$)\))

Match another digit or balanced subexpression.

(?(1)(?!$|\)))

If the match started at the beginning of the string or after a (, it must not match at the end of the string or after a ), because this subexpression is already parenthesised (or is the whole expression, which does not need to be parenthesised).

($&)

Parenthesise this match.

+1`(?<=(^|\()?)(\d|\(((\()|(?<-4>\))|[^()])+(?(4)$)\))[-+](\d|\(((\()|(?<-7>\))|[^()])+(?(7)$)\))(?(1)(?!$|\)))
($&)

Do the - and + signs in the same way.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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