15
\$\begingroup\$

Scientists have made contact with a parallel universe. Just one problem: They write math differently. Help the scientists make a program that can convert normal math expressions to their equivalent in alternate universe math. The connection through the portal is bad so your code needs to be as short as possible

Given a expression, containing only the operators *, +, parenthesis, and variables represented by single lower case ASCII letters, convert it from normal order of operations (* first then +) to inverse order of operations used in a parallel universe (+ first then *). You must remove any redundant parenthesis.

Note: The expression will stay exactly the same. All you need to change is the position of the parenthesis.

Variable names are guaranteed to be unique. Expressions are guaranteed to be valid, be matched, and contain no invalid characters. There will never be redundant parenthesis in the input.

You may substitute * and + with any other 2 unique characters if you prefer. You may substitute () with [] or {} if you prefer.

Test cases

Before After
a+b a+b
a+b*c a+(b*c)
(a+b)*c a+b*c
((a+b)*(c+d)+e)*f (a+b*c+d)+e*f
(a*b+c*d)*e+f ((a*b)+(c*d)*e)+f
a+b+c a+b+c
a*b*c a*b*c
\$\endgroup\$
5
  • \$\begingroup\$ Are variables guaranteed to be single letters? \$\endgroup\$
    – Neil
    Dec 23, 2022 at 14:27
  • 1
    \$\begingroup\$ @Neil yes, as variables are single ASCII lowercase letters \$\endgroup\$
    – mousetail
    Dec 23, 2022 at 14:29
  • \$\begingroup\$ Suggest a+b+c \$\endgroup\$
    – l4m2
    Dec 23, 2022 at 14:56
  • \$\begingroup\$ Can I substitute ( and ) with other characters as well or must they remain the same? \$\endgroup\$ Dec 23, 2022 at 14:57
  • \$\begingroup\$ @CommandMaster you can replace them with a different type of brackets if you like. \$\endgroup\$
    – mousetail
    Dec 23, 2022 at 15:01

5 Answers 5

6
\$\begingroup\$

Charcoal, 100 bytes

F²⊞υ⟦⟧FS«F№)+ι«≔⊟υη⊞§υ±¹⎇⊖Lη⪫()⪫η*⊟η»F№⁺)βι«F№)ι≔⪫⊟υ+ι⊞§υ±¹ι»F№((+ι⊞υ⟦⟧»≔⊟υη≔⊟υθ⊞θ⎇∧θ⊖Lη⪫()⪫η*⪫η*⪫θ+

Try it online! Link is to verbose version of code. Explanation:

F²⊞υ⟦⟧

Start with two lists, one for the + group and one for the * group.

FS«

Loop over the characters in the input string.

F№)+ι«

If the current character is a ) or +, then:

≔⊟υη

Remove the * group.

⊞§υ±¹⎇⊖Lη⪫()⪫η*⊟η

Join it with *s and wrap it in ()s if there is more than one expression in the group, otherwise just push the expression to the + group.

»F№⁺)βι«

If the current character is a ) or lowercase letter:

F№)ι

If it's a ), then...

≔⪫⊟υ+ι

... remove the + group and join it on +.

⊞§υ±¹ι

Push it to the (previous) * group.

