{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "provenance": [],
      "authorship_tag": "ABX9TyMKvR+DF9qlkhkkPrzv+zEK",
      "include_colab_link": true
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "view-in-github",
        "colab_type": "text"
      },
      "source": [
        "<a href=\"https://colab.research.google.com/github/Tanu-N-Prabhu/Python/blob/master/Python%20Coding%20Interview%20Prep/Basic_calculator.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "# Basic Calculator\n",
        "\n",
        "## Problem\n",
        "\n",
        "Given a string s representing a valid expression, implement a basic calculator to evaluate it, and return the result of the evaluation.\n",
        "\n",
        "> Note: You are not allowed to use any built-in function which evaluates strings as mathematical expressions, such as eval().\n",
        "\n",
        "```\n",
        "Example 1\n",
        "Input: s = \"1 + 1\"\n",
        "Output: 2\n",
        "\n",
        "Example 2\n",
        "Input: s = \"2-1 + 2\"\n",
        "Output: 3\n",
        "\n",
        "Example 3\n",
        "Input: s = \"(1+(4+5+2)-3)+(6+8)\"\n",
        "Output: 23\n",
        "\n",
        "Constraints\n",
        "1 <= s.length <= 3 * 105\n",
        "s consists of digits, '+', '-', '(', ')', and ' '.\n",
        "s represents a valid expression.\n",
        "'+' is not used as a unary operation (i.e., \"+1\" and \"+(2 + 3)\" is invalid).\n",
        "'-' could be used as a unary operation (i.e., \"-1\" and \"-(2 + 3)\" is valid).\n",
        "\n",
        "There will be no two consecutive operators in the input.\n",
        "Every number and running calculation will fit in a signed 32-bit integer.\n"
      ],
      "metadata": {
        "id": "YpjYRBtSkCUr"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "## Solution"
      ],
      "metadata": {
        "id": "7P0B3DxAlDNW"
      }
    },
    {
      "cell_type": "code",
      "execution_count": 1,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "hXwpq4W-jVXC",
        "outputId": "5190701d-9b85-49b2-9326-09ca5650df91"
      },
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "23\n"
          ]
        }
      ],
      "source": [
        "class Solution:\n",
        "    def calculate(self, s: str) -> int:\n",
        "        stack = []\n",
        "        num = 0\n",
        "        sign = 1\n",
        "        result = 0\n",
        "\n",
        "        for char in s:\n",
        "            if char.isdigit():\n",
        "                num = num * 10 + int(char)\n",
        "            elif char == \"+\":\n",
        "                result += sign * num\n",
        "                num = 0\n",
        "                sign = 1\n",
        "            elif char == \"-\":\n",
        "                result += sign * num\n",
        "                num = 0\n",
        "                sign = -1\n",
        "            elif char == \"(\":\n",
        "                stack.append(result)\n",
        "                stack.append(sign)\n",
        "                result = 0\n",
        "                sign = 1\n",
        "            elif char == \")\":\n",
        "                result += sign * num\n",
        "                num = 0\n",
        "                result *= stack.pop()  # Pop the sign.\n",
        "                result += stack.pop()  # Pop the preceding result.\n",
        "\n",
        "        result += sign * num\n",
        "        return result\n",
        "\n",
        "\n",
        "# Example usage:\n",
        "solution = Solution()\n",
        "s = \"(1+(4+5+2)-3)+(6+8)\"\n",
        "result = solution.calculate(s)\n",
        "print(result)  # Output: 23"
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "## Credits\n",
        "\n",
        "I would like to thank [Dhirajpatra](https://github.com/dhirajpatra) for writing this piece of code. Feel free to reach him out if you have any questions about Python Programming.\n"
      ],
      "metadata": {
        "id": "xF26di99lOJd"
      }
    }
  ]
}