{ "nbformat": 4, "nbformat_minor": 0, "metadata": { "colab": { "name": "HW 7", "provenance": [], "collapsed_sections": [] }, "kernelspec": { "display_name": "Python 3", "language": "python", "name":...

{
"cells": [
{
"cell_type": "markdown",
"metadata": {
"id": "ZCixiV44_qj9"
},
"source": [
"Before you turn this problem in, make sure everything runs as expected. First, **restart the kernel** (in the menubar, select Kernel$\\rightarrow$Restart) and then **run all cells** (in the menubar, select Cell$\\rightarrow$Run All).\n",
"\n",
"Make sure you fill in any place that says `YOUR CODE HERE` or \"YOUR ANSWER HERE\", as well as your name and collaborators below:"
]
},
{
"cell_type": "code",
"execution_count": 1,
"metadata": {
"id": "-U2UDMpr_qj-"
},
"outputs": [],
"source": [
"NAME = \"\"\n",
"COLLABORATORS = \"\""
]
},
{
"cell_type": "markdown",
"metadata": {
"id": "XXAOw2IQ_qkC"
},
"source": [
"---"
]
},
{
"cell_type": "markdown",
"metadata": {
"deletable": false,
"editable": false,
"id": "IjCmJxfx_qkD",
"nbgrader": {
"checksum": "25175b5354bbbd7cfa83290fd26cb55c",
"grade": false,
"grade_id": "cell-b4ddb837b6cd125d",
"locked": true,
"schema_version": 1,
"solution": false
}
},
"source": [
"# Homework 7: Expression Trees\n",
"\n",
"Copyright Luca de Alfaro, 2019-20. \n",
"License: [CC-BY-NC-ND](https://creativecommons.org/licenses/by-nc-nd/4.0/)."
]
},
{
"cell_type": "markdown",
"metadata": {
"deletable": false,
"editable": false,
"id": "sssH1epV_qkD",
"nbgrader": {
"checksum": "6d34e41c32a8683030f7d98e30bcc019",
"grade": false,
"grade_id": "cell-deabe6385dbf079d",
"locked": true,
"schema_version": 1,
"solution": false
}
},
"source": [
"## Submission\n",
"\n",
"[Please submit to this Google Form](https://docs.google.com/forms/d/e/1FAIpQLSceVO96w9k1LOJ1hPFCeCT9mSaBtjwA8Ds0IQMHEmvrcn4dKg/viewform?usp=sf_link).\n",
"\n",
"Deadline: Friday November 6, 11pm (check on Canvas for updated information)."
]
},
{
"cell_type": "markdown",
"metadata": {
"id": "HaLBPyml_qkE"
},
"source": [
"## The assignment\n",
"\n",
"There are three questions in this assignment, each labeled `Question n:`, and each followed by one or more test cells:\n",
"\n",
"* A question on printing out expressions in LaTeX, \n",
"* A question on derivatives,\n",
"* A question on checking expression equality."
]
},
{
"cell_type": "markdown",
"metadata": {
"deletable": false,
"editable": false,
"id": "UQrAnhcU_qkE",
"nbgrader": {
"checksum": "f34d3d7cd714483ea63dd4ecd99d6b1a",
"grade": false,
"grade_id": "cell-1eef897c16ae7c5c",
"locked": true,
"schema_version": 1,
"solution": false
}
},
"source": [
"We will develop a data structure to represent arithmetic expressions containing variables, such as $3 + 4$ or $2 + x * (1 - y)$. \n",
"\n",
"What is an expression? An expression consists of one of these: \n",
"\n",
"\n",
"1. A number\n",
"2. A variable\n",
"3. If $e_1$ and $e_2$ are expressions, then $e_1 + e_2$, $e_1 - e_2$, $e_1 * e_2$, and $e_1 / e_2$ are also expressions. \n",
"\n",
"Formally, the set of expressions is the _least_ set constructed according to the rules above. \n",
"\n",
"Thus, an expression can be either a constant, representing numbers and variables, or a composite expression, consisting of an operator, a left expression, and a right expression. \n"
]
},
{
"cell_type": "markdown",
"metadata": {
"deletable": false,
"editable": false,
"id": "PSFpZHID_qkF",
"nbgrader": {
"checksum": "4f03ae847ff88ef66263b98715a6ea48",
"grade": false,
"grade_id": "cell-367a6ba7ae8ce08",
"locked": true,
"schema_version": 1,
"solution": false
}
},
"source": [
"There are (at least) two ways of representing expressions. The simplest way is to represent expressions as trees, and define operations on them. \n",
"The more sophisticated way consists in representing expressions via classes: there will be one class for variable and constants, and one class representing composite expressions; both of these classes will be subclasses of a generic \"expression\" class. \n",
"\n",
"In this chapter, we will represent expression as trees, to gain experience with writing recursive functions on trees; in the next chapter, we will show how to represent them more elegantly as classes."
]
},