»F№((+ι

If it's a ( or +, then...

⊞υ⟦⟧

... for + restore the previously popped * group while for ( push two new groups for + and *.

»≔⊟υη≔⊟υθ

Get the final * and + groups.

⊞θ⎇∧θ⊖Lη⪫()⪫η*⪫η*

Join the final * group on * and push it to the + group, wrapping it in ()s if the + group is not empty.

⪫θ+

Join the + group on + and output the result.

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

JavaScript (Node.js), 193 bytes

x=>g(eval(`[${x.replace(/./g,x=>x=='['|x==']'?x+',':`"${x}",`)}]`))
g=x=>x[1]?x.map(h=c=>h|=c==1?!!u.push(v=[]):v.push(c)&&c,u=[v=[]])|h-3?x.map(g).join``:u.map(v=>v[1]?`[${g(v)}]`:v).join`1`:x

Try it online!

JavaScript (Node.js), 207 bytes

x=>g(eval(`[${x.replace(/./g,x=>x=='('?'[':x==')'?'],':`"${x}",`)}]`))
g=x=>x[1]?x.map(h=c=>h|=c=='+'?!!u.push(v=[]):v.push(c)&&c=='*'?2:0,u=[v=[]])|h-3?x.map(g).join``:u.map(v=>v[1]?`(${g(v)})`:v).join`+`:x

Try it online!

Was strongly messing + and *

\$\endgroup\$
3
\$\begingroup\$

Python 3, 162 bytes

lambda s:g(compile(s,'','eval',1024).body,0)
def g(n,p):
 if'N'in'%s'%n:return n.id
 x='A'in'%s'%n.op;s=g(n.left,x)+'*+'[x]+g(n.right,x);return[s,f'({s})'][p-p*x]

Try it online!

Uses ast.

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

Rust + syn + quote, 315 bytes

use{syn::{*,Expr::*,BinOp::*},quote::*};
fn g(e:Expr,p:usize)->String{match
e{Path(e)=>e.to_token_stream().to_string(),Paren(e)=>g(*e.expr,p),Binary(e)=>{let
x=matches!(e.op,Add(_))as _;let
r=g(*e.left,x)+["*","+"][x]+&g(*e.right,x);[&r,&format!("({r})")][!x&p].into()}_=>loop{}}}let
f=|s|g(parse_str(s).unwrap(),0)

A port of gsitcia's python answer. Handling ASTs in Rust is actually really nice, but a little verbose compared to python.

Playground

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

JavaScript (Node.js), 116 bytes

s=>(M=o=>s[(q=s[i++])<')'&&A(),i++]=='*'?q+='*'+M``:o&&q,A=o=>s[q=M()&&o+s[i]?`(${q})`:q,i-1]>')'?q+='+'+A``:q)(i=0)

Try it online!

A simple recursive descent parser with syntax

A ::= M ["+" A]?
M ::= ("a" .. "z" | "(" A ")") ["*" M]?
s=> // s: input expression
    // i: index of current character (cursor)
(
  M= // Function for parsing M ::= ("a" .. "z" | "(" A ")") ["*" M]?
    o=> // o is undefined if invoked from A
        // o is empty array if invoked from M
      s[
        (q=s[i++])<')'&&A(), // read next character as token "a" .. "z"
                             // or if we got a '(', read an expression A
                             // save the result to variable `q`
      i++]=='*'? // if the following character is `*`
        q+='*'+M``: // we read the optional `"*" M` part
                    // save the result to variable `q` and return it
                    // returns something truthy
        o&&q, // we don't have the extra "*"
              // if o is undefined (invoked from A), return undefined
              //    which means we do not need "()" pairs
              //    if we add `q` with other expressions
              // if o is empty array (invoked from M), return the result
              //    so "q+='*'+M``" could work as expected
  A= // Function for parsing A ::= M "+" A | M
    o=> // o is undefined if invoked from from M
        // o is 0 if invoked from outer
        // o is empty array if invoked from A
        //   which means currently we are parsing a part of addition
        //   and we may need "()" in such case
      s[
        q=M()&& // read the M and the result is saved it to variable q
                // M() returns truthy if we need "()" in case of adding it
                // M() returns falsy if we do not need "()"
          o+s[i]? // if o is undefined (from M) or 0 (from outer)
                  //   and s[i] is undefined (the expression ends)
                  //     so we do not have more things to add
                  //   o+s[i] is NaN (falsy), means we do not need "()"
                  // in all other cases, o+s[i] is some non-empty string
                  //   (truthy), means we need "()"
            `(${q})`:q, // wrap `q` with "()" if needed, save result to `q`
        i-1]>')'? // if we have more thing to add
                  //   s[i-1] is "+" instead of ")"
          q+='+'+A``:q // add them and parse following additions if needed
)(i=0) // initial cursor to 0
\$\endgroup\$
1
  • \$\begingroup\$ Oh god how long did you take to write those comments XD \$\endgroup\$
    – DialFrost
    Jan 1, 2023 at 13:02

Your Answer

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

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