LeetCode224-基本计算器

发表于 | 分类于

题目链接

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

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

题目详述

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

字符串表达式可以包含左括号 ( ，右括号 )，加号 + ，减号 -，非负整数和空格 。

示例 1:

1
2
输入: "1 + 1"
输出: 2

示例 2:

1
2
输入: " 2-1 + 2 "
输出: 3

示例 3:

1
2
输入: "(1+(4+5+2)-3)+(6+8)"
输出: 23

说明：

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

题目详解

  • LeetCode150-逆波兰表达式求值 是逆波兰表达式（后缀表达式）求值，本题是则是中缀表达式（只含加减，带括号）求值。
  • 运用两个栈，一个用来记录运算符，另一个用来记录数字。然后从前往后遍历整个表达式。
  • 如果碰到 (、+、-，直接入栈。
  • 如果碰到 )，保证运算符栈顶一定是 (，将其弹出。然后根据运算符栈顶操作符，对数字栈顶的两个元素进行运算后压栈。
  • 如果碰到数字，求出当前数入栈，并判断运算符栈的栈顶元素，如果不是 (，则弹出运算符栈的栈顶元素，并对数字栈顶的两个元素进行运算后压栈。从而保证运算符栈的栈顶最多有一个连续的 + 或 -。
  • 延申讨论可查看 表达式求值。
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
public class LeetCode_00224 {

    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] == '+' || cs[i] == '-') {
                op.push(cs[i]);
            } else if (cs[i] == ')') {
                op.pop();
                if (!op.isEmpty() && op.peek() != '(') {
                    calc(op, num);
                }
            } 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;
                }
                num.push(k);
                i = j - 1;
                if (!op.isEmpty() && op.peek() != '(') {
                    calc(op, num);
                }
            }
        }
        return num.peek();
    }

    private void calc(Deque<Character> op, Deque<Integer> num) {
        int y = num.pop();
        int x = num.pop();
        if (op.pop() == '+') {
            num.push(x + y);
        } else {
            num.push(x - y);
        }
    }
}