
{
"cell_type": "markdown",
"metadata": {
"deletable": false,
"editable": false,
"id": "lAgp_ohc_qkG",
"nbgrader": {
"checksum": "97744fff2401606b8a3764cbcb14370a",
"grade": false,
"grade_id": "cell-4f9963e65bfa7f24",
"locked": true,
"schema_version": 1,
"solution": false
}
},
"source": [
"We will represent expressions as trees. A number will be represented via a number; a variable via a string, and the expression $e_1 \\odot e_2$ via the tuple $(\\odot, e_1, e_2)$, for $\\odot \\in \\{+, -, *, / \\}$.\n",
"\n",
"For example, we will represent $2 * (x + 1)$ via:\n",
"\n",
" ('*', 2, ('+', 'x', 1))"
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {
"deletable": false,
"editable": false,
"id": "d0RF--5t_qkG",
"nbgrader": {
"checksum": "ff9dd21c9b5cebc05a51dddf8f0c3372",
"grade": false,
"grade_id": "cell-b2d84e2d75b1834b",
"locked": true,
"schema_version": 1,
"solution": false
}
},
"outputs": [],
"source": [
"e = ('*', 2, ('+', 'x', 1))\n"
]
},
{
"cell_type": "markdown",
"metadata": {
"deletable": false,
"editable": false,
"id": "4cuZlVnm_qkJ",
"nbgrader": {
"checksum": "90f23d4be6fd84cbf132b2497f87f84f",
"grade": false,
"grade_id": "cell-0ef73bcc5b3c9143",
"locked": true,
"schema_version": 1,
"solution": false
}
},
"source": [
"Let us define a check function, in preparation for our first question."
]
},
{
"cell_type": "code",
"execution_count": 3,
"metadata": {
"deletable": false,
"editable": false,
"id": "7P6yw6l-_qkK",
"nbgrader": {
"checksum": "3a4da5274c6f62d706e62940d7ccf319",
"grade": false,
"grade_id": "cell-cb08bfd0538a01cb",
"locked": true,
"schema_version": 1,
"solution": false
}
},
"outputs": [],
"source": [
"def check_equal(x, y, msg=None):\n",
" if x != y:\n",
" if msg is None:\n",
" print(\"Error:\")\n",
" else:\n",
" print(\"Error in\", msg, \":\")\n",
" print(\" Your answer was:\", x)\n",
" print(\" Correct answer: \", y)\n",
" assert x == y, \"%r and %r are different\" % (x, y)\n",
" print(\"Success\")"
]
},
{
"cell_type": "markdown",
"metadata": {
"deletable": false,
"editable": false,
"id": "wuolZ1Vu_qkN",
"nbgrader": {
"checksum": "b8c5993f5da061acf7ba9254fe05cc41",
"grade": false,
"grade_id": "cell-4aaaa507299e3412",
"locked": true,
"schema_version": 1,
"solution": false
}
},
"source": [
"## Question 1: Printing an expression in LaTeX format\n",
"\n",
"Our first question asks you to write a function `expr_to_latex` so that, for an expression `e`, `expr_to_latex(e)` will produce a string which is the LaTeX representation of the expression `e`. \n",
"This sounds complicated, but the rules are simple: \n",
"\n",
"* Numbers and variable names are simply converted to strings (you can use str()). \n",
"* If e = (op, e1, e2), then you compute the strings s1 and s2 representing e1 and e2 via a recursive call.\n",
"* If op is one of `\"+\"`, `\"-\"`, `\"*\"`, you proceed as follows: \n",
" \n",
" * Enclose s1 in parentheses if: \n",
" \n",
" e1 is not a leaf, and its operator is not `\"/\"`\n",
" \n",
" To enclose s1 in parentheses, do: `s1 = \"(\" + s1 + \")\"`;\n",
" * Same for e2;\n",
" * Finally, you output s1 + op + s2, where op is one of `+`, `-`, `*`. \n",
"* If you have e1 / e2, you output `\\frac{s1}{s2}`.\n",
"\n",
"To test whether parentheses are needed, for an expression e1, you can use this code: \n",
"\n",
" if isinstance(e1, tuple) and e1[0] != '/':\n",
"\n",
"Some examples will help: \n",
"\n",
"If the expression is\n",
"\n",
" (\"+\", 3, \"x\")\n",
" \n",
"the latex output is simply `\"3+x\"`. If the expression is \n",
"\n",
" (\"+\", 3, (\"*\", 2, \"x\"))\n",
"\n",
"you should output \n",
"\n",
" \"3+(2*x)\"\n",
" \n",
"where the parentheses have been added because the expression `(\"*\", 2, \"x\")` is not a leaf. \n",
"If the expression is \n",
"\n",
" (\"/\", (\"+\", 3, (\"*\", 2, \"x\")), (\"+\", 1, \"x\"))\n",
" \n",
"you should output: \n",
"\n",
" \\frac{3+(2*x)}{1+x}\n",
" "
]
},