algorithms/241-different-ways-to-add-parentheses.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "normal-ordinary",
   "metadata": {},
   "source": [
    "### [为运算表达式设计优先级](https://leetcode-cn.com/problems/different-ways-to-add-parentheses/)\n",
    "\n",
    "给定一个含有数字和运算符的字符串，为表达式添加括号，改变其运算优先级以求出不同的结果。你需要给出所有可能的组合的结果。有效的运算符号包含`+`,`-`以及`*`。\n",
    "\n",
    "#### 示例 1:\n",
    "```\n",
    "输入: \"2-1-1\"\n",
    "输出: [0, 2]\n",
    "解释: \n",
    "((2-1)-1) = 0 \n",
    "(2-(1-1)) = 2\n",
    "```\n",
    "\n",
    "#### 示例 2:\n",
    "```\n",
    "输入: \"2*3-4*5\"\n",
    "输出: [-34, -14, -10, -10, 10]\n",
    "解释: \n",
    "(2*(3-(4*5))) = -34 \n",
    "((2*3)-(4*5)) = -14 \n",
    "((2*(3-4))*5) = -10 \n",
    "(2*((3-4)*5)) = -10 \n",
    "(((2*3)-4)*5) = 10\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "id": "sustainable-water",
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List   \n",
    "from operator import add, sub, mul\n",
    "\n",
    "operators = {'+': add, '-': sub, '*': mul}\n",
    "class Solution:\n",
    "    def diffWaysToCompute(self, expr: str) -> List[int]:\n",
    "        if expr.isdigit():\n",
    "            return [int(expr)]\n",
    "        ans = []\n",
    "        for i, c in enumerate(expr):\n",
    "            if c in operators:\n",
    "                left = self.diffWaysToCompute(expr[0:i])\n",
    "                right = self.diffWaysToCompute(expr[i+1:])\n",
    "                for l in left:\n",
    "                    for r in right:\n",
    "                        ans.append(operators[c](l, r))\n",
    "        return ans\n",
    "solution = Solution()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "id": "radio-experience",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[6]"
      ]
     },
     "execution_count": 24,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "solution.diffWaysToCompute(\"2*3\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "id": "grateful-grass",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[2, 0]"
      ]
     },
     "execution_count": 25,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "solution.diffWaysToCompute(\"2-1-1\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "id": "outdoor-engineering",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[-34, -10, -14, -10, 10]"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "solution.diffWaysToCompute(\"2*3-4*5\")"
   ]
  }
 ],
 "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.8.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}