Python solution with detailed explanation


  • 0
    G

    Solution

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

    Algorithm

    1. Examples to run: 14-3/2
    2. 1-3/2+1
    3. Processing is left to right.
    4. if character is digit, scan the next number as num.
    5. if character is * or /, then pop the stack and scan the next number and complete the operation and push to stack.
    6. if character is -, then set sign to negative. Then the next scanned number will be negative and pushed on stack. Note we cannot prefetch next number here since 1-5/2 means 5/2 needs to be computed prior.
    7. Note the special treatment for division here. Python's division with negative numbers can be weird and hence we do the dance above.
    class Solution(object):
        def extract_num(self, expr, i):
            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, expr):
            """
            :type s: str
            :rtype: int
            """
            i, st = 0, []
            negative_sign = False
            operations = {
                            "+": lambda x,y:x+y,
                            "-": lambda x,y:x-y,
                            "/": lambda x,y: int(x/(float(y))),
                            "*": lambda x,y:x*y
                         }
            while i < len(expr):
                x = expr[i]
                if x == "/" or x == "*":
                    op1 = st.pop()
                    op2, i = self.extract_num(expr, i+1)
                    st.append(operations[x](op1, op2))
                elif x == "+" or x == "-":
                    if x == "-":
                        negative_sign = True
                    i = i+1
                elif x.isspace():
                    i = i+1
                else:
                    op, i = self.extract_num(expr, i)
                    if negative_sign:
                        op = op*-1
                        negative_sign = False
                    st.append(op)
            return sum(st)
    

Log in to reply
 

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