FazBrowse GitHub Viewer | Trending | | Home

Tools: [Download Repo ZIP] [View Raw Code] [Original HTTPS Page]

LeetCode-Solutions/Python/basic-calculator-ii.py at master · pythonpeixun/LeetCode-Solutions · GitHub

45 lines (39 loc) · 1.4 KB

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

# Time: O(n)

# Space: O(n)

class Solution(object):

# @param {string} s

# @return {integer}

def calculate(self, s):

operands, operators = [], []

operand = ""

for i in reversed(xrange(len(s))):

if s[i].isdigit():

operand += s[i]

if i == 0 or not s[i-1].isdigit():

operands.append(int(operand[::-1]))

operand = ""

elif s[i] == ')' or s[i] == '*' or s[i] == '/':

operators.append(s[i])

elif s[i] == '+' or s[i] == '-':

while operators and \

(operators[-1] == '*' or operators[-1] == '/'):

self.compute(operands, operators)

operators.append(s[i])

elif s[i] == '(':

while operators[-1] != ')':

self.compute(operands, operators)

operators.pop()

while operators:

self.compute(operands, operators)

return operands[-1]

def compute(self, operands, operators):

left, right = operands.pop(), operands.pop()

op = operators.pop()

if op == '+':

operands.append(left + right)

elif op == '-':

operands.append(left - right)

elif op == '*':

operands.append(left * right)

elif op == '/':

operands.append(left / right)

Back | FazBrowse Home | New Git URL