
{
"cell_type": "markdown",
"metadata": {
"id": "0Bg9DSxG_qkN"
},
"source": [
"One word of caution about Python strings. To include a `\\` in a string, you have to quote it, as in `\"\\\\\"`. \n",
"So to generate the string `\\frac`, you have to actually write `\"\\\\frac\"` in your code. "
]
},
{
"cell_type": "code",
"execution_count": 4,
"metadata": {
"deletable": false,
"id": "6Y8lrjfH_qkO",
"nbgrader": {
"checksum": "94517672f088a185c064b0b22df0f450",
"grade": false,
"grade_id": "cell-3fc0f1961983e06f",
"locked": false,
"schema_version": 1,
"solution": true
}
},
"outputs": [],
"source": [
"### Question 1: define expr_to_latex\n",
"\n",
"def expr_to_latex(e):\n",
" # YOUR CODE HERE\n",
" if(not isinstance(e,tuple)):\n",
" return str(e)\n",
" else:\n",
" op=e[0]\n",
" e1=e[1]\n",
" e2=e[2]\n",
" \n",
" s1=expr_to_latex(e1)\n",
" s2=expr_to_latex(e2)\n",
" \n",
" if(op==\"/\"):\n",
" return \"\\\\frac{\"+s1+\"}{\"+s2+\"}\"\n",
" else:\n",
" if(isinstance(e1,tuple) and s1[0]!='\\\\'):\n",
" s1=\"(\"+s1+\")\"\n",
" \n",
" if(isinstance(e2,tuple) and s2[0]!='\\\\'):\n",
" s2=\"(\"+s2+\")\"\n",
" \n",
" return s1+op+s2\n",
" "
]
},
{
"cell_type": "code",
"execution_count": 5,
"metadata": {
"colab": {
"base_uri": "https://localhost:8080/"
},
"deletable": false,
"editable": false,
"id": "4ydYx__1_qkR",
"nbgrader": {
"checksum": "42d641399cbca3dabc52107784e7ac2b",
"grade": true,
"grade_id": "cell-7ab5a60722b73c1f",
"locked": true,
"points": 5,
"schema_version": 1,
"solution": false
},
"outputId": "ca90890f-687d-4599-ef5b-468ca23ec2d1"
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Success\n",
"Success\n"
]
}
],
"source": [
"### Question 1, part 1: 5 points: tests for leaves. \n",
"\n",
"check_equal(expr_to_latex(3), \"3\")\n",
"check_equal(expr_to_latex(\"x\"), \"x\")\n"
]
},
{
"cell_type": "code",
"execution_count": 6,
"metadata": {
"colab": {
"base_uri": "https://localhost:8080/"
},
"deletable": false,
"editable": false,
"id": "hUf-RFTG_qkV",
"nbgrader": {
"checksum": "e18f519d05031591a39114157c7053c4",
"grade": true,
"grade_id": "cell-5ff30fed1e5a2476",
"locked": true,
"points": 5,
"schema_version": 1,
"solution": false
},
"outputId": "ac37157d-35c8-4bc1-daa5-9fe6074cbb51"
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Success\n",
"Success\n",
"Success\n",
"Success\n"
]
}
],
"source": [
"### Question 1, part 2: 5 points: simple expressions. \n",
"e = (\"+\", 3, \"x\")\n",
"check_equal(expr_to_latex(e), \"3+x\")\n",
"e = (\"-\", \"y\", \"x\")\n",
"check_equal(expr_to_latex(e), \"y-x\")\n",
"e = (\"*\", \"y\", \"2\")\n",
"check_equal(expr_to_latex(e), \"y*2\")\n",
"e = (\"/\", \"y\", \"2\")\n",
"check_equal(expr_to_latex(e), \"\\\\frac{y}{2}\")\n"
]
},
{
"cell_type": "code",
"execution_count": 7,
"metadata": {
"colab": {
"base_uri": "https://localhost:8080/"
},
"deletable": false,
"editable": false,
"id": "akOGCX6q_qkY",
"nbgrader": {
"checksum": "84ffe941a1d0c8d7d11493dedcc7af04",
"grade": true,
"grade_id":...