echo

任生命穿梭 时间的角落

0%

基本计算器II

Posted on In Valine:

227. 基本计算器 II

给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。

整数除法仅保留整数部分。

示例 1：

1
2
输入：s = "3+2*2"
输出：7

示例 2：

1
2
输入：s = " 3/2 "
输出：1

示例 3：

1
2
输入：s = " 3+5 / 2 "
输出：5

提示：

  • 1 <= s.length <= 3 * 105
  • s 由整数和算符 ('+', '-', '*', '/') 组成，中间由一些空格隔开
  • s 表示一个 有效表达式
  • 表达式中的所有整数都是非负整数，且在范围 [0, 231 - 1] 内
  • 题目数据保证答案是一个 32-bit 整数

此题没有括号，乘除优先于加减计算，不妨先进行所有的乘除运算，并将这些乘除运算后的整数放回原来的位置，之后整个表达式的值，就等于一系列整数加减后的值。

我们可以使用一个栈来保存进行乘除运算后的整数的值。对于加减号后的数字，直接压入栈中；对于乘除号后的数字，直接与栈顶元素计算，并替换栈顶元素为计算后的结果。

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
class Solution {
    public int calculate(String s) {
        Deque<Integer> stack = new LinkedList<Integer>();
        //第一个数字前的符号设置为 + ，直接将第一个数入栈
        char preSign = '+';
        int num = 0;
        int n = s.length();
        for(int i = 0; i < n; i++){
            //将连续的数字字符转换为整数
            if(Character.isDigit(s.charAt(i))){
                num = num * 10 + s.charAt(i) - '0';
            }
            //当前字符不是数字或空格，或者当前是最后一个字符，计算最后结果	
            if(!Character.isDigit(s.charAt(i)) && s.charAt(i) != ' ' || i == n - 1){
                switch (preSign) {
                    case '+': stack.push(num); break;
                    case '-': stack.push(-num); break;
                    case '*': stack.push(stack.pop() * num); break;
                    case '/': stack.push(stack.pop() / num); break;
                }
            //更新符号和数字
            num = 0;
            preSign = s.charAt(i);
            }
        }
		//将所有数字相加，得到最后结果
        int ans = 0;
        while(!stack.isEmpty()){
            ans += stack.pop();
        }

        return ans;
    }
}