{"id":13984,"date":"2021-04-30T17:29:53","date_gmt":"2021-04-30T11:59:53","guid":{"rendered":"https:\/\/java2blog.com\/?p=13984"},"modified":"2021-04-30T17:29:53","modified_gmt":"2021-04-30T11:59:53","slug":"prefix-to-postfix-java","status":"publish","type":"post","link":"https:\/\/java2blog.com\/prefix-to-postfix-java\/","title":{"rendered":"Convert Prefix to Postfix in Java"},"content":{"rendered":"\n<p>In this article we continue with another interesting problem related to <a href=\"https:\/\/java2blog.com\/implement-stack-using-array-in-java\/\" target=\"_blank\" rel=\"noopener noreferrer\">Stack data structure<\/a>. Given a Prefix expression, convert into its Equivalent Postfix Expression.<\/p>\n\n<div id=\"toc_container\" class=\"toc_light_blue no_bullets\"><p class=\"toc_title\">Table of Contents<\/p><ul class=\"toc_list\"><li><a href=\"#Algorithm_for_prefix_to_postfix\">Algorithm for prefix to postfix<\/a><\/li><li><a href=\"#Implementation_for_Prefix_to_postfix_conversion_in_java\">Implementation for Prefix to postfix conversion in java<\/a><\/li><li><a href=\"#Time_complexity\">Time complexity<\/a><\/li><\/ul><\/div>\n\n\n<p>It is recommended to first go through <a href=\"https:\/\/java2blog.com\/infix-to-postfix-java\/\" target=\"_blank\" rel=\"noopener noreferrer\">Infix to postfix<\/a> conversion for better understanding.<\/p>\n\n\n<p>Let us understand what we mean by Prefix and Postfix Expression.<\/p>\n\n\n<p>Prefix Expression is an expression where operators precede the operands. In simpler terms, the operators appear before the operands in the expression. They are of form : <code>op X Y<\/code>, op is operator and X,Y are operands. For Example: <code>+AB<\/code> is a Prefix Expression for Infix: A+B.<\/p>\n\n\n<p>Postfix Expressions re of the form <code>X Y op<\/code>, where operators come after operands. For Example: <code>AB+<\/code> is the Postfix for Infix: A+B.<\/p>\n\n\n<p>We need to convert Prefix to Postfix so for the Prefix Expression : <code>+ \/ AB * CD<\/code> , the Infix will be : <code>(A \/ B) + (C * D)<\/code>. Then on converting this infix the resultant Postfix Expression will be : <code>AB\/ CD* +<\/code> .<\/p>\n\n\n<p>Now, to convert Prefix expression into Postfix, we can try first converting the Prefix into Infix notation then convert the result into Postfix. But, we can do this in a single step by directly converting the Prefix into Postfix. Let us look at the Algorithm.<\/p>\n\n\n<h2 class=\"wp-block-heading\"><span id=\"Algorithm_for_prefix_to_postfix\">Algorithm for prefix to postfix<\/span><\/h2>\n\n\n<ol><li>We will start traversing the Prefix Expression from Right to Left, unlike what we did in Infix to Postfix Conversion. We will use a single Stack Postfix which will hold the operands and a part of evaluated Postfix expression. When we reach the end ( at i = -1) , the stack will hold the resultant Postfix expression.<\/li><li>For each character we encounter, we consider two cases:<ol><li>f the Character is a Operand we push it into the Postfix Stack.<\/li><li>If the Character is a Operator we pop two elements from the Stack, add two elements together followed with the operator and push the result back to the Postfix Stack again for future evaluation. This will be the part of total Postfix.<\/li><\/ol><\/li><li>When we come to end of the String traversing from Right (Length-1) to Left (0) , at i=-1 we stop and at the at the end the Postfix stack contain only one value, which will be the resultant Postfix Expression.<\/li><\/ol>\n\n\n<p>Now, let us understand this algorithm with an example. Consider the Prefix expression :&nbsp;<code>\/+AB-CD<\/code>. The Infix for this is : ((A + B) \/ (C &#8211; D)).<\/p>\n\n\n<p>Let us evaluate the given expression step by step. We take decisions when we encounter Operator or Operands. The steps are:<\/p>\n\n\n<ul>\n<li>\n<p><code>Step 1:<\/code> We start iterating from the end of the string (length &#8211; 1 = 7 &#8211; 1 = 6 ) to start index. At <code>i=6<\/code>, we have char = &#8216;D&#8217;, an operand so we push it into the Postfix Stack. At <code>i=5<\/code>, we have char = &#8216;C&#8217;, we push it into the stack. The Postfix stack now is:<\/p>\n\n\n\n<div class=\"wp-block-image\"><figure class=\"aligncenter size-large is-resized\"><img decoding=\"async\" loading=\"lazy\" src=\"https:\/\/java2blog.com\/wp-content\/uploads\/2021\/04\/Pre_to_Postfix.png\" alt=\"\" class=\"wp-image-13995\" width=\"187\" height=\"217\" srcset=\"https:\/\/java2blog.com\/wp-content\/uploads\/2021\/04\/Pre_to_Postfix.png 294w, https:\/\/java2blog.com\/wp-content\/uploads\/2021\/04\/Pre_to_Postfix-259x300.png 259w\" sizes=\"(max-width: 187px) 100vw, 187px\" \/><\/figure><\/div>\n\n<\/li>\n<li>\n\n<p><code>Step 2:<\/code> We continue iteration at <code>i=4<\/code>, char = &#8216;-&#8216; , an operator, so we pop two operands from stack and add them with the operator in the same order. We then push the result (CD-) into the Postfix stack again for future evaluation. The stack now is: <\/p>\n\n\n\n<div class=\"wp-block-image\"><figure class=\"aligncenter size-large is-resized\"><img decoding=\"async\" loading=\"lazy\" src=\"https:\/\/java2blog.com\/wp-content\/uploads\/2021\/04\/Pre_to_Postfix-1.png\" alt=\"\" class=\"wp-image-13996\" width=\"215\" height=\"249\" srcset=\"https:\/\/java2blog.com\/wp-content\/uploads\/2021\/04\/Pre_to_Postfix-1.png 294w, https:\/\/java2blog.com\/wp-content\/uploads\/2021\/04\/Pre_to_Postfix-1-259x300.png 259w\" sizes=\"(max-width: 215px) 100vw, 215px\" \/><figcaption><strong>Now, CD- is an Operand.<\/strong><\/figcaption><\/figure><\/div>\n\n<\/li>\n<li>\n\n<p><code>Step 3:<\/code> Now at <code>i=3<\/code>, we have char = &#8216;B&#8217;, and at <code>i=2<\/code>, we have char = &#8216;A&#8217;, since both are operands so we push them into stack one by one . The Postfix stack is now:<\/p>\n\n\n\n<div class=\"wp-block-image\"><figure class=\"aligncenter size-large is-resized\"><img decoding=\"async\" loading=\"lazy\" src=\"https:\/\/java2blog.com\/wp-content\/uploads\/2021\/04\/Pre_to_Postfix-2.png\" alt=\"\" class=\"wp-image-13997\" width=\"222\" height=\"258\" srcset=\"https:\/\/java2blog.com\/wp-content\/uploads\/2021\/04\/Pre_to_Postfix-2.png 294w, https:\/\/java2blog.com\/wp-content\/uploads\/2021\/04\/Pre_to_Postfix-2-259x300.png 259w\" sizes=\"(max-width: 222px) 100vw, 222px\" \/><\/figure><\/div>\n\n<\/li>\n\n<li>\n<p><code>Step 4:<\/code> At <code>i=1<\/code>, char = &#8216;+&#8217;, an Operator. So we perform Step 2 again by popping and adding the two elements with the operator and then push the result (AB+) back to stack. The Postfix stack now looks :<\/p>\n\n\n\n<div class=\"wp-block-image\"><figure class=\"aligncenter size-large is-resized\"><img decoding=\"async\" loading=\"lazy\" src=\"https:\/\/java2blog.com\/wp-content\/uploads\/2021\/04\/Pre_to_Postfix-3.png\" alt=\"\" class=\"wp-image-13998\" width=\"179\" height=\"208\" srcset=\"https:\/\/java2blog.com\/wp-content\/uploads\/2021\/04\/Pre_to_Postfix-3.png 294w, https:\/\/java2blog.com\/wp-content\/uploads\/2021\/04\/Pre_to_Postfix-3-259x300.png 259w\" sizes=\"(max-width: 179px) 100vw, 179px\" \/><\/figure><\/div>\n\n<\/li>\n\n<li>\n<p><code>Step 5:<\/code> Finally At <code>i=0<\/code>, we get char =&#8217;\/&#8217;, an Operator so we pop both the operands (<code>AB+<\/code> and <code>CD-<\/code>) and add it with the operator. We stop iteration as we reached index 0. The Postfix stack at the end now contains our resultant Postfix Expression which is :<\/p>\n\n\n\n<div class=\"wp-block-image\"><figure class=\"aligncenter size-large is-resized\"><img decoding=\"async\" loading=\"lazy\" src=\"https:\/\/java2blog.com\/wp-content\/uploads\/2021\/04\/Pre_to_Postfix-4.png\" alt=\"\" class=\"wp-image-13999\" width=\"208\" height=\"241\" srcset=\"https:\/\/java2blog.com\/wp-content\/uploads\/2021\/04\/Pre_to_Postfix-4.png 294w, https:\/\/java2blog.com\/wp-content\/uploads\/2021\/04\/Pre_to_Postfix-4-259x300.png 259w\" sizes=\"(max-width: 208px) 100vw, 208px\" \/><figcaption><strong>The Postfix is: AB+ CD- \/<\/strong><\/figcaption><\/figure><\/div>\n<\/li>\n<\/ul>\n\n\n<h2 class=\"wp-block-heading\"><span id=\"Implementation_for_Prefix_to_postfix_conversion_in_java\">Implementation for Prefix to postfix conversion in java<\/span><\/h2>\n\n\n<p>Let us look at the implementation of the above example in JAVA:<\/p>\n\n\n<pre class=\"wp-block-code\"><code>import java.util.*;\n\nclass PrefixToPostfix \n{\n\n  \/\/ check if character is operator or not\n  static boolean isOperator(char ch)\n  {\n    if(ch == '+' || ch == '-' || ch == '*' || ch == '\/')\n    return true;\n\n    return false;\n  }\n\n  \/\/ Convert prefix to Postfix expression\n  static String convertPrefixToPostfix(String prefix)\n  {\n    Stack&lt;String&gt; postFix = new Stack&lt;&gt;();\n\n    \/\/ length of prefix expression\n    int n = prefix.length();\n\n    \/\/ reading from right to left\n    for (int i = n - 1; i &gt;= 0; i--)\n    {\n      char ch= prefix.charAt(i);\n\n      \/\/ check if symbol is operator\n      if (isOperator(ch))\n      {\n      \/\/ pop two operands from stack\n      String first = postFix.pop();\n\n      String second = postFix.pop();\n\n      \/\/ concat the operands and operator to form Postfix\n      String temp_postFix = first + second + ch;\n\n      \/\/ Push the partly evaluated postfix back to stack\n      postFix.push(temp_postFix);\n      }\n\n      \/\/ if symbol is an operand\n      else \n      { \n      \/\/ push the operand to the stack\n      postFix.push(ch + \"\");\n      }\n    }\n\n    \/\/ stack contains only the Postfix expression\n    return postFix.pop();\n  }\n\n  public static void main(String args&#091;])\n  {\n    String prefix = \"\/+AB-CD\";      \/\/ Infix is : (A+B) \/ (C-D).\n    System.out.println(\"The Prefix Expression is: \"+prefix);\n    String result = convertPrefixToPostfix(prefix);\n    System.out.println(\"The Equivalent Postfix is : \"+ result);  \n\n    System.out.println();\n\n    prefix = \"*+AB\/-CDE\";          \/\/ Infix is : (A+B) * ((C-D)\/E).\n    System.out.println(\"The Prefix Expression is: \"+prefix);\n    result = convertPrefixToPostfix(prefix);\n    System.out.println(\"The Equivalent Postfix is : \"+ result);  \n\n  }\n\n}<\/code><\/pre>\n\n\n<p><code>Output:<\/code><\/p>\n\n\n<pre class=\"wp-block-code\"><code>The Prefix Expression is: \/+AB-CD\nThe Equivalent Postfix is : AB+CD-\/\n\nThe Prefix Expression is: *+AB\/-CDE\nThe Equivalent Postfix is : AB+CD-E\/*<\/code><\/pre>\n\n\n<p>We have implemented two examples. Now let us look at the Time Complexity of our approach.<\/p>\n\n<h2><span id=\"Time_complexity\">\nTime complexity\n<\/span><\/h2>\n\n<p><code>Time Complexity:<\/code> As we traverse the whole input string once and the stack operations require constant time, the overall <a href=\"https:\/\/java2blog.com\/introduction-to-complexity-of-algorithm\" target=\"_blank\" rel=\"noopener noreferrer\">time complexity<\/a> is <code>O(n)<\/code>, n is the length of Prefix Expression.<\/p>\n\n\n<p>So that&#8217;s all about how to convert Prefix to postfix in java. You can try with different examples and execute this code for better understanding.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Learn about how to convert Prefix to Postfix in java.<\/p>\n","protected":false},"author":18,"featured_media":14045,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"inline_featured_image":false,"_mi_skip_tracking":false},"categories":[182,12],"tags":[],"_links":{"self":[{"href":"https:\/\/java2blog.com\/wp-json\/wp\/v2\/posts\/13984"}],"collection":[{"href":"https:\/\/java2blog.com\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/java2blog.com\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/java2blog.com\/wp-json\/wp\/v2\/users\/18"}],"replies":[{"embeddable":true,"href":"https:\/\/java2blog.com\/wp-json\/wp\/v2\/comments?post=13984"}],"version-history":[{"count":0,"href":"https:\/\/java2blog.com\/wp-json\/wp\/v2\/posts\/13984\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/java2blog.com\/wp-json\/wp\/v2\/media\/14045"}],"wp:attachment":[{"href":"https:\/\/java2blog.com\/wp-json\/wp\/v2\/media?parent=13984"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/java2blog.com\/wp-json\/wp\/v2\/categories?post=13984"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/java2blog.com\/wp-json\/wp\/v2\/tags?post=13984"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}