algorithms/224-basic-calculator.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "moved-reunion",
   "metadata": {},
   "source": [
    "### 基本计算器\n",
    "\n",
    "实现一个基本的计算器来计算一个简单的字符串表达式`s`的值。\n",
    "\n",
    "#### 示例 1：\n",
    "```\n",
    "输入：s = \"1 + 1\"\n",
    "输出：2\n",
    "```\n",
    "\n",
    "#### 示例 2：\n",
    "```\n",
    "输入：s = \" 2-1 + 2 \"\n",
    "输出：3\n",
    "```\n",
    "\n",
    "#### 示例 3：\n",
    "```\n",
    "输入：s = \"(1+(4+5+2)-3)+(6+8)\"\n",
    "输出：23\n",
    "```\n",
    "\n",
    "#### 提示：\n",
    "- 1 <= s.length <= 3 * 105\n",
    "- s 由数字、'+'、'-'、'('、')'、和 ' ' 组成\n",
    "- s 表示一个有效的表达式"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "utility-blocking",
   "metadata": {},
   "source": [
    "```ast\n",
    "expression : DIGIT_LITERAL | '(' expression ')' | DIGIT_LITERAL '+' expression |  term '-' expression\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 194,
   "id": "mounted-sherman",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['-2', '+', '1']\n",
      "['1', '+', '1']\n",
      "['2', '-', '1', '+', '2']\n",
      "['(', '1', '+', '(', '4', '+', '5', '+', '2', ')', '-', '3', ')', '+', '(', '6', '+', '8', ')']\n",
      "['216', '-', '18', '+', '(', '2', '-', '1', ')', '+', '100', '-', '50']\n"
     ]
    }
   ],
   "source": [
    "from typing import List\n",
    "\n",
    "def tokenize(s: str) -> List[str]:\n",
    "    tokens, i, start = [], 0, -1\n",
    "    sign = 1\n",
    "    for c in s:\n",
    "        if c.isdigit():\n",
    "            if start == -1:\n",
    "                start = i  \n",
    "        else:\n",
    "            if start > -1:\n",
    "                if sign == 1:\n",
    "                    tokens.append(s[start:i])\n",
    "                else:\n",
    "                    tokens.append('-' + s[start:i])\n",
    "                start = -1\n",
    "            if c == '+' or c == '(' or c == ')':\n",
    "                tokens.append(c)\n",
    "            elif c == '-':\n",
    "                if len(tokens) == 0 or tokens[-1] == '+' or tokens[-1] == '(':\n",
    "                    sign = -1\n",
    "                else:\n",
    "                    tokens.append(c)\n",
    "        i += 1\n",
    "    if start > -1:\n",
    "        tokens.append(s[start:i])\n",
    "    \n",
    "    return tokens\n",
    "\n",
    "print(tokenize(\"-2+ 1\"))\n",
    "print(tokenize(\"1 + 1\"))\n",
    "print(tokenize(\"2-1 + 2\"))\n",
    "print(tokenize(\"(1+(4+5+2)-3)+(6+8)\"))\n",
    "print(tokenize(\"216-18 + (2-1)+ 100-50\"))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 195,
   "id": "printable-dayton",
   "metadata": {},
   "outputs": [],
   "source": [
    "import operator\n",
    "\n",
    "operators = {'+': operator.add, '-': operator.sub}\n",
    "\n",
    "def parseRPN(tokens: List[str]):\n",
    "    stack, ret = [], []\n",
    "    inner = False\n",
    "    for i, t in enumerate(tokens):\n",
    "        if t.isdigit() or t[0] == '-' and t[1:].isdigit():\n",
    "            ret.append(t)                \n",
    "        elif t in operators:\n",
    "            if len(stack) == 0 or stack[-1] == '(':\n",
    "                stack.append(t)\n",
    "            else:\n",
    "                while len(stack) > 0 and stack[-1] != '(':\n",
    "                    ret.append(stack.pop())\n",
    "                if len(stack) == 0 or stack[-1] == '(':\n",
    "                    stack.append(t)\n",
    "        elif t == '(':\n",
    "            stack.append('(')\n",
    "        elif t == ')':\n",
    "            while len(stack) > 0:\n",
    "                op = stack.pop()\n",
    "                if op == '(':\n",
    "                    break\n",
    "                else:\n",
    "                    ret.append(op)\n",
    "            \n",
    "    while len(stack) > 0:\n",
    "        ret.append(stack.pop())\n",
    "    return ret\n",
    "\n",
    "def evaluateRPN(ast: List[str]) -> int:\n",
    "    op = ast.pop()\n",
    "    if op in operators:\n",
    "        right = evaluateRPN(ast)\n",
    "        left = evaluateRPN(ast)\n",
    "        return operators[op](left, right)\n",
    "    elif op.isdigit() or op[0] == '-' and op[1:].isdigit():\n",
    "        return int(op)\n",
    "    \n",
    "def calculate(s: str):\n",
    "    tokens = tokenize(s)\n",
    "    ast = parseRPN(tokens)\n",
    "    return evaluateRPN(ast)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 196,
   "id": "electrical-mercy",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 196,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "calculate(\"1 + 2\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 197,
   "id": "straight-mailman",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 197,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "calculate(\"2-1 + 2\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 198,
   "id": "simple-agency",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 198,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "calculate('5 - (3 - 1)')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 199,
   "id": "bigger-belarus",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "23"
      ]
     },
     "execution_count": 199,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "calculate(\"(1+(4+5+2)-3)+(6+8)\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 200,
   "id": "breeding-joseph",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "249"
      ]
     },
     "execution_count": 200,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "calculate(\"216-18 + (2-1)+ 100-50\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 201,
   "id": "independent-runner",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "-1"
      ]
     },
     "execution_count": 201,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "calculate(\"-2+ 1\")"
   ]
  }
 ],
 "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
}