227. 基本计算器 II

题目描述

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

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

你可以假设给定的表达式总是有效的。所有中间结果将在 [-231, 231 - 1] 的范围内。

注意：不允许使用任何将字符串作为数学表达式计算的内置函数，比如 eval() 。

输入输出

1
2
3
4
5
6
7
8
输入：s = "3+2*2"
输出：7

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

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

基本思路

leetcode 224/227 有些类似 逆波兰式解决

声明两个栈 一个放数字num 一个放操作符op

再定义一个eval() 用于从数字栈num中弹出两个数字a和b，再从操作符栈op中弹出操作符号，进行计算后将结果数字加入到数字栈num中。

1、当遇到空格 ‘ ‘时，跳过。

2、当遇到数字时，则读取一个连续的完整数字，再将其加入到数字栈num中。

3、当遇到’+’，’-‘，’*’，’/‘ 运算符时，需要考虑优先级：

  • 如果操作符栈op的栈顶元素的优先级比当前遇到的操作符优先级高或者相等，则while循环进行eval()操作，即将数字栈num栈顶的两个元素取出来，然后和操作符栈op的栈顶操作符进行相应计算，并将计算结果压回数字栈num中。(这是本题的关键所在，这样的操作保证了操作符栈中的操作符自栈底到栈顶优先级递增。而由于栈的先进后出的特点，后进来的优先级高的操作符会先被用于计算)
    否则，将当前运算符压入操作符栈op中。

4、扫描完整个表达式后，如果操作符栈op中还存在元素，则while循环进行eval()操作。

5、最终返回数字栈num的栈顶元素值。

细节处理：

1、由于运算符有优先级，所以设计一个哈希表来存储加减乘除运算符的优先级，我们将’+’和’-‘设为1级优先级，将’*’和’/‘设为2级优先级。
2、考虑到表达式s的第一个数字可能为负数，因此我们给s开头添加一个字符0。
时间复杂度分析： 每个数字和操作进栈出栈一次，所以总的时间复杂度是 O(n)。

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
class Solution {
    Stack<Integer> num = new Stack<Integer>();
    Stack<Character> op = new Stack<Character>();
    HashMap<Character, Integer> map = new HashMap<Character, Integer>();

    public int calculate(String s) {
        //处理第一位是负号的情况
        s = '0' + s;
        // 定义优先级
        map.put('+', 1);
        map.put('-', 1);
        map.put('*', 2);
        map.put('/', 2);

        for(int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if(c == ' ') continue;
            if(c >= '0' && c <= '9'){// c是数字
                int x = 0;
                while(i < s.length() && s.charAt(i) >= '0' && s.charAt(i) <= '9'){
                    x = x * 10 + s.charAt(i++) - '0';
                }
                i--;
                num.add(x);
            }
            else{// c是操作符
                while(!op.isEmpty() && map.get(op.peek()) >= map.get(c)){
                    eval();
                }
                op.add(c);
            }
        }
        while(!op.isEmpty()) eval();
        return num.pop();
    }

    public void eval(){
        int b = num.pop();
        int a = num.pop();
        char c = op.pop();
        int res = 0;

        if(c == '+') res = a + b;
        else if(c == '-') res = a - b;
        else if(c == '*') res = a * b;
        else res = a / b;
        num.add(res);
    }
}