{{clarified-review}} {{task}}

;Task: Create a program that takes an [[wp:Reverse Polish notation|RPN]] representation of an expression formatted as a space separated sequence of tokens and generates the equivalent expression in [[wp:Infix notation|infix notation]].

• Assume an input of a correct, space separated, string of tokens

• Generate a space separated output string representing the same expression in infix notation

• Show how the major datastructure of your algorithm changes with each new token parsed.

• Test with the following input RPN strings then print and display the output here. :{| class="wikitable" ! RPN input !! sample output |- || align="center" | 3 4 2 * 1 5 - 2 3 ^ ^ / +|| 3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3 |- || align="center" | 1 2 + 3 4 + ^ 5 6 + ^|| ( ( 1 + 2 ) ^ ( 3 + 4 ) ) ^ ( 5 + 6 ) |}

• Operator precedence and operator associativity is given in this table: :{| class="wikitable"

! operator !! [[wp:Order_of_operations|precedence]] !! [[wp:Operator_associativity|associativity]] !! operation |- || align="center" | ^ || 4 || right || exponentiation |- || align="center" | * || 3 || left || multiplication |- || align="center" | / || 3 || left || division |- || align="center" | + || 2 || left || addition |- || align="center" | - || 2 || left || subtraction |}

;See also:

