{"id":315,"date":"2016-12-11T17:08:12","date_gmt":"2016-12-11T09:08:12","guid":{"rendered":"http:\/\/blog.messi.moe\/?p=315"},"modified":"2016-12-11T17:43:17","modified_gmt":"2016-12-11T09:43:17","slug":"infix-to-postfix","status":"publish","type":"post","link":"https:\/\/blog.messi.moe\/?p=315","title":{"rendered":"Infix to Postfix and Evaluation of Postfix"},"content":{"rendered":"<pre><code class=\"python\">def infix2postfix(infix):\n  postfix=[]\n  digits=['1','2','3','4','5','6','7','8','9','0']\n  ohigh=['*','\/']\n  olow=['+','-']\n  s=[]\n  i=0\n  while(i&lt;len(infix)):\n    if infix[i] in digits:\n      postfix.append(infix[i])\n    if infix[i]=='(':\n      s.append(infix[i])\n    if infix[i] in olow:\n      while(len(s)!=0 and s[len(s)-1] in ohigh):\n        postfix.append(s[len(s)-1])\n        s.pop()\n      else:\n        s.append(infix[i])\n    if infix[i] in ohigh:\n      s.append(infix[i])\n    if infix[i]==')':\n      while(len(s)!=0 and s[len(s)-1]!='('):\n        postfix.append(s[len(s)-1])\n        s.pop()\n      if s[len(s)-1]=='(':\n        s.pop()\n    i+=1\n  while(len(s)!=0):\n    postfix.append(s[len(s)-1])\n    s.pop()\n  return postfix\nprint infix2postfix(\"6-((5+4)*(3-2)+1)\")\n\ndef cal(n2,n1,operation):\n  if operation=='+':\n    return (int(n1)+int(n2))\n  if operation=='-':\n    return (int(n1)-int(n2))\n  if operation=='*':\n    return (int(n1)*int(n2))\n  if operation=='\/':\n    return d(int(n1)\/int(n2))\n\ndef evaluatePostfix(postfix):\n  digits=['1','2','3','4','5','6','7','8','9','0']\n  op=['+','-','*','\/']\n  s=[]\n  postfix=postfix[::-1]\n  #print postfix\n  while(len(postfix)&gt;1):\n    if postfix[len(postfix)-1] in digits:\n      s.append(postfix[len(postfix)-1])\n      postfix.pop()\n    if postfix[len(postfix)-1] in op:\n      operation=postfix[len(postfix)-1]\n      postfix.pop()\n      n1=s[len(s)-1]\n      #print n1\n      s.pop()\n      n2=s[len(s)-1]\n      #print n2\n      s.pop()\n      s.append(cal(n1,n2,operation))\n    #print postfix,s\n  if len(postfix)==1 and len(s)==2:\n    return cal(int(s[1]),int(s[0]),postfix[0])\n\nprint evaluatePostfix(infix2postfix(\"6-((5+4)*(3-2)+1)\"))\n<\/code><\/pre>\n<p>Output:<\/p>\n<pre><code class=\"bash\">Python 2.7.10 (default, Jul 14 2015, 19:46:27)\n[GCC 4.8.2] on linux\n\n['6', '5', '4', '+', '3', '2', '-', '*', '1', '+', '-']\n-4\n<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"<pre><code class=\"python\">def infix2postfix(infix):\n  postfix=[]\n  digits=['1','2','3','4','5','6','7','8','9','0']\n  ohigh=['*','\/']\n  olow=['+','-']\n  s=[]\n  i=0\n  while(i&lt;len(infix)):\n    if infix[i] in digits:\n      postfix.append(infix[i])\n    if infix[i]=='(':\n      s.append(infix[i])\n    if infix[i] in olow:\n      while(len(s)!=0 and s[len(s)-1] in ohigh):\n        postfix.append(s[len(s)-1])\n        s.pop()\n      else:\n        s.append(infix[i])\n    if infix[i] in ohigh:\n      s.append(infix[i])\n    if infix[i]==')':\n      while(len(s)!=0 and s[len(s)-1]!='('):\n        postfix.append(s[len(s)-1])\n        s.pop()\n      if s[len(s)-1]=='(':\n        s.pop()\n    i+=1\n  while(len(s)!=0):\n    postfix.append(s[len(s)-1])\n    s.pop()\n  return postfix\nprint infix2postfix(\"6-((5+4)*(3-2)+1)\")\n\ndef cal(n2,n1,operation):\n  if operation=='+':\n    return (int(n1)+int(n2))\n  if operation=='-':\n    return (int(n1)-int(n2))\n  if operation=='*':\n    return (int(n1)*int(n2))\n  if operation=='\/':\n    return d(int(n1)\/int(n2))\n\ndef evaluatePostfix(postfix):\n  digits=['1','2','3','4','5','6','7','8','9','0']\n  op=['+','-','*','\/']\n  s=[]\n  postfix=postfix[::-1]\n  #print postfix\n  while(len(postfix)&gt;1):\n    if postfix[len(postfix)-1] in digits:\n      s.append(postfix[len(postfix)-1])\n      postfix.pop()\n    if postfix[len(postfix)-1] in op:\n      operation=postfix[len(postfix)-1]\n      postfix.pop()\n      n1=s[len(s)-1]\n      #print n1\n      s.pop()\n      n2=s[len(s)-1]\n      #print n2\n      s.pop()\n      s.append(cal(n1,n2,operation))\n    #print postfix,s\n  if len(postfix)==1 and len(s)==2:\n    return cal(int(s[1]),int(s[0]),postfix[0])\n\nprint evaluatePostfix(infix2postfix(\"6-((5+4)*(3-2)+1)\"))\n<\/code><\/pre>\n<p>Output:<\/p>\n<pre><code class=\"bash\">Python 2.7.10 (default, Jul 14 2015, 19:46:27)\n[GCC 4.8.2] on linux\n\n['6', '5', '4', '+', '3', '2', '-', '*', '1', '+', '-']\n-4\n<\/code><\/pre>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[1],"tags":[],"_links":{"self":[{"href":"https:\/\/blog.messi.moe\/index.php?rest_route=\/wp\/v2\/posts\/315"}],"collection":[{"href":"https:\/\/blog.messi.moe\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blog.messi.moe\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blog.messi.moe\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/blog.messi.moe\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=315"}],"version-history":[{"count":18,"href":"https:\/\/blog.messi.moe\/index.php?rest_route=\/wp\/v2\/posts\/315\/revisions"}],"predecessor-version":[{"id":334,"href":"https:\/\/blog.messi.moe\/index.php?rest_route=\/wp\/v2\/posts\/315\/revisions\/334"}],"wp:attachment":[{"href":"https:\/\/blog.messi.moe\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=315"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blog.messi.moe\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=315"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blog.messi.moe\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=315"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}