Fork me on GitHub

Basic Caculator II

Posted on

In this question, we need to implement a naive caculator, but thing will never be easu for the rookie like me, so lets go through it.

Description

Given a nested list of integers represented as a string, implement a parser to deserialize it.

Each element is either an integer, or a list – whose elements may also be integers or other lists.

Note: You may assume that the string is well-formed:

  • String is non-empty.
  • String does not contain white spaces.
  • String contains only digits 0-9, [, - ,, ].

Discuss

From the textbook we learn that the data structure Stack will be of great help to get the value from expression. The following code just implement it with the given rules.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
import pdb
class Solution(object):
    
    def calculate(self, s):
        """
        :type s: str
        :rtype: int
        """
        def add(a, b):
            return a+b
        def sub(a, b):
            return a-b
        def dot(a, b):
            return a*b
        def divide(a, b):
            return int(a/b)
        
        self.s = s
        self.length = len(s)
        self.index = 0
        self.operator_dict = {
            " ": 0,
            "+": (1, add),
            "-": (1, sub),
            "*": (2, dot),
            "/": (2, divide)
        }
        self.expression_stack = []
        self.number_stack = []
        while self.index < self.length:
            self.escape_space()
            self.processNumber()
            self.escape_space()
            self.processOperator()

        while self.expression_stack:
            self.doCaculate()
            
        return self.number_stack[0]
    
    def doCaculate(self):
        right = self.number_stack.pop()
        left = self.number_stack.pop()
        func = self.expression_stack.pop()[1]
        result = func(left, right)
        self.number_stack.append(result)
    
    def escape_space(self):
        while self.index < self.length and self.s[self.index] == ' ':
            self.index += 1
        return 
    
    def processOperator(self):
        if self.index >= self.length:
            return
        operator = self.s[self.index]
        self.index += 1
        tup = self.operator_dict[operator]
        
        ##In case the first element of the expression stack
        while self.expression_stack and tup[0] <= self.expression_stack[-1][0]:
                self.doCaculate()
        
        self.expression_stack.append(tup)
        
    
    def processNumber(self):
        if self.index >= self.length:
            return 
        number_stack = []
        while self.index < self.length and self.isdigit():
            number_stack.append(int(self.s[self.index]))
            self.index += 1
        
        ret_num = 0
        bit = 1
        while number_stack:
            current = number_stack.pop()
            ret_num += current*bit
            bit *= 10
            
        self.number_stack.append(ret_num)

if __name__ == '__main__':
    s = Solution()
    print(s.calculate("1*2-3/4+5*6-7*8+9/10"))

Detail

In fact , this implementation can extended to support more operators, life exponential, and the another question on leetcode Basic Caculator IV is more considering the parentheses.