• [[Parsing/Shunting-yard algorithm]] for a method of generating an RPN from an infix expression.
• [[Parsing/RPN calculator algorithm]] for a method of calculating a final value from this output RPN expression.
• [http://www.rubyquiz.com/quiz148.html Postfix to infix] from the RubyQuiz site.

Ada

Using the solution of the task [[stack]]:

   type Priority is range 1..4;
   type Infix is record
      Precedence : Priority;
      Expression : Unbounded_String;
   end record;
   package Expression_Stack is new Generic_Stack (Infix);
   use Expression_Stack;

   function Convert (RPN : String) return String is
      Arguments : Stack;
      procedure Pop
                (  Operation   : Character;
                   Precedence  : Priority;
                   Association : Priority
                )  is
         Right, Left : Infix;
         Result      : Infix;
      begin
         Pop (Right, Arguments);
         Pop (Left,  Arguments);
         Result.Precedence := Association;
         if Left.Precedence < Precedence then
            Append (Result.Expression, '(');
            Append (Result.Expression, Left.Expression);
            Append (Result.Expression, ')');
         else
            Append (Result.Expression, Left.Expression);
         end if;
         Append (Result.Expression, ' ');
         Append (Result.Expression, Operation);
         Append (Result.Expression, ' ');
         if Right.Precedence < Precedence then
            Append (Result.Expression, '(');
            Append (Result.Expression, Right.Expression);
            Append (Result.Expression, ')');
         else
            Append (Result.Expression, Right.Expression);
         end if;
         Push (Result, Arguments);
      end Pop;
      Pointer : Integer := RPN'First;
   begin
      while Pointer <= RPN'Last loop
         case RPN (Pointer) is
            when ' ' =>
               Pointer := Pointer + 1;
            when '0'..'9' =>
               declare
                  Start : constant Integer := Pointer;
               begin
                  loop
                     Pointer := Pointer + 1;
                     exit when Pointer > RPN'Last
                       or else RPN (Pointer) not in '0'..'9';
                  end loop;
                  Push
                  (  (  4,
                        To_Unbounded_String (RPN (Start..Pointer - 1))
                     ),
                     Arguments
                  );
               end;
            when '+' | '-' =>
               Pop (RPN (Pointer), 1, 1);
               Pointer := Pointer + 1;
            when '*' | '/' =>
               Pop (RPN (Pointer), 2, 2);
               Pointer := Pointer + 1;
            when '^' =>
               Pop (RPN (Pointer), 4, 3);
               Pointer := Pointer + 1;
            when others =>
               raise Constraint_Error with "Syntax";
         end case;
      end loop;
      declare
         Result : Infix;
      begin
         Pop (Result, Arguments);
         return To_String (Result.Expression);
      end;
   end Convert;

The test program:

with Ada.Strings.Unbounded;  use Ada.Strings.Unbounded;
with Ada.Text_IO;            use Ada.Text_IO;
with Generic_Stack;

procedure RPN_to_Infix is
   -- The code above
begin
   Put_Line ("3 4 2 * 1 5 - 2 3 ^ ^ / + = ");
   Put_Line (Convert ("3 4 2 * 1 5 - 2 3 ^ ^ / +"));
   Put_Line ("1 2 + 3 4 + ^ 5 6 + ^ = ");
   Put_Line (Convert ("1 2 + 3 4 + ^ 5 6 + ^"));
end RPN_to_Infix;

should produce the following output

3 4 2 * 1 5 - 2 3 ^ ^ / + =
3 + 4 * 2 / (1 - 5) ^ (2 ^ 3)
1 2 + 3 4 + ^ 5 6 + ^ =
((1 + 2) ^ (3 + 4)) ^ (5 + 6)

ALGOL 68

{{works with|ALGOL 68G|Any - tested with release 2.8.win32}} Recursively parses the RPN string backwards to build a parse tree which is then printed.

# rpn to infix - parses an RPN expression and generates the equivalent        #
#               infix expression                                              #
PROC rpn to infix = ( STRING rpn )STRING:
BEGIN

    # we parse the string backwards using recursive descent                   #
    INT    rpn pos   := UPB rpn;
    BOOL   had error := FALSE;

    # mode to hold nodes of the parse tree                                    #
    MODE NODE = STRUCT( INT op
                      , UNION( REF NODE, STRING ) left
                      , REF NODE right
                      );

    REF NODE nil node = NIL;


    # op codes                                                                #
    INT error            = 1;
    INT factor           = 2;
    INT add              = 3;
    INT sub              = 4;
    INT mul              = 5;
    INT div              = 6;
    INT pwr              = 7;

    []STRING op name     = ( "error", "factor", "+", "-", "*", "/", "^" );
    []BOOL   right associative
                         = ( FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE );
    []INT    priority    = ( 1, 1, 2, 2, 3, 3, 4 );



    # returns TRUE  if we have reached the end of the rpn string,             #
    #         FALSE otherwise                                                 #
    PROC at end = BOOL: rpn pos < LWB rpn;

    # positions to the previous character, if there is one                    #
    PROC next = VOID: rpn pos -:= 1;

    # skip spaces in the rpn string                                           #
    PROC skip spaces = VOID:
        WHILE have( " " )
        DO
            next
        OD # skip spaces # ;

    # returns TRUE  if the rpn character at rpn pos is c,                     #
    #         FALSE if the character is not c or there is no character        #
    #               at rpn pos                                                #
    PROC have = ( CHAR c )BOOL:
        IF at end
        THEN
            # no character at rpn pos #
            FALSE
        ELSE
            # have a character - check it is the required one #
            rpn[ rpn pos ] = c
        FI # have # ;

    # gets an operand from the rpn string                                     #
    # an operand is either a number or a sub-expression                       #
    PROC get operand = ( STRING rpn, STRING operand name )REF NODE:
    BEGIN

        # handle the operator or operand, if there is one                     #

        skip spaces;

        print( ( ( "parsing "
                 + operand name
                 + " from: "
                 + IF at end THEN "" ELSE rpn[ LWB rpn : rpn pos ] FI
                 )
               , newline
               )
             );

        REF NODE result :=
            IF   at end
            THEN
                # no operand #
                had error       := TRUE;
                HEAP NODE       := ( error, "!! Missing operand !!", NIL )
            ELIF have( "+" )
            THEN
                # addition #
                next;
                HEAP NODE right := get operand( rpn, "+ right operand" );
                HEAP NODE left  := get operand( rpn, "+ left operand"  );
                HEAP NODE       := ( add, left, right )
            ELIF have( "-" )
            THEN
                # subtraction #
                next;
                HEAP NODE right := get operand( rpn, "- right operand" );
                HEAP NODE left  := get operand( rpn, "- left operand"  );
                HEAP NODE       := ( sub, left, right )
            ELIF have( "*" )
            THEN
                # multiplication #
                next;
                HEAP NODE right := get operand( rpn, "* right operand" );
                HEAP NODE left  := get operand( rpn, "* left operand"  );
                HEAP NODE       := ( mul, left, right )
            ELIF have( "/" )
            THEN
                # division #
                next;
                HEAP NODE right := get operand( rpn, "/ right operand" );
                HEAP NODE left  := get operand( rpn, "/ left operand"  );
                HEAP NODE       := ( div, left, right )
            ELIF have( "^" )
            THEN
                # exponentiation #
                next;
                HEAP NODE right := get operand( rpn, "^ right operand" );
                HEAP NODE left  := get operand( rpn, "^ left operand"  );
                HEAP NODE       := ( pwr, left, right )
            ELSE
                # must be an operand #
                STRING value := "";

                WHILE NOT at end
                  AND NOT have( " " )
                DO
                    rpn[ rpn pos ] +=: value;
                    next
                OD;

                HEAP NODE := ( factor, value, NIL )
            FI;

        print( ( operand name + ": " + TOSTRING result, newline ) );

        result
    END # get operand # ;


    # converts the parse tree to a string with apppropriate parenthesis       #
    OP TOSTRING = ( REF NODE operand )STRING:
    BEGIN

        # converts a node of the parse tree to a string, inserting            #
        # parenthesis if necessary                                            #
        PROC possible parenthesis = ( INT op, REF NODE expr )STRING:
            IF op OF expr = error
            OR op OF expr = factor
            THEN
                # operand is an error/factor - parenthisis not needed #
                TOSTRING expr
            ELIF priority( op OF expr ) < priority( op )
            THEN
                # the expression is a higher precedence operator than the     #
                # one we are building the expression for - need parenthesis   #
                ( "( " + TOSTRING expr + " )" )
            ELIF right associative[ op OF operand ]
             AND op OF left( operand ) = op OF operand
            THEN
                # right associative operator                                  #
                ( "( " + TOSTRING expr + " )" )
            ELSE
                # lower precedence expression - parenthesis not needed        #
                TOSTRING expr
            FI # possible parenthesis # ;

        # gets the left branch of a node, which must be a node                #
        PROC left  = ( REF NODE operand )REF NODE:
            CASE left OF operand
            IN ( REF NODE o ): o
            ,  ( STRING   s ): HEAP NODE := ( error, s, NIL )
            ESAC # left # ;

        IF   had error
        THEN
            # an error occured parsing the expression #
            "Invalid expression"
        ELIF operand IS nil node
        THEN
           # no operand? #
            "<empty>"
        ELIF op OF operand = error
          OR op OF operand = factor
        THEN
            # error parsing the expression #
            # or a factor #
            CASE left OF operand
            IN ( REF NODE o ): "Error: String expected: (" + TOSTRING o + ")"
            ,  ( STRING   s ): s
            ESAC
        ELSE
            # general operand #
            ( possible parenthesis( op OF operand, left(    operand ) )
            + " " + op name[ op OF operand ] + " "
            + possible parenthesis( op OF operand, right OF operand   )
            )
        FI
    END # TOSTRING # ;

    STRING result = TOSTRING get operand( rpn, "expression" );

    # ensure there are no more tokens in the string #
    skip spaces;
    IF at end
    THEN
        # OK - there was only one expression #
        result
    ELSE
        # extraneous tokens #
        ( "Error - unexpected text before expression: ("
        + rpn[ LWB rpn : rpn pos ]
        + ")"
        )
    FI
END # rpn to infix # ;



main: (

    # test the RPN to Infix comnverter                                        #
    STRING rpn;

    rpn := "3 4 2 * 1 5 - 2 3 ^ ^ / +";
    print( ( rpn, ":  ", rpn to infix( rpn ), newline, newline ) );

    rpn := "1 2 + 3 4 + ^ 5 6 + ^";
    print( ( rpn, ":  ", rpn to infix( rpn ), newline ) )

)

{{out}}

 parsing expression from: 3 4 2 * 1 5 - 2 3 ^ ^ / +
 parsing + right operand from: 3 4 2 * 1 5 - 2 3 ^ ^ /
 parsing / right operand from: 3 4 2 * 1 5 - 2 3 ^ ^
 parsing ^ right operand from: 3 4 2 * 1 5 - 2 3 ^
 parsing ^ right operand from: 3 4 2 * 1 5 - 2 3
 ^ right operand: 3
 parsing ^ left operand from: 3 4 2 * 1 5 - 2
 ^ left operand: 2
 ^ right operand: 2 ^ 3
 parsing ^ left operand from: 3 4 2 * 1 5 -
 parsing - right operand from: 3 4 2 * 1 5
 - right operand: 5
 parsing - left operand from: 3 4 2 * 1
 - left operand: 1
 ^ left operand: 1 - 5
 / right operand: ( 1 - 5 ) ^ 2 ^ 3
 parsing / left operand from: 3 4 2 *
 parsing * right operand from: 3 4 2
 * right operand: 2
 parsing * left operand from: 3 4
 * left operand: 4
 / left operand: 4 * 2
 + right operand: 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3
 parsing + left operand from: 3
 + left operand: 3
 expression: 3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3
 3 4 2 * 1 5 - 2 3 ^ ^ / +:  3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3

 parsing expression from: 1 2 + 3 4 + ^ 5 6 + ^
 parsing ^ right operand from: 1 2 + 3 4 + ^ 5 6 +
 parsing + right operand from: 1 2 + 3 4 + ^ 5 6
 + right operand: 6
 parsing + left operand from: 1 2 + 3 4 + ^ 5
 + left operand: 5
 ^ right operand: 5 + 6
 parsing ^ left operand from: 1 2 + 3 4 + ^
 parsing ^ right operand from: 1 2 + 3 4 +
 parsing + right operand from: 1 2 + 3 4
 + right operand: 4
 parsing + left operand from: 1 2 + 3
 + left operand: 3
 ^ right operand: 3 + 4
 parsing ^ left operand from: 1 2 +
 parsing + right operand from: 1 2
 + right operand: 2
 parsing + left operand from: 1
 + left operand: 1
 ^ left operand: 1 + 2
 ^ left operand: ( 1 + 2 ) ^ ( 3 + 4 )
 expression: ( ( 1 + 2 ) ^ ( 3 + 4 ) ) ^ ( 5 + 6 )
 1 2 + 3 4 + ^ 5 6 + ^:  ( ( 1 + 2 ) ^ ( 3 + 4 ) ) ^ ( 5 + 6 )

AWK

Slavishly (mostly) follows TCL example, but instead of lists it uses strings. Except for the stack, which uses an array, of course.

The kludge is prepending the precedence on the front of the expressions stored on the stack. This shows up when the tail() function is used, and when 'x' is prepended as a placeholder when adding parenthesis.

#!/usr/bin/awk -f

BEGIN {
    initStack()
    initOpers()
    print "Infix: " toInfix("3 4 2 * 1 5 - 2 3 ^ ^ / +")
    print ""
    print "Infix: " toInfix("1 2 + 3 4 + ^ 5 6 + ^")
    print ""
    print "Infix: " toInfix("moon stars mud + * fire soup * ^")
    exit
}

function initStack() {
    delete stack
    stackPtr = 0
}

function initOpers() {
    VALPREC = "9"
    LEFT = "l"
    RIGHT = "r"
    operToks  = "+"  "-"  "/"  "*"  "^"
    operPrec  = "2"  "2"  "3"  "3"  "4"
    operAssoc = LEFT LEFT LEFT LEFT RIGHT
}

function toInfix(rpn,      t, toks, tok, a, ap, b, bp, tp, ta) {
    print "Postfix: " rpn
    split(rpn, toks, / +/)
    for (t = 1; t <= length(toks); t++) {
        tok = toks[t]
        if (!isOper(tok)) {
            push(VALPREC tok)
        }
         else {
            b = pop()
            bp = prec(b)
            b = tail(b)
            a = pop()
            ap = prec(a)
            a = tail(a)
            tp = tokPrec(tok)
            ta = tokAssoc(tok)
            if (ap < tp || (ap == tp && ta == RIGHT)) {
                a = "(" a ")"
            }
            if (bp < tp || (bp == tp && ta == LEFT)) {
                b = "(" b ")"
            }
            push(tp a " "  tok " " b)
        }
        print "    " tok " -> " stackToStr()
    }
    return tail(pop())
}

function push(expr) {
    stack[stackPtr] = expr
    stackPtr++
}

function pop() {
    stackPtr--
    return stack[stackPtr]
}

function isOper(tok) {
    return index(operToks, tok) != 0
}

function prec(expr) {
    return substr(expr, 1, 1)
}

function tokPrec(tok) {
    return substr(operPrec, operIdx(tok), 1)
}

function tokAssoc(tok) {
    return substr(operAssoc, operIdx(tok), 1)
}

function operIdx(tok) {
    return index(operToks, tok)
}

function tail(s) {
    return substr(s, 2)
}

function stackToStr(    s, i, t, p) {
    s = ""
    for (i = 0; i < stackPtr; i++) {
        t = stack[i]
        p = prec(t)
        if (index(t, " ")) t = "{" tail(t) "}"
        else t = tail(t)
        s = s "{" p " " t "} "
    }
    return s
}

Output:

Postfix: 3 4 2 * 1 5 - 2 3 ^ ^ / + 3 -> {9 3} 4 -> {9 3} {9 4} 2 -> {9 3} {9 4} {9 2} * -> {9 3} {3 {4 * 2}} 1 -> {9 3} {3 {4 * 2}} {9 1} 5 -> {9 3} {3 {4 * 2}} {9 1} {9 5} - -> {9 3} {3 {4 * 2}} {2 {1 - 5}} 2 -> {9 3} {3 {4 * 2}} {2 {1 - 5}} {9 2} 3 -> {9 3} {3 {4 * 2}} {2 {1 - 5}} {9 2} {9 3} ^ -> {9 3} {3 {4 * 2}} {2 {1 - 5}} {4 {2 ^ 3}} ^ -> {9 3} {3 {4 * 2}} {4 {(1 - 5) ^ 2 ^ 3}} / -> {9 3} {3 {4 * 2 / (1 - 5) ^ 2 ^ 3}} + -> {2 {3 + 4 * 2 / (1 - 5) ^ 2 ^ 3}} Infix: 3 + 4 * 2 / (1 - 5) ^ 2 ^ 3

Postfix: 1 2 + 3 4 + ^ 5 6 + ^ 1 -> {9 1} 2 -> {9 1} {9 2} + -> {2 {1 + 2}} 3 -> {2 {1 + 2}} {9 3} 4 -> {2 {1 + 2}} {9 3} {9 4} + -> {2 {1 + 2}} {2 {3 + 4}} ^ -> {4 {(1 + 2) ^ (3 + 4)}} 5 -> {4 {(1 + 2) ^ (3 + 4)}} {9 5} 6 -> {4 {(1 + 2) ^ (3 + 4)}} {9 5} {9 6} + -> {4 {(1 + 2) ^ (3 + 4)}} {2 {5 + 6}} ^ -> {4 {((1 + 2) ^ (3 + 4)) ^ (5 + 6)}} Infix: ((1 + 2) ^ (3 + 4)) ^ (5 + 6)

Postfix: moon stars mud + * fire soup * ^ moon -> {9 moon} stars -> {9 moon} {9 stars} mud -> {9 moon} {9 stars} {9 mud} + -> {9 moon} {2 {stars + mud}} * -> {3 {moon * (stars + mud)}} fire -> {3 {moon * (stars + mud)}} {9 fire} soup -> {3 {moon * (stars + mud)}} {9 fire} {9 soup} * -> {3 {moon * (stars + mud)}} {3 {fire * soup}} ^ -> {4 {(moon * (stars + mud)) ^ (fire * soup)}} Infix: (moon * (stars + mud)) ^ (fire * soup)

AutoHotkey

{{works with|AutoHotkey_L}}

expr := "3 4 2 * 1 5 - 2 3 ^ ^ / +"

stack := {push: func("ObjInsert"), pop: func("ObjRemove")}
out := "TOKEN`tACTION                  STACK (comma separated)`r`n"
Loop Parse, expr, %A_Space%
{
	token := A_LoopField
	if token is number
		stack.push([0, token])
	if isOp(token)
	{
		b := stack.pop(), a := stack.pop(), p := b.1 > a.1 ? b.1 : a.1
		p := Precedence(token) > p ? precedence(token) : p
		if (a.1 < b.1) and isRight(token)
			stack.push([p, "( " . a.2 " ) " token " " b.2])
		else if (a.1 > b.1) and isLeft(token)
			stack.push([p, a.2 token " ( " b.2 " ) "])
		else
			stack.push([p, a.2 . " " . token . " " . b.2])
	}
	out .= token "`t" (isOp(token) ? "Push Partial expression "
			   : "Push num" space(16)) disp(stack) "`r`n"
}
out .= "`r`n The final output infix expression is: '" disp(stack) "'"
clipboard := out
isOp(t){
       return (!!InStr("+-*/^", t) && t)
}
IsLeft(o){
       return !!InStr("*/+-", o)
}
IsRight(o){
       return o = "^"
}
Precedence(o){
       return (InStr("+-/*^", o)+3)//2
}
Disp(obj){
       for each, val in obj
		if val[2]
			o .= ", " val[2]
       return  SubStr(o,3)
}
Space(n){
       return n>0 ? A_Space Space(n-1) : ""
}

;Output

TOKEN	ACTION                  STACK (comma separated)
3	Push num                3
4	Push num                3, 4
2	Push num                3, 4, 2
*	Push Partial expression 3, 4 * 2
1	Push num                3, 4 * 2, 1
5	Push num                3, 4 * 2, 1, 5
-	Push Partial expression 3, 4 * 2, 1 - 5
2	Push num                3, 4 * 2, 1 - 5, 2
3	Push num                3, 4 * 2, 1 - 5, 2, 3
^	Push Partial expression 3, 4 * 2, 1 - 5, 2 ^ 3
^	Push Partial expression 3, 4 * 2, ( 1 - 5 ) ^ 2 ^ 3
/	Push Partial expression 3, 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3
+	Push Partial expression 3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3

 The final output infix expression is: '3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3'
```


## C

Takes RPN string from command line, string must be enclosed in double quotes. This is necessary since / and ^ are control characters for the command line. The second string, which can be any valid string, is optional and if supplied, the expression tree is printed out as it is built. The final expression is printed out in both cases.

```C

#include
#include
#include

char** components;
int counter = 0;

typedef struct elem{
	char data[10];
	struct elem* left;
	struct elem* right;
}node;

typedef node* tree;

int precedenceCheck(char oper1,char oper2){
	return (oper1==oper2)? 0:(oper1=='^')? 1:(oper2=='^')? 2:(oper1=='/')? 1:(oper2=='/')? 2:(oper1=='*')? 1:(oper2=='*')? 2:(oper1=='+')? 1:(oper2=='+')? 2:(oper1=='-')? 1:2;
}

int isOperator(char c){
	return (c=='+'||c=='-'||c=='*'||c=='/'||c=='^');
}

void inorder(tree t){
	if(t!=NULL){
		if(t->left!=NULL && isOperator(t->left->data[0])==1 && (precedenceCheck(t->data[0],t->left->data[0])==1 || (precedenceCheck(t->data[0],t->left->data[0])==0 && t->data[0]=='^'))){
			printf("(");
			inorder(t->left);
			printf(")");
		}
		else
			inorder(t->left);

		printf(" %s ",t->data);

		if(t->right!=NULL && isOperator(t->right->data[0])==1 && (precedenceCheck(t->data[0],t->right->data[0])==1 || (precedenceCheck(t->data[0],t->right->data[0])==0 && t->data[0]!='^'))){
			printf("(");
			inorder(t->right);
			printf(")");
		}
		else
			inorder(t->right);
	}
}

char* getNextString(){
	if(counter<0){
		printf("\nInvalid RPN !");
		exit(0);
	}
	return components[counter--];
}

tree buildTree(char* obj,char* trace){
	tree t = (tree)malloc(sizeof(node));

	strcpy(t->data,obj);

	t->right = (isOperator(obj[0])==1)?buildTree(getNextString(),trace):NULL;
	t->left = (isOperator(obj[0])==1)?buildTree(getNextString(),trace):NULL;

	if(trace!=NULL){
			printf("\n");
			inorder(t);
	}

	return t;
}

int checkRPN(){
	int i, operSum = 0, numberSum = 0;

	if(isOperator(components[counter][0])==0)
		return 0;

	for(i=0;i<=counter;i++)
		(isOperator(components[i][0])==1)?operSum++:numberSum++;

	return (numberSum - operSum == 1);
}

void buildStack(char* str){
	int i;
	char* token;

	for(i=0;str[i]!=00;i++)
		if(str[i]==' ')
			counter++;

	components = (char**)malloc((counter + 1)*sizeof(char*));

	token = strtok(str," ");

	i = 0;

	while(token!=NULL){
		components[i] = (char*)malloc(strlen(token)*sizeof(char));
		strcpy(components[i],token);
		token = strtok(NULL," ");
		i++;
	}
}

int main(int argC,char* argV[]){
	int i;
	tree t;

	if(argC==1)
		printf("Usage : %s  ",argV[0]);
	else{
		buildStack(argV[1]);

		if(checkRPN()==0){
			printf("\nInvalid RPN !");
			return 0;
		}

		t = buildTree(getNextString(),argV[2]);

		printf("\nFinal infix expression : ");
		inorder(t);
	}

	return 0;
}

```

Output, both final and traced outputs are shown:

```txt

C:\rosettaCode>rpn2Infix.exe "3 4 2 * 1 5 - 2 3 ^ ^ / +"

Final infix expression :  3  + ( 4  *  2 ) / ( 1  -  5 ) ^  2  ^  3
C:\rosettaCode>rpn2Infix.exe "1 2 + 3 4 + ^ 5 6 + ^"

Final infix expression : (( 1  +  2 ) ^ ( 3  +  4 )) ^ ( 5  +  6 )
C:\rosettaCode>rpn2Infix.exe "3 4 2 * 1 5 - 2 3 ^ ^ / +" yes

 3
 2
 2  ^  3
 5
 1
 1  -  5
( 1  -  5 ) ^  2  ^  3
 2
 4
 4  *  2
( 4  *  2 ) / ( 1  -  5 ) ^  2  ^  3
 3
 3  + ( 4  *  2 ) / ( 1  -  5 ) ^  2  ^  3
Final infix expression :  3  + ( 4  *  2 ) / ( 1  -  5 ) ^  2  ^  3
C:\rosettaCode>rpn2Infix.exe "1 2 + 3 4 + ^ 5 6 + ^" yes

 6
 5
 5  +  6
 4
 3
 3  +  4
 2
 1
 1  +  2
( 1  +  2 ) ^ ( 3  +  4 )
(( 1  +  2 ) ^ ( 3  +  4 )) ^ ( 5  +  6 )
Final infix expression : (( 1  +  2 ) ^ ( 3  +  4 )) ^ ( 5  +  6 )

```



## C#

{{trans|Java}}

```c#
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text.RegularExpressions;

namespace PostfixToInfix
{
    class Program
    {
        class Operator
        {
            public Operator(char t, int p, bool i = false)
            {
                Token = t;
                Precedence = p;
                IsRightAssociative = i;
            }

            public char Token { get; private set; }
            public int Precedence { get; private set; }
            public bool IsRightAssociative { get; private set; }
        }

        static IReadOnlyDictionary operators = new Dictionary
        {
            { '+', new Operator('+', 2) },
            { '-', new Operator('-', 2) },
            { '/', new Operator('/', 3) },
            { '*', new Operator('*', 3) },
            { '^', new Operator('^', 4, true) }
        };

        class Expression
        {
            public String ex;
            public Operator op;

            public Expression(String e)
            {
                ex = e;
            }

            public Expression(String e1, String e2, Operator o)
            {
                ex = String.Format("{0} {1} {2}", e1, o.Token, e2);
                op = o;
            }
        }

        static String PostfixToInfix(String postfix)
        {
            var stack = new Stack();

            foreach (var token in Regex.Split(postfix, @"\s+"))
            {
                char c = token[0];

                var op = operators.FirstOrDefault(kv => kv.Key == c).Value;
                if (op != null && token.Length == 1)
                {
                    Expression rhs = stack.Pop();
                    Expression lhs = stack.Pop();

                    int opPrec = op.Precedence;

                    int lhsPrec = lhs.op != null ? lhs.op.Precedence : int.MaxValue;
                    int rhsPrec = rhs.op != null ? rhs.op.Precedence : int.MaxValue;

                    if ((lhsPrec < opPrec || (lhsPrec == opPrec && c == '^')))
                        lhs.ex = '(' + lhs.ex + ')';

                    if ((rhsPrec < opPrec || (rhsPrec == opPrec && c != '^')))
                        rhs.ex = '(' + rhs.ex + ')';

                    stack.Push(new Expression(lhs.ex, rhs.ex, op));
                }
                else
                {
                    stack.Push(new Expression(token));
                }

                // print intermediate result
                Console.WriteLine("{0} -> [{1}]", token,
                    string.Join(", ", stack.Reverse().Select(e => e.ex)));
            }
            return stack.Peek().ex;
        }

        static void Main(string[] args)
        {
            string[] inputs = { "3 4 2 * 1 5 - 2 3 ^ ^ / +", "1 2 + 3 4 + ^ 5 6 + ^" };
            foreach (var e in inputs)
            {
                Console.WriteLine("Postfix : {0}", e);
                Console.WriteLine("Infix : {0}", PostfixToInfix(e));
                Console.WriteLine(); ;
            }
            Console.ReadLine();
        }
    }
}
```


```txt
3 -> [3]
4 -> [3, 4]
2 -> [3, 4, 2]
* -> [3, 4 * 2]
1 -> [3, 4 * 2, 1]
5 -> [3, 4 * 2, 1, 5]
- -> [3, 4 * 2, 1 - 5]
2 -> [3, 4 * 2, 1 - 5, 2]
3 -> [3, 4 * 2, 1 - 5, 2, 3]
^ -> [3, 4 * 2, 1 - 5, 2 ^ 3]
^ -> [3, 4 * 2, (1 - 5) ^ 2 ^ 3]
/ -> [3, 4 * 2 / (1 - 5) ^ 2 ^ 3]
+ -> [3 + 4 * 2 / (1 - 5) ^ 2 ^ 3]
Infix : 3 + 4 * 2 / (1 - 5) ^ 2 ^ 3

Postfix : 1 2 + 3 4 + ^ 5 6 + ^
1 -> [1]
2 -> [1, 2]
+ -> [1 + 2]
3 -> [1 + 2, 3]
4 -> [1 + 2, 3, 4]
+ -> [1 + 2, 3 + 4]
^ -> [(1 + 2) ^ (3 + 4)]
5 -> [(1 + 2) ^ (3 + 4), 5]
6 -> [(1 + 2) ^ (3 + 4), 5, 6]
+ -> [(1 + 2) ^ (3 + 4), 5 + 6]
^ -> [((1 + 2) ^ (3 + 4)) ^ (5 + 6)]
Infix : ((1 + 2) ^ (3 + 4)) ^ (5 + 6)
```



## C++

Very primitive implementation, doesn't use any parsing libraries which would shorten this greatly.

```Cpp

#include 
#include 
#include 
#include