卖萌的弱渣

I am stupid, I am hungry.

Basic Calculator 2

Implement a basic calculator to evaluate a simple expression string.

The expression string contains only non-negative integers, +, -, * , / operators and empty spaces . The integer division should truncate toward zero.

You may assume that the given expression is always valid.

Examples:

1
2
3

"3+2*2" = 7
" 3/2 " = 1
" 3+5 / 2 " = 5

Note

Do not use the eval built-in library function.

Solution

Java

(Basic-Calculator2.java) download
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

public class Solution {
    public int calculate(String s) {
        if(s==null || s.length()==0) return 0;
        int len = s.length();
        Stack<Integer> stack = new Stack<Integer>();
        int num = 0;
        char ops = '+';
        for(int i=0;i<len;i++){
            // number
            if(Character.isDigit(s.charAt(i))){
                num = num*10 + s.charAt(i)-'0';
            }
            // ops: 我们使用的是上一次的ops
            if((!Character.isDigit(s.charAt(i)) && s.charAt(i) != ' ') || i==len-1){
                if(ops == '+')
                    stack.push(num);
                if(ops == '-')
                    stack.push(-num);
                if(ops == '*')
                    stack.push(stack.pop()*num);
                if(ops == '/')
                    stack.push(stack.pop()/num);
                ops = s.charAt(i);
                num = 0;

            }
        }
        int ret = 0;
        for(int i: stack)
            ret+=i;
        return ret;
    }
}

Python

  • 若当前运算符为乘除法，则马上对d与下一个运算数执行乘除运算，赋值给d；

  • 若当前运算符为加减法，则对total与d执行func（加减）运算，赋值给total，并更新func；

(Basic-Calculator2.py) download
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
87
88
89
90

### This solution will Timeout
class Solution(object):
    def calculate(self, s):
        """
        :type s: str
        :rtype: int
        """
        seq = re.split('(\D)',s)
        operator = []
        nums = []
        stack = []
        i = 0

        while i < len(seq):
            if seq[i] == " ":
                i += 1
                continue
            # number
            if seq[i] not in "+-*/":
                stack.append(int(seq[i]))
                i += 1

            # operator: */ will handle the calculation here
            if seq[i] in "*/":
                left = stack.pop()
                right = int(seq[i+1])
                if seq[i] == "*":
                    ret = left*right
                else:
                    ret = left / right
                stack.append(ret)
                i += 2
            else:
                # "+-"
                stack.append(seq[i])
                i += 1
        # handle +- here
        while len(stack) > 1:
            left = stack.pop(0)
            op = stack.pop(0)
            right = stack.pop(0)

            if op == "+":
                stack.insert(left+right)
            else:
                stack.insert(left-right)

        return stack[0]




class Solution(object):
    def calculate(self, s):
        """
        :type s: str
        :rtype: int
        """
        s = re.sub(r'\d+', ' \g<0> ', s)
        seq = s.split()

        idx = 0
        total = 0
        d = 0
        last_op = "+"
        while idx < len(seq):

            # numbers
            if seq[idx] not in "*/+-":
                d = int(seq[idx])
            # calculate "*" and "/" immediately
            if seq[idx] in "*/":
                if seq[idx] == "*":
                    d = d*int(seq[idx+1])
                if seq[idx] == "/":
                    d = d/int(seq[idx+1])
                idx += 1
            # only interest in last_op
            if seq[idx] in "+-":
                if last_op == "+":
                    total += d
                if last_op == "-":
                    total -= d
                last_op = seq[idx]
            idx += 1

        if last_op == "+":
            return total+d
        else:
            return total-d