{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Ex Notazione Polacca\n",
    "Scrivere una funzione che valuta un'espressione scritta con la notazione polacca \n",
    "https://it.wikipedia.org/wiki/Notazione_polacca\n",
    "\n",
    "Consideriamo solo operazioni binarie: +,−,∗,/\n",
    "e solo valori interi"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Scannerizzare l’espressione da destra a sinistra\n",
    "\n",
    "per ogni simbolo:\n",
    "\n",
    "\tse il simbolo è un operando allora mettilo in una pila\n",
    "    \n",
    "\tse è un operatore op allora:\n",
    "    \n",
    "\t\ttogli il primo elemento dalla pila e salvalo in x\n",
    "        \n",
    "\t\ttogli il primo elemento dalla pila e salvalo in y\n",
    "        \n",
    "            spingi il risultato  x op y nella pila \n",
    "            \n",
    "ritorna la testa della pila come risultato"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Hint:\n",
    "\n",
    "Creare una funzione isoperator(elem) che valuta se elem è un operatore op = +,-,\\,*. Creare una funzione comp(op,x,y) che dato un operatore op e due numeri x, y mi ritorna il risultato dell'operazione z = x op y . Creare una funzione polf(s) che scansione da destra gli elementi di s, se sono operandi li aggiunge ad una pila se sono operatori (lo valuta usando la funz isoperator(elem) ) rimuove dalla pila gli ultimi due elementi x,y e aggiunge alla pila il risultato di comp(op,x,y)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Metodo per implementare un algoritmo\n",
    "\n",
    "- identificare nell'algoritmo la azioni di base da eseguire\n",
    "- per ogni azione fornire un'implementazione e testarla con l'interprete python\n",
    "- fare una funzione e testarla\n",
    "- combinare le varie implementazioni\n",
    "- testare la funzione nell'interprete di python"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Soluzione Esercizio notazione polacca\n",
    "\n",
    "###### Algoritmo:\n",
    "\n",
    "- Scannerizzare l’espressione da destra a sinistra\n",
    "\n",
    "- per ogni simbolo:\n",
    "\n",
    "\t- se il simbolo è un operando allora mettilo in una pila\n",
    "    \n",
    "\t- se è un operatore op allora:\n",
    "    \n",
    "\t\t- togli il primo elemento dalla pila e salvalo in x\n",
    "        \n",
    "\t\t- togli il primo elemento dalla pila e salvalo in y\n",
    "        \n",
    "        - spingi il risultato  x op y nella pila \n",
    "            \n",
    "- ritorna la testa della pila come risultato\n",
    "\n",
    "\n",
    "###### Task:\n",
    "\n",
    "-1- scannerizzare l'espressione da destra a sinistra\n",
    "\n",
    "-2- verificare se il simbolo è un operatore od un operando\n",
    "\n",
    "-3- implementare le operazione di append e push e pop in python\n",
    "\n",
    "-4- dato un operatore, eseguire l'operazione associata"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['-', '*', '/', '15', '-', '7', '+', '1', '1', '3', '+', '2', '+', '1', '1']"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "expr = '- * / 15 - 7 + 1 1 3 + 2 + 1 1'\n",
    "l_expr=expr.split()\n",
    "l_expr"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**1** - scannerizzare l'espressione da destra a sinistra"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "1\n",
      "+\n",
      "2\n",
      "+\n",
      "3\n",
      "1\n",
      "1\n",
      "+\n",
      "7\n",
      "-\n",
      "15\n",
      "/\n",
      "*\n",
      "-\n"
     ]
    }
   ],
   "source": [
    "for i in range(1,len(l_expr)+1):\n",
    "    print(l_expr[len(l_expr)-i])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "1\n",
      "+\n",
      "2\n",
      "+\n",
      "3\n",
      "1\n",
      "1\n",
      "+\n",
      "7\n",
      "-\n",
      "15\n",
      "/\n",
      "*\n",
      "-\n"
     ]
    }
   ],
   "source": [
    "for i in range(len(l_expr)-1,-1,-1):\n",
    "    print(l_expr[i])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['-', '*', '/', '15', '-', '7', '+', '1', '1', '3', '+', '2', '+', '1', '1']"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "l_expr.reverse()\n",
    "l_expr"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**2** - verificare se il simbolo è un operatore od un operando"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "def isAnOperator( x ):                                 # ritorna True se x è ’+’,’−’,’∗’,’/’”””\n",
    "    return (x=='+') or (x=='-') or (x=='*') or (x=='/')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "isAnOperator( '9' )"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**3** - implementare le operazione di append e push e pop in python"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['-', '*', '/', '15', '-', '7', '+', '1', '1', '3', '+', '2', '+', '1', '1']"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "l_expr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "('15', '7')"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "l_expr[3],l_expr[5]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[15, 7]"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "pila = []\n",
    "pila.append(int(l_expr[3]))\n",
    "pila.append(int(l_expr[5]))\n",
    "pila"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(7, 15)"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "x = pila.pop()\n",
    "y = pila.pop()\n",
    "x,y"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**4** - dato un operatore, eseguire l'operazione associata"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [],
   "source": [
    "# calcola il valore dell'espressione ’x op y’, \n",
    "#dove x e y sono due interi e op è un operatore tra ’+’,’−’,’∗’,’/’””” \n",
    "def compute( op , x , y ):\n",
    "    if (op=='+'):\n",
    "        return x+y \n",
    "    elif op=='-':\n",
    "        return x-y \n",
    "    elif op=='*':\n",
    "        return x*y \n",
    "    elif op=='/':\n",
    "        return x/y \n",
    "    else:\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2.0"
      ]
     },
     "execution_count": 23,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "compute('/',12,6)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "[1]\n",
      "1\n",
      "[1, 1]\n",
      "+\n",
      "[2]\n",
      "2\n",
      "[2, 2]\n",
      "+\n",
      "[4]\n",
      "3\n",
      "[4, 3]\n",
      "1\n",
      "[4, 3, 1]\n",
      "1\n",
      "[4, 3, 1, 1]\n",
      "+\n",
      "[4, 3, 2]\n",
      "7\n",
      "[4, 3, 2, 7]\n",
      "-\n",
      "[4, 3, 5]\n",
      "15\n",
      "[4, 3, 5, 15]\n",
      "/\n",
      "[4, 3, 3.0]\n",
      "*\n",
      "[4, 9.0]\n",
      "-\n",
      "[5.0]\n",
      "[5.0]\n"
     ]
    }
   ],
   "source": [
    "expr = '- * / 15 - 7 + 1 1 3 + 2 + 1 1'\n",
    "l_expr=expr.split()\n",
    "\n",
    "pila = []\n",
    "for i in range(len(l_expr)-1,-1,-1):\n",
    "    print(l_expr[i])\n",
    "    if isAnOperator( l_expr[i] ):\n",
    "        pila.append( compute( l_expr[i] , pila.pop() , pila.pop() ) )\n",
    "    else:\n",
    "        pila.append( int(l_expr[i]) )\n",
    "    print(pila)\n",
    "print(pila)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [],
   "source": [
    "def isAnOperator( x ):                                 \n",
    "    return (x=='+') or (x=='-') or (x=='*') or (x=='/')\n",
    "\n",
    "def compute( op , x , y ):\n",
    "    if (op=='+'):\n",
    "        return x+y \n",
    "    elif op=='-':\n",
    "        return x-y \n",
    "    elif op=='*':\n",
    "        return x*y \n",
    "    elif op=='/':\n",
    "        return x/y \n",
    "    else:\n",
    "        return 0\n",
    "\n",
    "def evalPolishExpression( expr ):\n",
    "    e=expr.split()\n",
    "    pila = []\n",
    "    for i in range(len(e)-1,-1,-1):\n",
    "        if isAnOperator( e[i] ):\n",
    "            pila.append( compute( e[i] , pila.pop() , pila.pop() ) )\n",
    "        else:\n",
    "            pila.append( int(e[i]) )\n",
    "    return(pila.pop())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "5.0"
      ]
     },
     "execution_count": 27,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "evalPolishExpression( '- * / 15 - 7 + 1 1 3 + 2 + 1 1' )"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}