Convert from postfix notation to infix notation

Question

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.

Answer 1

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);}

Answer 2

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)

Answer 3

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

Answer 4

Regex (PCRE2), _¹⁴⁰ 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), _¹⁴⁴ 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).

Answer 5

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