Created
April 3, 2020 08:20
-
-
Save arghyadeep99/7370d75fa4a92baaf50e3caf74017764 to your computer and use it in GitHub Desktop.
SPCC IA-2.ipynb
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| { | |
| "nbformat": 4, | |
| "nbformat_minor": 0, | |
| "metadata": { | |
| "colab": { | |
| "name": "SPCC IA-2.ipynb", | |
| "provenance": [], | |
| "authorship_tag": "ABX9TyMY1wM/GnLvTM6u1kxovQ2/", | |
| "include_colab_link": true | |
| }, | |
| "kernelspec": { | |
| "name": "python3", | |
| "display_name": "Python 3" | |
| } | |
| }, | |
| "cells": [ | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "id": "view-in-github", | |
| "colab_type": "text" | |
| }, | |
| "source": [ | |
| "<a href=\"https://colab.research.google.com/gist/arghyadeep99/7370d75fa4a92baaf50e3caf74017764/spcc-ia-2.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "metadata": { | |
| "id": "WC2qqNMWEYtB", | |
| "colab_type": "code", | |
| "colab": {} | |
| }, | |
| "source": [ | |
| "import graphviz\n", | |
| "\n", | |
| "gv = graphviz.Graph(format = 'png')\n", | |
| "\n", | |
| "grammar = {\n", | |
| " 'E': [{'E+T':1},{'T':2}],\n", | |
| " 'T': [{'T*F':3},{'F':4}],\n", | |
| " 'F': [{'val':5}]\n", | |
| "}\n", | |
| "\n", | |
| "subs = {\n", | |
| " 1:'+',\n", | |
| " 2:'',\n", | |
| " 3:'*',\n", | |
| " 4:'',\n", | |
| " 5:'{}'\n", | |
| "}" | |
| ], | |
| "execution_count": 0, | |
| "outputs": [] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "metadata": { | |
| "id": "ks3FkvBMEgFt", | |
| "colab_type": "code", | |
| "colab": { | |
| "base_uri": "https://localhost:8080/", | |
| "height": 34 | |
| }, | |
| "outputId": "b544e241-42d3-484b-a67a-5112c4f54a7a" | |
| }, | |
| "source": [ | |
| "infix = list(input('Enter the infix expression: '))" | |
| ], | |
| "execution_count": 2, | |
| "outputs": [ | |
| { | |
| "output_type": "stream", | |
| "text": [ | |
| "Enter the infix expression: 4+9*6\n" | |
| ], | |
| "name": "stdout" | |
| } | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "metadata": { | |
| "id": "GSIPKKZyFM6C", | |
| "colab_type": "code", | |
| "colab": { | |
| "base_uri": "https://localhost:8080/", | |
| "height": 119 | |
| }, | |
| "outputId": "99490256-e989-44f2-e02c-7b6eed550ec5" | |
| }, | |
| "source": [ | |
| "print(\"Production Grammar:\")\n", | |
| "for k,v in grammar.items():\n", | |
| " for i in v:\n", | |
| " for k_grammar, v_grammar in i.items():\n", | |
| " print(f'{k} -> {k_grammar}')" | |
| ], | |
| "execution_count": 3, | |
| "outputs": [ | |
| { | |
| "output_type": "stream", | |
| "text": [ | |
| "Production Grammar:\n", | |
| "E -> E+T\n", | |
| "E -> T\n", | |
| "T -> T*F\n", | |
| "T -> F\n", | |
| "F -> val\n" | |
| ], | |
| "name": "stdout" | |
| } | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "metadata": { | |
| "id": "ul0oLZJXB8YU", | |
| "colab_type": "code", | |
| "colab": { | |
| "base_uri": "https://localhost:8080/", | |
| "height": 702 | |
| }, | |
| "outputId": "0bd36bb9-af18-4348-8f05-590f812affcc" | |
| }, | |
| "source": [ | |
| "operators = []\n", | |
| "numbers = []\n", | |
| "\n", | |
| "for char in infix:\n", | |
| " if char.isdigit():\n", | |
| " numbers.append(int(char))\n", | |
| " else:\n", | |
| " operators.append(char)\n", | |
| "\n", | |
| "traversal = ['E', 'E1', 'T', 'F', 'val1', 5, 4, 2, '+', 'T1', 'T2', 'F1', 'val2', 5, 4, '*', 'F2', 'val3', 5, 3, 1]\n", | |
| "\n", | |
| "#Printing the parse tree\n", | |
| "\n", | |
| "j = 0\n", | |
| "for i in range(len(traversal)-1): \n", | |
| " if type(traversal[i]) == int and type(traversal[i+1]) == int:\n", | |
| " j -= 1\n", | |
| " #continue\n", | |
| " elif type(traversal[i]) == int and type(traversal[i+1]) == str:\n", | |
| " gv.edge(str(traversal[j-1]), str(traversal[i+1]))\n", | |
| " gv.edge(str(traversal[j-1]), str(traversal[i+2]))\n", | |
| " j = i+2\n", | |
| " elif type(traversal[i]) == str and type(traversal[i+1]) == int:\n", | |
| " j -= 1\n", | |
| " elif not type(traversal[i+1]) == int and traversal[i] not in ['+', '*']:\n", | |
| " gv.edge(str(traversal[i]), str(traversal[i+1]))\n", | |
| " j+=1\n", | |
| "\n", | |
| "print(gv)\n", | |
| "gv" | |
| ], | |
| "execution_count": 4, | |
| "outputs": [ | |
| { | |
| "output_type": "stream", | |
| "text": [ | |
| "graph {\n", | |
| "\tE -- E1\n", | |
| "\tE1 -- T\n", | |
| "\tT -- F\n", | |
| "\tF -- val1\n", | |
| "\tE -- \"+\"\n", | |
| "\tE -- T1\n", | |
| "\tT1 -- T2\n", | |
| "\tT2 -- F1\n", | |
| "\tF1 -- val2\n", | |
| "\tT1 -- \"*\"\n", | |
| "\tT1 -- F2\n", | |
| "\tF2 -- val3\n", | |
| "}\n" | |
| ], | |
| "name": "stdout" | |
| }, | |
| { | |
| "output_type": "execute_result", | |
| "data": { | |
| "text/plain": [ | |
| "<graphviz.dot.Graph at 0x7f5790554ba8>" | |
| ], | |
| "image/svg+xml": "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n<!-- Generated by graphviz version 2.40.1 (20161225.0304)\n -->\n<!-- Title: %3 Pages: 1 -->\n<svg width=\"278pt\" height=\"332pt\"\n viewBox=\"0.00 0.00 278.00 332.00\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 328)\">\n<title>%3</title>\n<polygon fill=\"#ffffff\" stroke=\"transparent\" points=\"-4,4 -4,-328 274,-328 274,4 -4,4\"/>\n<!-- E -->\n<g id=\"node1\" class=\"node\">\n<title>E</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"99\" cy=\"-306\" rx=\"27\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"99\" y=\"-302.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">E</text>\n</g>\n<!-- E1 -->\n<g id=\"node2\" class=\"node\">\n<title>E1</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"27\" cy=\"-234\" rx=\"27\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"27\" y=\"-230.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">E1</text>\n</g>\n<!-- E--E1 -->\n<g id=\"edge1\" class=\"edge\">\n<title>E--E1</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M83.7307,-290.7307C71.512,-278.512 54.4602,-261.4602 42.2473,-249.2473\"/>\n</g>\n<!-- + -->\n<g id=\"node6\" class=\"node\">\n<title>+</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"99\" cy=\"-234\" rx=\"27\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"99\" y=\"-230.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">+</text>\n</g>\n<!-- E--+ -->\n<g id=\"edge5\" class=\"edge\">\n<title>E--+</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M99,-287.8314C99,-277 99,-263.2876 99,-252.4133\"/>\n</g>\n<!-- T1 -->\n<g id=\"node7\" class=\"node\">\n<title>T1</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"171\" cy=\"-234\" rx=\"27\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"171\" y=\"-230.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">T1</text>\n</g>\n<!-- E--T1 -->\n<g id=\"edge6\" class=\"edge\">\n<title>E--T1</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M114.2693,-290.7307C126.488,-278.512 143.5398,-261.4602 155.7527,-249.2473\"/>\n</g>\n<!-- T -->\n<g id=\"node3\" class=\"node\">\n<title>T</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"27\" cy=\"-162\" rx=\"27\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"27\" y=\"-158.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">T</text>\n</g>\n<!-- E1--T -->\n<g id=\"edge2\" class=\"edge\">\n<title>E1--T</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M27,-215.8314C27,-205 27,-191.2876 27,-180.4133\"/>\n</g>\n<!-- F -->\n<g id=\"node4\" class=\"node\">\n<title>F</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"27\" cy=\"-90\" rx=\"27\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"27\" y=\"-86.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">F</text>\n</g>\n<!-- T--F -->\n<g id=\"edge3\" class=\"edge\">\n<title>T--F</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M27,-143.8314C27,-133 27,-119.2876 27,-108.4133\"/>\n</g>\n<!-- val1 -->\n<g id=\"node5\" class=\"node\">\n<title>val1</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"27\" cy=\"-18\" rx=\"27\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"27\" y=\"-14.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">val1</text>\n</g>\n<!-- F--val1 -->\n<g id=\"edge4\" class=\"edge\">\n<title>F--val1</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M27,-71.8314C27,-61 27,-47.2876 27,-36.4133\"/>\n</g>\n<!-- T2 -->\n<g id=\"node8\" class=\"node\">\n<title>T2</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"99\" cy=\"-162\" rx=\"27\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"99\" y=\"-158.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">T2</text>\n</g>\n<!-- T1--T2 -->\n<g id=\"edge7\" class=\"edge\">\n<title>T1--T2</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M155.7307,-218.7307C143.512,-206.512 126.4602,-189.4602 114.2473,-177.2473\"/>\n</g>\n<!-- * -->\n<g id=\"node11\" class=\"node\">\n<title>*</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"171\" cy=\"-162\" rx=\"27\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"171\" y=\"-158.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">*</text>\n</g>\n<!-- T1--* -->\n<g id=\"edge10\" class=\"edge\">\n<title>T1--*</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M171,-215.8314C171,-205 171,-191.2876 171,-180.4133\"/>\n</g>\n<!-- F2 -->\n<g id=\"node12\" class=\"node\">\n<title>F2</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"243\" cy=\"-162\" rx=\"27\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"243\" y=\"-158.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">F2</text>\n</g>\n<!-- T1--F2 -->\n<g id=\"edge11\" class=\"edge\">\n<title>T1--F2</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M186.2693,-218.7307C198.488,-206.512 215.5398,-189.4602 227.7527,-177.2473\"/>\n</g>\n<!-- F1 -->\n<g id=\"node9\" class=\"node\">\n<title>F1</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"99\" cy=\"-90\" rx=\"27\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"99\" y=\"-86.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">F1</text>\n</g>\n<!-- T2--F1 -->\n<g id=\"edge8\" class=\"edge\">\n<title>T2--F1</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M99,-143.8314C99,-133 99,-119.2876 99,-108.4133\"/>\n</g>\n<!-- val2 -->\n<g id=\"node10\" class=\"node\">\n<title>val2</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"99\" cy=\"-18\" rx=\"27\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"99\" y=\"-14.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">val2</text>\n</g>\n<!-- F1--val2 -->\n<g id=\"edge9\" class=\"edge\">\n<title>F1--val2</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M99,-71.8314C99,-61 99,-47.2876 99,-36.4133\"/>\n</g>\n<!-- val3 -->\n<g id=\"node13\" class=\"node\">\n<title>val3</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"243\" cy=\"-90\" rx=\"27\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"243\" y=\"-86.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">val3</text>\n</g>\n<!-- F2--val3 -->\n<g id=\"edge12\" class=\"edge\">\n<title>F2--val3</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M243,-143.8314C243,-133 243,-119.2876 243,-108.4133\"/>\n</g>\n</g>\n</svg>\n" | |
| }, | |
| "metadata": { | |
| "tags": [] | |
| }, | |
| "execution_count": 4 | |
| } | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "metadata": { | |
| "id": "_rb1VVzBCAiE", | |
| "colab_type": "code", | |
| "colab": { | |
| "base_uri": "https://localhost:8080/", | |
| "height": 34 | |
| }, | |
| "outputId": "63a49284-6c30-473c-8c3a-07d34687fdc2" | |
| }, | |
| "source": [ | |
| "postfix = []\n", | |
| "i = 0\n", | |
| "for element in traversal:\n", | |
| " if type(element) == str and element.startswith('val'):\n", | |
| " num = numbers[i]\n", | |
| " i += 1\n", | |
| " elif type(element) == int:\n", | |
| " postfix.append(subs[element].format(num))\n", | |
| "post_exp = \"\".join(postfix)\n", | |
| "print(\"Postfix Expression is: \",post_exp)" | |
| ], | |
| "execution_count": 5, | |
| "outputs": [ | |
| { | |
| "output_type": "stream", | |
| "text": [ | |
| "Postfix Expression is: 496*+\n" | |
| ], | |
| "name": "stdout" | |
| } | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "metadata": { | |
| "id": "7ZyHEA_uCRNz", | |
| "colab_type": "code", | |
| "colab": { | |
| "base_uri": "https://localhost:8080/", | |
| "height": 153 | |
| }, | |
| "outputId": "b80d7300-e335-49c7-c1eb-6e418909d34a" | |
| }, | |
| "source": [ | |
| "stack = []\n", | |
| "top, j = -1, 0\n", | |
| "exp = list(post_exp) #Reduction of SDT into AST.\n", | |
| "for i in exp:\n", | |
| " if i != '*' and i != '+':\n", | |
| " stack.append(i)\n", | |
| " top += 1\n", | |
| " print(f'{i} was pushed into the stack.')\n", | |
| " else:\n", | |
| " val1 = stack.pop()\n", | |
| " val2 = stack.pop()\n", | |
| " print(f'{val1} and {val2} were popped from the stack.')\n", | |
| " intermediate = str(eval(val1+i+val2))\n", | |
| " stack.append(intermediate)\n", | |
| " top -= 1\n", | |
| " print(f'{intermediate} was pushed to the stack.')\n", | |
| "\n", | |
| "print(\"Result: \", stack[top])" | |
| ], | |
| "execution_count": 6, | |
| "outputs": [ | |
| { | |
| "output_type": "stream", | |
| "text": [ | |
| "4 was pushed into the stack.\n", | |
| "9 was pushed into the stack.\n", | |
| "6 was pushed into the stack.\n", | |
| "6 and 9 were popped from the stack.\n", | |
| "54 was pushed to the stack.\n", | |
| "54 and 4 were popped from the stack.\n", | |
| "58 was pushed to the stack.\n", | |
| "Result: 58\n" | |
| ], | |
| "name": "stdout" | |
| } | |
| ] | |
| } | |
| ] | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment