{"id":9445,"date":"2022-08-30T09:50:27","date_gmt":"2022-08-30T09:50:27","guid":{"rendered":"https:\/\/www.prepbytes.com\/blog\/?p=9445"},"modified":"2022-10-10T04:11:06","modified_gmt":"2022-10-10T04:11:06","slug":"conversion-of-postfix-expression-to-infix-expression","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/conversion-of-postfix-expression-to-infix-expression\/","title":{"rendered":"Conversion of Postfix expression to Infix expression"},"content":{"rendered":"

\"\"<\/p>\n

Problem statement<\/h3>\n

Given an arithmetic expression<\/a> in postfix notation , convert it into the equivalent infix notation. <\/p>\n

Sample example :<\/strong><\/p>\n

Postfix Input : abc\/-ad\/e-* <\/p>\n

Infix output : ((a-(b\/c))*((a\/d)-e))<\/p>\n

Postfix input : ab+cd+*<\/p>\n

Infix Output : ((a+b)*(c+d)) <\/p>\n

Introduction to Arithmetic Notations<\/h3>\n

Any arithmetic expression consists of operands and operators . The way we arrange our operators and operands to write the arithmetic expression is called Notation .<\/p>\n

There are three different notations for writing the Arithmetic expression :<\/p>\n

    \n
  • \n

    Infix expression<\/strong>\nAn expression is said to be in infix notation if the operators in the expression are placed in between the operands on which the operator works.
    \nFor example => a + b * c\nInfix expressions are easy to read ,write and understand by humans , but not by computer\nIt\u2019s costly , in terms of time and space , to process Infix expressions <\/p>\n<\/li>\n

  • \n

    Postfix expression (Reverse Polish Notation)<\/strong>\nAn expression is said to be in postfix notation if the operators in the expression are placed after the operands on which the operator works.\nFor example => abc*+\nIt\u2019s most used to notation for evaluating arithmetic expression <\/p>\n<\/li>\n

  • \n

    Prefix expression (or Polish Notation )<\/strong>\nAn expression is said to be in prefix notation if the operators in the expression are placed before the operands on which the operator works.\nFor example => +a*bc<\/p>\n<\/li>\n<\/ul>\n

    Precedence order and Associativity of Operators<\/h3>\n\n
    Precedence<\/td>Type<\/td>Operators<\/td>Associativity<\/td><\/tr>
    1<\/td>Postfix<\/td>() [] -> . ++ —<\/td>Left to Right<\/td><\/tr>
    2<\/td>Unary<\/td>+ – ! ~ ++ — (type)* & sizeof<\/td>Right to Left<\/td><\/tr>
    3<\/td>Multiplicative<\/td>* \/ %<\/td>Left to Right<\/td><\/tr>
    4<\/td>Additive<\/td>+ –<\/td>Left to Right<\/td><\/tr>
    5<\/td>Shift<\/td><<, >><\/td>Left to Right<\/td><\/tr>
    6<\/td>Relational<\/td>< <= > >=<\/td>Left to Right<\/td><\/tr>
    7<\/td>Equality<\/td>== !=<\/td>Left to Right<\/td><\/tr>
    8<\/td>Bitwise AND<\/td>&<\/td>Left to Right<\/td><\/tr>
    9<\/td>Bitwise XOR<\/td>^<\/td>Left to Right<\/td><\/tr>
    10<\/td>Bitwise OR<\/td>|<\/td>Left to Right<\/td><\/tr>
    11<\/td>Logical AND<\/td>&&<\/td>Left to Right<\/td><\/tr>
    12<\/td>Logical OR<\/td>||<\/td>Left to Right<\/td><\/tr>
    13<\/td>Conditional<\/td>?:<\/td>Right to Left<\/td><\/tr>
    14<\/td>Assignment<\/td>= += -+ *= \/= %= >>= <<= &= ^= |=<\/td>Right to Left<\/td><\/tr>
    15<\/td>Comma<\/td>,<\/td>Left to Right<\/td><\/tr><\/tbody><\/table><\/figure>\n\n

    In this article we are gonna talk about how to convert postfix expressions into infix expressions .\nFor the simplicity and understanding purpose , we will consider only \u2018+\u2019 , \u2018-\u2019 ,\u2019\/\u2019 , \u2018*\u2019 , \u2018(\u2019 and \u2018)\u2019 .<\/p>\n

    Approach<\/h3>\n

    For converting Postfix to infix we use a stack . The stack helps us store the operands. Whenever an operator is found , we pop two operands from the stack and push a new operand , which is the result of the current operator on the popped operands, into the stack with parenthesis . The final element at the top of the stack will be our infix expression .<\/p>\n

    Algorithm<\/h3>\n
      \n
    1. \n

      Scan all symbols one by one from left to right in the given postfix expression .<\/p>\n<\/li>\n

    2. \n

      If the reading symbol is an operand , push it into the stack .<\/p>\n<\/li>\n

    3. \n

      If the reading symbol is an operator , then\na. Pop two expression from the stack , operand1 and operand2 , which is operand for the current operator\nb. Push \u201c(\u201c + operand2 + operator + operand1 + \u201c)\u201d into the stack <\/p>\n<\/li>\n

    4. \n

      If there is no symbol left then stop the process . Top of the stack will have the required infix expression .<\/p>\n<\/li>\n<\/ol>\n

      NOTE :<\/strong> \u2018+\u2019 denotes the concatenation of strings . <\/p>\n

      Postfix to infix conversion example with dry run<\/h3>\n

      \"\"<\/p>\n

      Implementation<\/h3>\n\t\t\t\t\t\t