{"id":9449,"date":"2022-08-30T09:39:29","date_gmt":"2022-08-30T09:39:29","guid":{"rendered":"https:\/\/www.prepbytes.com\/blog\/?p=9449"},"modified":"2023-04-25T12:24:57","modified_gmt":"2023-04-25T12:24:57","slug":"conversion-of-prefix-to-postfix-notation","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/conversion-of-prefix-to-postfix-notation\/","title":{"rendered":"Conversion of Prefix to Postfix notation"},"content":{"rendered":"

\"\"<\/p>\n

We have been given an arithmetic expression, and we have to write a program that converts prefix to postfix. The expression is given in the form of a string that contains alphabets i.e a-z or A-Z denotes operands and operators are ( +, \u2013, *, \/ ). In short, we have to program a prefix to postfix converter.<\/p>\n

Here are some examples, that will give you a clear understanding of what is exactly meant by prefix to postfix conversion.<\/p>\n

Example 1:<\/strong><\/p>\n

Input:<\/strong> -a\/bc-\/ade\nOutput:<\/strong> abc\/-ad\/e-<\/em><\/p>\n

Example 2:<\/strong><\/p>\n

Input:<\/strong> ab\nOutput:<\/strong> ab<\/em><\/p>\n

Before discussing the solution of the prefix to postfix. Let us first discuss arithmetic notations in brief.<\/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,<\/strong><\/p>\n

    a + b * c<\/code><\/pre>\n
    Infix expressions are easy to read ,write and understand by  humans ,  but not by computer. It\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,<\/strong><\/p>\n
    abc*+<\/code><\/pre>\n
    It\u2019s the most used notation for evaluating arithmetic expressions<\/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,<\/strong><\/p>\n
    +a*bc<\/code><\/pre>\n<\/li>\n<\/ul>\n
    Precedence Order and  Associativity of Operators<\/h3>\n
    The precedence order of operators is given in the below table.<\/p>\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 going to see how we can convert prefix to postfix expressions. For simplicity and understanding purposes, we will consider only \u2018+\u2019, \u2018-\u2019, \u2019\/\u2019, \u2018*\u2019, \u2018(\u2019 and \u2018)\u2019.<\/p>\n
    Prefix to Postfix Conversion<\/h3>\n
    To convert a prefix to postfix expression, we will use a stack to hold the operands. Whenever an operator is found, we pop two operands from the stack and push a new operand. The final element at the top of the stack will be our postfix expression.<\/p>\n
    Algorithm for Prefix to Postfix Converter<\/h3>\n
    Here is the stepwise algorithm to convert prefix to postfix expressions.<\/p>\n
      \n
    • Step 1<\/strong>: Scan all symbols one by one from right to left in the given prefix expression.<\/li>\n
    • Step 2<\/strong>: If the reading symbol is an operand, push it into the stack.<\/li>\n
    • Step 3<\/strong>: If the reading symbol is an operator, then \n
        \n
      • a.<\/strong> Pop two expressions from the stack, operand1, and operand2, which is the operand for the current operator <\/li>\n
      • b.<\/strong> Push operand1 + operand2 + operator into the stack<\/li>\n<\/ul><\/li>\n
      • Step 4<\/strong>: If there is no symbol left then stop the process. The top of the stack will have the required postfix expression.<\/li>\n<\/ul>\n
        NOTE :<\/strong> \u2018+\u2019 denotes the concatenation of strings . <\/p>\n
        Dry Run for Prefix to Postfix Conversion<\/h3>\n
        \"\"<\/p>\n
        Code Implementation of Prefix to Postfix Converter<\/h3>\n
        Here is the code to perform prefix to postfix conversion in C++.<\/p>\n\t\t\t\t\t\t