Prefix_and_Postfix_Expressions_in_Data_Structure_Using_Stacks.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "Cpe211B-MamarungkasHanzel-Assign5.ipynb",
      "provenance": [],
      "collapsed_sections": [
        "5kzdORbSQJkv",
        "pwwysDkZi3cj",
        "OF1P8DxC_moi",
        "8qHKwa-j_3_d"
      ],
      "authorship_tag": "ABX9TyN6MXMTCDkRL6StWsKfVAV1",
      "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/MMRNGKS/Data-Structures-and-Algorithm-Analysis-Problem-Code-w-Solutions/blob/main/Cpe211B_MamarungkasHanzel_Assign5.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "5kzdORbSQJkv"
      },
      "source": [
        "# **1. Implement as a Python code the algorithm for parenthesis count (stack implementation) that accepts as input an arithmetic expression string having parentheses symbols: ( , ). The Python code will determine if the input arithmetic expression string is valid or invalid by checking if each left parenthesis '(' is paired with a right parenthesis ')'. Use only 1 stack.**"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "VP-yB_RDQ60q"
      },
      "source": [
        "This lines of codes will check the validity of the arithmetic expression that will be inputted by the user. It will  be valid if the quantity of both '(' and ')' are equal in the expression. If not then it is invalid.  "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "HurcYJUuQtN7",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "1d53a747-0f7b-444b-a08f-7c54f373c153"
      },
      "source": [
        "stack = []    # < Declaring a Stack or a list with a variable name \"stack\".\n",
        "\n",
        "inp = input('Enter Expression: ')   # < Ask the user to input an Arithmetic Expression in string.\n",
        "exp = iter(inp)                     # < This function will iterate the strings that the user inputted.\n",
        "b = True                            # < Declaring a boolean variable, necessary for the \"quantity of ')' is greater than '('\" cases.\n",
        "\n",
        "for i in range(len(inp)):   # < The condition of this for-loop is stop the loop if the value of \"i\" is greater than the value of length of the string \"inp\".\n",
        "    x = next(exp)           # < Using next() function to get the iterated string from \"exp\". It is inside the loop to get each characters from \"exp\".\n",
        "    if x == '(':            # < If \"x\" is equal to character '(' is equals to TRUE\n",
        "        stack.append(x)     # < If the first condition is TRUE, push the current character of \"x\" inside the stack.\n",
        "    elif x == ')':          # < If \"x\" is equal to character ')' is equals to TRUE\n",
        "        try:\n",
        "            stack.pop()     # < If the second condition is TRUE, pop the top element inside the stack.\n",
        "        except IndexError:  # ^ If this results to a run-time error or exception then stack s is empty, which means that P.C.< 0, there are more ‘)’ than ‘(’.\n",
        "            b = False       # < If an exception occured set \"b\" to False.\n",
        "\n",
        "if bool(stack):         # < Using boolean function to determine if the stack is empty or not. If not, the condition is TRUE. \n",
        "    print('INVALID')    # < If the first condition is TRUE, print \"INVALID\".\n",
        "elif b == False:        # < This condition will turn into TRUE if there's an exception occurred inside the elif condition inside the loop above.\n",
        "    print('INVALID')    # < If the second condition is TRUE, print \"INVALID\".\n",
        "else:\n",
        "    print('VALID')      # < Else, print \"VALID\"."
      ],
      "execution_count": 4,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "Enter Expression: (2+4)/(2-4)\n",
            "VALID\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "pwwysDkZi3cj"
      },
      "source": [
        "# **2. Implement as a Python code the algorithm to evaluate an input postfix expression with numeric operands. Output the numeric value. Use only 1 stack.**"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "Lzl5NBKkjMKL"
      },
      "source": [
        "This lines of codes will evaluate postfix expression using push and pop method to a stack."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Wcr33tU3jOO7",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "0ff30d43-bfb3-4759-93c1-4f3c3848910c"
      },
      "source": [
        "stack = []    # < Declaring a Stack or a list with a variable name \"stack\".\n",
        "\n",
        "inp = input('Enter Expression: ')   # < Ask the user to input an Postfix Expression in string.\n",
        "exp = iter(inp)                     # < This function will iterate the strings that the user inputted. \n",
        "\n",
        "for i in range(len(inp)):   # < The condition of this for-loop is stop the loop if the value of \"i\" is greater than the value of length of the string \"inp\".\n",
        "    x = next(exp)           # < Using next() function to get the iterated string from \"exp\". It is inside the loop to get each characters from \"exp\".\n",
        "\n",
        "    if not (x == '+' or  x == '-' or x == '*' or x == '/'):   # < If \"x\" is not equal to any math operators will pass this condition.\n",
        "        stack.append(x)                                       # < If the first condition is TRUE, push the current character of \"x\" inside the stack.\n",
        "    elif x == '+' or  x == '-' or x == '*' or x == '/':       # < If \"x\" is equal to any math operators will pass this condition.\n",
        "        ro = stack.pop()                                      # < If the second condition is TRUE, pop the top element inside the stack.\n",
        "        lo = stack.pop()                                      # < If the second condition is TRUE, pop the current top element inside the stack.\n",
        "        eva = lo + x + ro                                     # < Concat the 3 string variable \"lo\", \"x\", \"ro\".\n",
        "        result = eval(eval('eva'))                            # < It evaluates the string \"eva\" using evaluate function.\n",
        "        stack.append(str(int(result)))                        # < Pushes the result of the evaluation inside the stack.\n",
        "        \n",
        "print(stack)    # < Prints the elements inside the stack."
      ],
      "execution_count": 6,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "Enter Expression: 23+45+*\n",
            "['45']\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "OF1P8DxC_moi"
      },
      "source": [
        "# **3. Implement as a Python code the algorithm to determine if an input string L is a palindrome string or not. Please see attached the other file for the Palindrome problem.**"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "iyZXE2fOMJLF"
      },
      "source": [
        "This lines of codes will recognize if the inputted string by the users are a palindrome or not. The process of recognizing is through push and pop to the stack by comparing the left characters of the origin to the right characters of the origin while popping an element. "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "hLMS2y-CMK29",
        "outputId": "f599f0ce-abd8-48f0-a20c-add8849b087c"
      },
      "source": [
        "stack = []    # < Declaring a Stack or a list with a variable name \"stack\".  \n",
        "\n",
        "inp = input('Input String L: ')   # < Ask the user to input a string.\n",
        "center = round(len(inp) / 2.01)   # < This int will give the half value of the number of length of the string that the user inputted.\n",
        "pal = iter(inp)                   # < This function will iterate the strings that the user inputted.\n",
        "b = True                          # < Declaring a boolean with a variable name \"b\", if this boolean will stay 'True' at the end of the program, user input is a palindrome.\n",
        "\n",
        "if (len(inp) % 2) != 0:         # < If value of length of the inputted string is odd, the condition is TRUE.\n",
        "    for i in range(len(inp)):   # < The condition of this for-loop is stop the loop if the value of \"i\" is greater than the value of length of the string \"inp\".\n",
        "        x = next(pal)           # < Using next() function to get the iterated string from \"pal\". It is inside the loop to get each characters from \"pal\".\n",
        "        if i < int(center):     # < If \"i\" is less than the value of \"center\", the condition is TRUE.\n",
        "            stack.append(x)     # < If the first condition is TRUE, push \"x\" inside the stack.\n",
        "        elif i > int(center):   # < If i is greater than the value of the \"center\", the condition is TRUE.\n",
        "            t = stack.pop()     # < If the second condition is TRUE, pop the top element of the stack, then the value of \"t\" will be the popped top element from the stack.\n",
        "            if x == t:          # < If the seconf condition is TRUE and \"x\" is equals to \"t\", then the nested if condition is TRUE.\n",
        "                continue        # < If the nested if is TRUE, continue the loop.\n",
        "            else:               # < If the nested if is FALSE set \"b\" to False and print 'Output: Not a Palindrome String' and finish the loop.\n",
        "                b = False\n",
        "                print('Output: Not a Palindrome String')\n",
        "                break\n",
        "        else:                   # < If the conditions above are FALSE, continue the loop.\n",
        "            continue\n",
        "else:                           # < If the value of length of the inputted string is even, the condition is TRUE.\n",
        "    b = False                   # < If the user inputted even length if strings, set \"b\" to false.\n",
        "    print('Output: NO (Not a palindrome string)') # < If the user inputted even length if strings, print 'Output: NO (Not a palindrome string)'.\n",
        "\n",
        "if b == True:                   # < If \"b\" is still TRUE, print 'Output: YES (A palindrome string)'.\n",
        "    print('Output: YES (A palindrome string)')"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "Input String L: step on no pets\n",
            "Output: YES (A palindrome string)\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "8qHKwa-j_3_d"
      },
      "source": [
        "# **4. Implement as a Python code the algorithm to convert from Infix to Postfix. Input: Infix expression string whose operands are digits. Output: Equivalent postfix expression string.**"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "KM_YqETGbeSB"
      },
      "source": [
        "This lines of codes converts infix expression to postfix expression using push and pop method to a stack."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "F0wriC5GbfEF",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "dbbd97ee-68af-4cb9-f058-7defb2a4b9ed"
      },
      "source": [
        "stack = []    # < Declaring a Stack or a list with a variable name \"stack\".    \n",
        "\n",
        "ops = {'+', '-', '*', '/', '^', '(', ')'}   # < A set of math operator elements inside a set with variable name \"ops\".\n",
        "prio = {'+':1, '-':1, '*':2, '/':2, '^':3}  # < A dictionary with a variable name \"prio\" that helps to indicate priorities in our conditions.\n",
        "postf = ''                                  # < A place holder string with a variable name \"postf\".\n",
        "\n",
        "inp = input('Enter Infix Expression: ')   # < Ask the user to input an Infix Expression in string.   \n",
        "exp = iter(inp)                           # < This function will iterate the strings that the user inputted. \n",
        "\n",
        "for i in range(len(inp)):   # < The condition of this for-loop is stop the loop if the value of \"i\" is greater than the value of length of the string \"inp\".         \n",
        "    x = next(exp)           # < Using next() function to get the iterated string from \"exp\". It is inside the loop to get each characters from \"exp\".   \n",
        "    \n",
        "    if x not in ops:    # < If \"x\" is not in the set of \"ops\", then the condition is TRUE.   \n",
        "            postf+= x   # < Concats \"x\" to \"postf\"\n",
        "    elif x == '(':          # < If \"x\" is equal to '(', then the condition is TRUE.\n",
        "        stack.append(x)   # < Push \"x\" inside the stack.\n",
        "    elif x == ')':        # < If \"x\" is equal to ')', then the condition is TRUE.            \n",
        "        while stack and stack[-1]!= '(':    # < Repeats the process inside this loop if \"stack\" and \"stack[-1]\" is not equal to '('.\n",
        "            postf += stack.pop()              # < Pop the top element in the stack and concats the popped element to \"postf\".\n",
        "        stack.pop()   # < Pop the current top element in the stack.\n",
        "    else:            # < This condition is TRUE if all the top conditions are False.\n",
        "        while stack and stack[-1] != '(' and prio[x] <= prio[stack[-1]]:    # < Repeats the process inside this loop if \"stack\" and \"stack[-1]\" is not equal to '(' and \"prio[x]\" is less than or equal to \"prio[stack[-1]]\".\n",
        "            postf += stack.pop()    # < Pop the top element in the stack and concats the popped element to \"postf\".\n",
        "        stack.append(x)             # < Push \"x\" inside the stack.\n",
        "                \n",
        "while len(stack) > 0:        # This while-loop will concat the remaining elements inside the stack and concat it to \"postf\" one by one from top to bottom.\n",
        "    postf += stack.pop()\n",
        "\n",
        "print(postf)    # < Prints the converted Infix Expression."
      ],
      "execution_count": 7,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "Enter Infix Expression: A + B * C + D\n",
            "A  B  C *+ D+\n"
          ]
        }
      ]
    }
  ]
}