227. Basic Calculator II

发表于 | 分类于

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.

Some examples:

“3+2*2” = 7
“ 3/2 “ = 1
“ 3+5 / 2 “ = 5

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

解法1：

用一个stack来存储中间结果。遇上×，／的时候计算之前的操作，遇上＋／－的时候只有在之前的操作为同一优先级的时候才计算。
写的比较繁琐，不如leetcode上的答案好。答案里不需要有stack, 用一个preVal来记录上一个计算的结果，只有当当前操作为加或者减的时候才需要把上一次更新的结果并入最终的结果。
C++

1

Java

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
91
public class Solution {
    public int calculate(String s) {
        Stack<Integer> operands = new Stack<Integer>();
        Stack<String> operators = new Stack<String>();
        int i = 0;
        while (i < s.length()) {
            if (s.charAt(i) == ' ') {
                i++;
                continue;
            } else if (s.charAt(i) == '+' || s.charAt(i) == '-'){
                if (!operators.empty()) {
                    int right = operands.pop();
                    int left = operands.pop();
                    String last = operators.pop();
                    if (last.equals("+")) {
                        operands.push(left + right);
                    } else if (last.equals("-")) {
                        operands.push(left - right);
                    } else if (last.equals("*")) {
                        operands.push(left * right);
                    } else {
                        operands.push(left / right);
                    }
                }
                operators.push(s.substring(i, i + 1));
                i++;
            } else if (s.charAt(i) == '*' || s.charAt(i) == '/') {
                if (!operators.empty()) {
                    String last = operators.peek();
                    if (last.equals("*")) {
                        operators.pop();
                        int right = operands.pop();
                        int left = operands.pop();
                        operands.push(left * right);
                    } else if (last.equals("/")) {
                        operators.pop();
                        int right = operands.pop();
                        int left = operands.pop();
                        operands.push(left / right);
                    }
                }
                operators.push(s.substring(i, i + 1));
                i++;
            } else {
                int j = i + 1;
                while (j < s.length() && s.charAt(j) >= '0' && s.charAt(j) <= '9') {
                    j++;
                }
                int element = Integer.parseInt(s.substring(i, j));
                // check if there is valid * or / operators
                if (!operators.empty()) {
                    if (operators.peek().equals("*")) {
                        operators.pop();
                        int left = operands.pop();
                        operands.push(left * element);
                    } else if (operators.peek().equals("/")) {
                        operators.pop();
                        int left = operands.pop();
                        operands.push(left / element);
                    } else {
                        operands.push(element);
                    }
                } else {
                    operands.push(element);                
                }
                i = j;
            }
        }
        // empty operators until it is empty
        while (!operators.empty()) {
            String operator = operators.pop();
            int right = operands.pop();
            int left = operands.pop();
            if (operator.equals("*")) {
                operands.push(left * right);
            } else if (operator.equals("/")) {
                operands.push(left / right);
            } else if (operator.equals("+")) {
                operands.push(left + right);
            } else {
                operands.push(left - right);
            }
        }
        return operands.pop();
    }
}

###解法２：　###
答案来自与leetcode
Java

lang: java
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
public int calculate(String s) {
    if (s == null) return 0;
    s = s.trim().replaceAll(" +", "");
    int length = s.length();
    int res = 0;
    long preVal = 0; // initial preVal is 0
    char sign = '+'; // initial sign is +
    int i = 0;
    while (i < length) {
        long curVal = 0;
        while (i < length && (int)s.charAt(i) <= 57 && (int)s.charAt(i) >= 48) { // int
            curVal = curVal*10 + (s.charAt(i) - '0');
            i++;
        }
        if (sign == '+') {
            res += preVal;  // update res
            preVal = curVal;
        } else if (sign == '-') {
            res += preVal;  // update res
            preVal = -curVal;
        } else if (sign == '*') {
            preVal = preVal * curVal; // not update res, combine preVal & curVal and keep loop
        } else if (sign == '/') {
            preVal = preVal / curVal; // not update res, combine preVal & curVal and keep loop
        }
        if (i < length) { // getting new sign
            sign = s.charAt(i);
            i++;
        }
    }
    res += preVal;
    return res;
}