Skip to content

Prepare For Coder Interview – Denny

  • Basic
  • Medium
  • Hard
  • Architect
  • Life

LeetCode: Basic Calculator III

Posted on January 26, 2018July 26, 2020 by braindenny

Basic Calculator III



Similar Problems:

  • CheatSheet: Leetcode For Code Interview
  • CheatSheet: Common Code Problems & Follow-ups
  • Tag: #manydetails, #stack, #calculator

Implement a basic calculator to evaluate a simple expression string.

The expression string may contain open ( and closing parentheses ), the plus + or minus sign -, non-negative integers and empty spaces .

The expression string contains only non-negative integers, +, -, *, / operators , open ( and closing parentheses ) and empty spaces . 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 [-2147483648, 2147483647].

Some examples:

"1 + 1" = 2
" 6-4 / 2 " = 4
"2*(5+5*2)/3+(6/2+8)" = 21
"(2+6* 3+5- (3*14/7+2)*5)+3"=-12

Note: Do not use the eval built-in library function.

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.


## https://code.dennyzhang.com/basic-calculator-iii
## Basic Ideas: +- yield to */
##
##           When we found one operator as +/, look for the next operator
##           When we found one operator as */, we solve it immediately
## Complexity: Time O(n), Space O(n)
class Solution(object):
    def calculate(self, s):
        """
        :type s: str
        :rtype: int
        """
        stack = []
        s = s.replace(' ', '')
        i, length = 0, len(s)
        while i<length:
            # print stack
            ch = s[i]
            if ch == '(':
                stack.append(ch)
            elif ch == ')':
                str_temp = stack.pop()
                stack.pop() # (
                str_temp = str(self.calculate_no_parenthese(str_temp))
                if len(stack) != 0 and (stack[-1] != '('):
                    stack[-1] = "%s%s" % (stack[-1], str_temp)
                else:
                    stack.append(str_temp)
            else:
                str_temp = ''
                while i<length and s[i] not in '()':
                    str_temp = '%s%s' % (str_temp, s[i])
                    i += 1
                if len(stack) != 0 and (stack[-1] != '('):
                    stack[-1] = "%s%s" % (stack[-1], str_temp)
                else:
                    stack.append(str_temp)
                continue
            i += 1
        return self.calculate_no_parenthese(stack[0])

    def calculate_no_parenthese(self, s):
        """
        :type s: str
        :rtype: int
        """
        """
        :type s: str
        :rtype: int
        """
        s = s.replace(' ', '')
        s = s.replace('--', '+')
        i = 0
        length = len(s)
        # solve */
        stack = []
        while i<length:
            if s[i].isdigit():
                # get the num
                num_str = ''
                while i<length and s[i].isdigit():
                    num_str = "%s%s" % (num_str, s[i])
                    i += 1
                stack.append(num_str)
            elif s[i] in '*/':
                num1 = int(stack.pop())
                num_str = ''
                op = s[i]
                # find the next number
                i += 1
                while i<length and s[i].isdigit():
                    num_str = "%s%s" % (num_str, s[i])
                    i += 1
                num2 = int(num_str)
                if op == '*':
                    num1 = num1*num2
                else:
                    num1 = num1/num2
                stack.append(str(num1))
            else:
                # +-
                stack.append(s[i])
                i += 1

        # solve +-
        res, i = 0, 0
        while i<len(stack):
            element = stack[i]
            if element in '+-':
                num2 = stack[i+1]
                i = i+2
                if element == '+':
                    res += int(num2)
                else:
                    res -= int(num2)
            else:
                res += int(element)
                i += 1
        return res
linkedin
github
slack

Post Views: 9
Posted in HardTagged #codetemplate, #manydetails, #stack, calculator, redo

Post navigation

LeetCode: Largest Rectangle in Histogram
LeetCode: Longest Substring Without Repeating Characters

Leave a Reply Cancel reply

Your email address will not be published.

Tags

#array #backtracking #bfs #binarytree #bitmanipulation #blog #classic #codetemplate #combination #dfs #dynamicprogramming #game #graph #greedy #heap #inspiring #interval #linkedlist #manydetails #math #palindrome #recursive #slidingwindow #stack #string #subarray #trie #twopointer #twosum binarysearch editdistance hashmap intervaldp knapsack monotone oodesign presum rectangle redo review rotatelist series sql treetraversal unionfind

Recent Posts

  • a
  • a
  • a
  • a
  • a

Recent Comments

    Archives

    Categories

    • Amusing
    • Basic
    • Easy
    • Hard
    • Life
    • Medium
    • Resource
    • Review
    • Series
    • Uncategorized
    Proudly powered by WordPress | Theme: petals by Aurorum.