LeetCode227-基本计算器II

发表于 | 分类于

题目链接

英文链接：https://leetcode.com/problems/basic-calculator-ii/

中文链接：https://leetcode-cn.com/problems/basic-calculator-ii/

题目详述

实现一个基本的计算器来计算一个简单的字符串表达式的值。

字符串表达式仅包含非负整数，+， - ，*，/ 四种运算符和空格 。 整数除法仅保留整数部分。

示例 1:

1
2
输入: "3+2*2"
输出: 7

示例 2:

1
2
输入: " 3/2 "
输出: 1

示例 3:

1
2
输入: " 3+5 / 2 "
输出: 5

说明：

  • 你可以假设所给定的表达式都是有效的。
  • 请不要使用内置的库函数 eval。

题目详解

  • LeetCode224-基本计算器 是中缀表达式，本题也是中缀表达式，并且没有括号，运算符包含加减乘除。
  • 运用两个栈，一个用来记录运算符，另一个用来记录数字。然后从前往后遍历整个表达式。
  • 如果碰到 *、/，直接入栈。
  • 如果碰到 +、-，如果运算符栈不为空，弹出栈顶元素进行运算压栈，然后把当前运算符入栈。
  • 如果碰到数字，求出当前数入栈，并判断运算符栈的栈顶是否为 * 或 /。如果是，则弹出栈顶元素进行运算。
  • 采用上面算法的理由是，乘除比加减的优先级高，每当运算符栈顶为 * 或 /，可以直接运算。每当前运算符为 + 或 -，且栈不为空，也要先进行运算，这样是为了保证栈顶最多出现一个连续的 + 或 -。
  • 遍历完成后，运算符栈要么为空，要么存在一个 + 或一个 -，弹出进行计算即可。
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
public class LeetCode_00227 {

    public int calculate(String s) {
        char[] cs = s.toCharArray();
        Deque<Character> op = new ArrayDeque<>();
        Deque<Integer> num = new ArrayDeque<>();
        for (int i = 0; i < cs.length; ++i) {
            if (cs[i] == '*' || cs[i] == '/') {
                op.push(cs[i]);
            } else if (cs[i] == '+' || cs[i] == '-') {
                if (!op.isEmpty()) {
                    calc(op, num);
                }
                op.push(cs[i]);
            } else if (Character.isDigit(cs[i])) {
                int j = i;
                int k = 0;
                while (j < cs.length && Character.isDigit(cs[j])) {
                    k = k * 10 + cs[j] - '0';
                    ++j;
                }
                i = j - 1;
                num.push(k);
                if (!op.isEmpty() && (op.peek() == '*' || op.peek() == '/')) {
                    calc(op, num);
                }
            }
        }
        if (!op.isEmpty()) {
            calc(op, num);
        }
        return num.peek();
    }

    private void calc(Deque<Character> op, Deque<Integer> num) {
        int y = num.pop();
        int x = num.pop();
        switch (op.pop()) {
            case '*':
                num.push(x * y);
                break;
            case '/':
                num.push(x / y);
                break;
            case '+':
                num.push(x + y);
                break;
            default:
                num.push(x - y);
                break;
        }
    }
}