Leetcode 227 Basic Calculator II

Problem description

Leetcode 206

Given a string s which represents an expression, evaluate this expression and return its value.

The integer division should truncate toward zero.

You may assume that the given expression is always valid. All intermediate results will be in the range of [-2^31, 2^31 - 1].

Note: You are not allowed to use any built-in function which evaluates strings as mathematical expressions, such as eval().

Example 1:

• Input: s = “3+2*2”
• Output: 7

Example 2:

• Input: s = “ 3/2 “
• Output: 1

Example 3:

• Input: s = “ 3+5 / 2 “
• Output: 5

Problem Solving Process

• Use a variable num to accumulate digits

• Use a variable sign to remember the last operator

For each character:

• If digit → build the number

• If operator or end of string:

  • Based on sign, apply the operation to the current num and update the stack

  • Reset num to 0

  • Update sign to the current operator

• The sum of all values in the stack gives the final resultThe sum of all values in the stack gives the final result

Code accomplish

class Solution(object):
    def calculate(self, s):
        """
        :type s: str
        :rtype: int
        """
        stack = []
        sign = "+"
        num = 0
        s = s.replace(" ","") + "+"

        for c in s:
            if c.isdigit():
                num = num * 10 + int(c)
            else:
                if sign == "+":
                    stack.append(num)
                elif sign == "-":
                    stack.append(-num)
                elif sign == "*":
                    stack.append(stack.pop() * num)
                elif sign == "/":
                    last = stack.pop()
                    stack.append(int(last / float(num)))
                num = 0
                sign = c
        return sum(stack)