4
\$\begingroup\$

This question may not be that creative, but I believe that it is different enough to pose a new challenge.

The Challenge

Your challenge is to write the shortest program possible that can take any valid expression in Reverse Polish Notation and convert it to infix notation that obeys the order of operations and has the necessary parentheses.

Input

Your program will receive a valid RPN expression on STDIN. This expression will consist of numbers and operators. There can be an arbitrary number of spaces between each item, but there will always be a space between two numbers. Likewise, there will never be a space within a number. Here is a formal grammer description, stolen and modified from the linked question above.

expression := expression expression operator | number
operator   := "+" | "-" | "*" | "/" | "^"
number     := digit number | digit
digit      := "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"

Here are some simple examples

2 3 -10000 +
16 4    12 3 / * -
1 2 +2 3 +^

In the first example, that is not a negation sign, it is a subtraction operator.

Output

Your program should output an equivalent infix expression to STDOUT, which should be a valid infix expression, with numbers, operators, and parentheses.

Here is a formal grammer description, again stolen.

expression     := number | subexpression | expression operator expression
subexpression  := "(" expression ")"
operator       := "+" | "-" | "*" | "/"
number         := digit | digit number
digit          := "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"

With infix notation, there must be an order of operations and a way to group subexpressions. The order of operations will be this:

Expressions inside parentheses
Exponents right to left
Multiplication and division (of equal importance) left to right
Addition and subtraction (of equal importance) left to right

As an example, 2^3^2-(2^3)^2 should equal 448.

The output should not contain any unneeded parentheses. ((2+1))-1 should reduce to 2+1-1. Also, you should not evaluate any expression. You should also not assume the commutative or associative properties. This means that, while the operators will move around, the numbers will always remain in the same order.

Here are the outputs for the above inputs. Note that what would normally be unneeded parenthesis are in the second example: removing them would invoke the associative property.

2-3+10000
16-4*(12/3)
(1+2)^(2+3)

I will add more examples later.

Rules, Regulations, and Notes

This is code golf, standard rules apply.

\$\endgroup\$
8
  • 3
    \$\begingroup\$ Re: no unneeded parentheses, "((2+1))-1 should reduce to (2+1)-1". Shouldn't it reduce to "2+1-1"? Or is that on a different level of "unneeded"? \$\endgroup\$
    – breadbox
    May 17, 2012 at 2:12
  • 1
    \$\begingroup\$ Your second example "16 4 12 3 / * -" should translate to "16-4*(12/3)". \$\endgroup\$
    – breadbox
    May 17, 2012 at 4:55
  • 1
    \$\begingroup\$ @breadbox Ok, the first comment was an error, which I have now fixed. For your second comment, 4*12/3 and 4*(12/3) equal the same thing. The first would be evaluated as 48/3 and the second would be 4*4, which is sixteen. \$\endgroup\$
    – PhiNotPi
    May 17, 2012 at 10:22
  • \$\begingroup\$ but doesn't that assume the associative property? "4*12/3" should be produced by the input "4 12 * 3 /", and "4 12 3 / *" should produce "4*(12/3)", no? \$\endgroup\$
    – breadbox
    May 17, 2012 at 15:31
  • \$\begingroup\$ Wow, yes it does actually use the associative property. Math is the only subject where reducing the number of properties makes it harder. \$\endgroup\$
    – PhiNotPi
    May 17, 2012 at 20:53

5 Answers 5

3
\$\begingroup\$

C, 305 chars

A good challenge! I'm finding this much harder to golf than the previous one. But here's what I have so far:

char*p,b[99];l[99],o[99],r[99],s[99],h,t;
q(e,a,d){int n=o[e]%47%2+(o[e]<48),f=a-n?a>n:d-!n;
l[e]?printf("("+f),q(l[e],n,1),q(r[e],n,!putchar(o[e])),
printf(")"+f):printf("%d",o[e]);}main(){for(p=gets(b);*p;)
*p%24>9?l[++h]=s[t-2],r[h]=s[--t],o[s[t-1]=h]=*p++:
*p-32?o[s[t++]=++h]=strtol(p,&p,10):++p;q(*s,3);}
\$\endgroup\$
2
  • \$\begingroup\$ 297 bytes \$\endgroup\$
    – ceilingcat
    Jun 16, 2020 at 7:45
  • \$\begingroup\$ @ceilingcat I promised myself I wouldn't embed unmatched parens/braces in a macro definition. (Unless it was really entertaining.) The change to strtol does mean that a number like 09 in the input can produce invalid output. \$\endgroup\$
    – breadbox
    Jul 16, 2020 at 23:57
2
\$\begingroup\$

Clojure - 282 279 271 268 characters

