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\$
  • 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 '12 at 2:12
  • 1
    \$\begingroup\$ Your second example "16 4 12 3 / * -" should translate to "16-4*(12/3)". \$\endgroup\$ – breadbox May 17 '12 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 '12 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 '12 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 '12 at 20:53
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\$
  • \$\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 '12 at 21:02
  • \$\begingroup\$ left-to-right associativity means that parentheses are redundant in that case. \$\endgroup\$ – breadbox May 18 '12 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 '12 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 '12 at 21:01
2
\$\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\$

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\$
  • \$\begingroup\$ I give you points for doing it completely in the lexer. \$\endgroup\$ – breadbox May 18 '12 at 7:38
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\$

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.