Basic Calculator

Question

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 .

You may assume that the given expression is always valid.

Some examples:

"1 + 1" = 2
" 2-1 + 2 " = 3
"(1+(4+5+2)-3)+(6+8)" = 23

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

Tags

• Stack
• Math

Thought

Two solutions:

• Without Reverse Polish notation(RPN)
• With Reverse Polish notation(RPN)

Without Reverse Polish notation Reference: https://discuss.leetcode.com/topic/15806/easy-18-lines-c-16-lines-python Since the calculation here only involves '+' and '-', it is possible to consider the whole calculation process happens between the sum of all integers (including positive integer and negative integer). Then we can use a stack of sign symbol for calculation.

With Reverse Polish notation Reference: http://bookshadow.com/weblog/2015/06/09/leetcode-basic-calculator/ This we need to convert the expression to reverse polish notation at first and then calculate the result. The algorithm for converting the infix notation to reverse polish notation is followed as Shunting-yard algorithm. After converting it, the calculation process is simple.

Notice Even though the efficiency of the algorithm without RPN is better, the practice with RPN is also recommended, because it is more universal in different problems.

Code

Without Reverse Polish notation

class Solution(object):
    def calculate(self, s):
        """
        :type s: str
        :rtype: int
        """
        result = 0
        i, sign = 0, [1, 1]
        while i < len(s):
            c = s[i]
            if c.isdigit():
                start = i
                while i < len(s) and s[i].isdigit():
                    i += 1
                result += sign.pop() * int(s[start:i])
                continue
            if c in '+-(':
                if c in '+(':
                    sign += [sign[-1]]
                else:
                    sign += [-sign[-1]]
            elif c == ')':
                sign.pop()
            i += 1
        return result

With Reverse Polish notation

class Solution(object):
    priorityDict = {'+': 1, '-':1, '*':2, '/':2}

    def toRPN(self, s):
        i = 0
        rpnList, stack = [], []
        while i < len(s):
            c = s[i]
            if c.isdigit():
                start = i
                while i < len(s) and s[i].isdigit():
                    i += 1
                rpnList.append(s[start:i])
                continue
            if c in self.priorityDict.keys():
                while stack and stack[-1] in self.priorityDict.keys() and self.priorityDict[stack[-1]] >= self.priorityDict[c]:
                    rpnList.append(stack.pop())
                stack.append(c)
            elif c == '(':
                stack.append(c)
            elif c == ')':
                while stack and stack[-1] != '(':
                    rpnList.append(stack.pop())
                stack.pop()
            i += 1
        while stack:
            rpnList.append(stack.pop())
        return rpnList

    def calculate(self, s):
        """
        :type s: str
        :rtype: int
        """
        if s == '':
            return 0
        rpnList = self.toRPN(s)
        stack = []
        for item in rpnList:
            if item not in self.priorityDict.keys():
                stack.append(int(item))
            else:
                reg2 = stack.pop()
                reg1 = stack.pop()
                if item == '+':
                    stack.append(reg1 + reg2)
                elif item == '-':
                    stack.append(reg1 - reg2)
                elif item == '*':
                    stack.append(reg1 * reg2)
                else:
                    stack.append(reg1 / reg2)
        return stack[0]