(dorun(map pr((reduce(fn[s v](let[p '{e 2,* 1,/ 1,+ 0,- 0}[t z](rseq s)a 
#(if(and(seq? %)(<=(p v)(p(nth % 1))))%`(~%))](if(p v)(conj(pop(pop s))
`(~@(a z)~({'e(symbol"^")}v v)~@(a t)))(conj s v))))[](map read-string
(re-seq #"\d+|[e+*/-]"(.replace(read-line)\^\e))))0)))

(line breaks are totally optional, only included for clarity, if removed ensure there is a single space between a and #( between the first two lines. all other spaces between the lines may be removed).

Assumes input will end after the first line, passes the example programs (outputs more spaces sometimes, but the right number of parentheses :)

Program can be tested here: http://ideone.com/gxykA

Ungolfed:

(defn stackify [s v]
  (let[p '{e 4,* 3,/ 3,+ 2,- 2}
       [t n] (rseq s)
       a #(if (and (coll? %) (<= (p v) (p (nth % 1)))) % `(~%))]
    (if (p v)
      (conj (pop (pop s))
            `(~@(a n) ~({'e(symbol"^")} v v) ~@(a t)))
      (conj s v))))

(defn read-postfix [s]
  "takes a string instead of reading from *in*"
  (->> (.replace s \^ \e)
       (re-seq #"\d+|[e+*/-]")
       (map read-string)
       (reduce stackify [])
       first
       (map pr)
       dorun))

(woo, first stackexchange post)

\$\endgroup\$
4
  • \$\begingroup\$ I can't comment above, but regarding your change to the rules, doesn't the non-assumption of the associative mean that removing parentheses is generally impossible? (order of operations becomes much less meaningful). The example 4 12 * 3 / seems to me like it should produce (4 * 12)/3, if no assumption is done, rather than 4*12/3 like you suggest. \$\endgroup\$
    – yoklov
    May 17, 2012 at 21:02
  • \$\begingroup\$ left-to-right associativity means that parentheses are redundant in that case. \$\endgroup\$
    – breadbox
    May 18, 2012 at 7:33
  • \$\begingroup\$ Err, doesn't left-to-right associativity assume the associative property? I guess I'm fuzzy on how you can have order of operations and not assume the associative property. \$\endgroup\$
    – yoklov
    May 18, 2012 at 20:41
  • \$\begingroup\$ Sorry, it is a little confusing. Left-to-right (vs right-to-left) associativity simply dictates what a parser does in the absence of parentheses. The associative property states that a formula has the same value even when associativity is changed. Thus for example, addition has the associative property, but subtraction does not. The rule is that you can't use any assumptions about certain operations having the associative property as a way to reduce parentheses. (But you still must leave out parentheses that are redundant given an operator's associativity.) \$\endgroup\$
    – breadbox
    May 18, 2012 at 21:01
2
\$\begingroup\$

Flex - 326 288 chars

 *s[99],**p=s,q[99],*n=q,t;main(){yylex();}
 #define W(c) p--;if(*--n c t)asprintf(p,"(%s)",*p);
 #define X asprintf(p++,"%s%s%s",*p,yytext,*(p+1));*n++=t;
 #define Z W(<=)W(<)X
%%
[0-9]+ *p++=strdup(yytext);*n++=9;
\+ t=1;Z
- t=1;Z
\* t=2;Z
\/ t=2;Z
\^ t=3;W(<)W(<=)X
\n puts(*--p);
. ;

trailing newline is needed

Compile with flex makeinfix.l && gcc lex.yy.c -lfl

Edit: fixed for new spec about 4 12 3 / * => 4*(12/3) and made quite a bit shorter

\$\endgroup\$
1
  • \$\begingroup\$ I give you points for doing it completely in the lexer. \$\endgroup\$
    – breadbox
    May 18, 2012 at 7:38
1
\$\begingroup\$

Regex (PCRE2), 140 146 bytes

s~(\d++|\((?1)(?3)(?1)\)) *((?1)) *([*-/^])|(?<=[*/^]()|[+-]|())\(((?1)(?>\^()|[+-]()|.)(?1))\)(?!\^|(?!\7)\4|\8(?!\5($|[+-])))~${1:+($1$3$2):$6}~

Try it online!

This is a single regex substitution to be repeatedly applied until it has nothing to match (or until there is no change, which has the same effect though slightly less efficient).

The assumption is made that there is no leading or trailing space, only possible space between items. This seems a reasonable interpretation of the challenge's rules as stated.

In the following explanation, represents a space:

s~                  # Begin substitution - match the following:
    # Match an expression that shall be converted to infix, with parentheses
    # added.
    (               # Define subroutine (?1) as an argument to an operator, and
                    # on the outermost level, capture this in $1:
        \d++        # Any number of digit characters, minimum one; force all of
                    # them to be consumed (prevent backtracking).
    |        # or...
        \(          # An opening parenthesis
        (?1)        # An argument
        (?3)        # An operator
        (?1)        # An argument
        \)          # A closing parenthesis
    )
    ␣*              # Any number of spaces, minimum zero.
    (               # $2 = the following:
        (?1)        # second argument
    )
    ␣*              # Any number of spaces, minimum zero.
    ([*-/^])        # Define subroutine (?3): Match an operator. The use of a
                    # range means "," and "." can be matched, but that's okay
                    # since they're guaranteed not to be in the input.
|   # Or, match an expression from which the surrounding parentheses shall be
    # removed. This can only match once everything matchable by the above has
    # already been processed.
    (?<=            # Atomic lookbehind
        [*/^]()     # \4 = set if preceded by '*' or '/' or "^"
    |
        [+-]        # set nothing if preceded by "+" or "-"
    |
        ()          # \5 = set if not preceded by any operator
    )
    \(              # An opening parenthesis (to be deleted)
    (               # $6 = the following:
        (?1)        # An argument
        (?>         # Atomic group – lock in the match once this expression
                    # completes.
            \^()    # \7 = set if the operator is "^"
        |
            [+-]()  # \8 = set if the operator is "+" or "-"
        |
            .       # set nothing if the operator is "*" or "/"; it's fine to
                    # use ".", because nothing besides an operator can be
                    # between two arguments (we've removed all the spaces by
                    # this point) and this expression is in an atomic group.
        )
        (?1)        # An argument
    )
    \)              # A closing parenthesis (to be deleted)
    (?!             # Negative lookahead – assert the following can't match:
        \^          # Followed by the operator "^"
    |
        (?!\7)      # Not using the operator "^", and:
        \4          # Preceded by the operator "*" or "/" or  "^"
    |        # or...
        \8          # Using the operator "+" or "-", and:
        (?!         # Not matching the following:
            \5      # Not preceded by any operator, and:
            (
                $       # Followed by nothing
            |           # or
                [+-]    # Followed by the operator "+" or "-"
            )
        )
    )
~                   # Replace with the following:
${1                 # Conditional upon whether \1 is set:
    :+($1$3$2)      # if \1 is set, concatenate $1 + $3 + $2 and surround that
                    # with parentheses.
    :$6             # otherwise, replace with $6 (which is what was matched in
                    # the second alternative, minus its parentheses).
}
~                   # No flags, not even global, which means each substitution
                    # will only make one match, and then the next one will
                    # start its search for a match from the beginning of the
                    # string again. This is slightly less efficient, and done
                    # for golf purposes.

This uses PCRE2_SUBSTITUTE_EXTENDED, which provides a syntax for conditional replacement. Sadly, neither PHP, R, nor Julia support this, even though the option has existed in PCRE2 for nearly 7 years now.

This allows almost anything to be done in a single substitution, where before it would have required multiple substitutions. Without it, this problem would not have been possible in a single substitution, because its first stage inserts parentheses into a string that has none to begin with, but the second stage needs to remove parentheses without adding any.

Some things may still be impossible with a single substitution. The entire state is represented by the current value of the string, and if a later stage needs to go pass through a state that intersects with the possible states of an earlier stage, it would be processed by that earlier stage rather than the later one.

Regex (Boost), 144 146 bytes

s~(\d++|\((?1)(?3)(?1)\)) *((?1)) *([*-/^])|((?<=[*/^]()|[+-])|())\(((?1)(?>\^()|[+-]()|.)(?1))\)(?!\^|(?!\8)\5|\9(?!\6($|[+-])))~?1\($1$3$2\):$7~

Try it online!

Ported to Boost's syntax, which uses parentheses, thus those in the replacement expression need to be backslash-escaped.

Boost does not support alternatives of different widths in one lookbehind, so the |(?<!\))() alternative was moved outside. It also does not support bare backreference syntax with \10 or higher (it'd have to be done as \k<10> instead), but that ended up not mattering (no non-capturing groups had to be used).

\$\endgroup\$
0
\$\begingroup\$

Python3, 140 chars

Difficult to golf, but I've got it sub 200, so I guess it will do.

s=[]
for k in input().split():
    if k in ['+','-','*','/']:p=len(s);s=s[0:p-2]+['('+s[p-2]+k+s[p-1]+')'];
    else:s.append(k)
print(s[0])

Pushes and pops data to the stack and converts to infix

\$\endgroup\$
1
  • \$\begingroup\$ This doesn't work at all when not every token is space-delimited, doesn't remove unnecessary parentheses in any way, and in some cases can't even parse an input even when it is fully space-delimited. None of the test cases return the correct output: Try it online! \$\endgroup\$
    – Deadcode
    Aug 10, 2022 at 15:55

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.