Python solution with detailed explanation


  • 0
    G

    Solution

    Basic Calculator https://leetcode.com/problems/basic-calculator/

    Insights from this problem

    1. Three main examples to run your code:"2-(5-6)", "2-3-4", and "(2)-(7)-(5)".
    2. Reduce to only "+" operation. You can convert "-" to "+" for the case when there is a number after "-", make that number negative. If there is a bracket after "-" then store the sign somehow.
    3. Keep two stacks - one for operands and other for operators. In the operator stack, you also push "(" and ")". When you hit ")", unwind the stack and evaluate the inner-most expression.
    4. Take a note at get_number method as well.
    5. Issues come with handling the negative sign. To handle it, maintain a sign variable.
      • When you see "-" sign, append "+" and set sign to -1.
      • When you see a number after "-" sign, that number gets multiplied by -1.
      • When you see a "(", push the sign on the stack as well. When you will unwind the stack to compute the inner-most expression, multiply with the sign you pushed for that expression. Example: "2-(5-6)", after "-", you will see "(" and push "-". Now at ")", you will compute 5+"-6" = -1. You will multiply it with -1 at stack unwind.
      • Google the video on infix to postfix expression as well.
    class Solution(object):
        def get_number(self, i, expr):
            num = 0
            while i < len(expr) and (expr[i].isdigit() or expr[i].isspace()):
                if expr[i].isdigit():
                    num = num*10 + int(expr[i])
                i = i+1
            return num,i
            
        def calculate(self, s):
            """
            :type s: str
            :rtype: int
            """
            st_operator, st_operand, i, sign = [], [], 0, 1
            expr = "".join(["(", s, ")"])
    
            while i < len(expr):
                x = expr[i]
                if x.isspace():
                    i=i+1
                elif x.isdigit():
                    num, i = self.get_number(i, expr)
                    num, sign = num*sign, 1
                    st_operand.append(num)
                elif x in ("+", "-"):
                    sign = -1 if x == "-" else 1
                    st_operator.append("+")
                    i = i+1
                elif x == "(":
                    # This is a delimiter for inner expression.
                    # Store the sign to multiply with value of inner expression.
                    st_operator.append((x, sign))
                    # Reset the sign
                    i, sign = i+1, 1
                elif x == ")":
                    while True:
                        y = st_operator.pop()
                        if len(y) == 2 and y[0] == "(":
                            st_operand[-1] = st_operand[-1]*y[1]  ### MULTIPLY WITH THE SIGN SO FAR.
                            sign = 1
                            break
                        else:               
                            st_operand.append(st_operand.pop()+st_operand.pop()) ### Can be only + sign now
                    i =i+1
            if len(st_operand) == 0:
                return 0
            return st_operand[-1]
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.