LeetCode 227 基本计算器 II 【c++/ja

发表于

这是我参与11月更文挑战的第20天，活动详情查看：2021最后一次更文挑战」

1、题目

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

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

示例 1：

1
2
ini复制代码输入：s = "3+2*2"
输出：7

示例 2：

1
2
ini复制代码输入：s = " 3/2 "
输出：1

示例 3：

1
2
ini复制代码输入：s = " 3+5 / 2 "
输出：5

提示：

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

2、思路

(栈,表达式求值) O(n)O(n)O(n)

对于表达式求值这类问题，我们维护两个栈，一个num栈用来记录数字，一个op栈用来记录操作符，遍历表达式，遇到操作符时进行数的相应计算。

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


具体定义如下：

1
2
3
4
5
6
7
8
9
10
11
12
c复制代码void eval() 
{
    int b = num.top(); num.pop();
    int a = num.top(); num.pop();
    char c = op.top(); op.pop();
    int r;
    if (c == '+') r = a + b;
    else if (c == '-') r = a - b;
    else if (c == '*') r = a * b;
    else r = a / b;
    num.push(r);
}

然后我们从前往后扫描整个表达式：

  • 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)O(n)O(n) 。

3、c++代码

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
c复制代码class Solution {
public:
    stack<int> num;  //存贮数字
    stack<char> op;  //存贮操作

    void eval() 
    {
        int b = num.top(); num.pop();
        int a = num.top(); num.pop();
        char c = op.top(); op.pop();
        int r;
        if (c == '+') r = a + b;
        else if (c == '-') r = a - b;
        else if (c == '*') r = a * b;
        else r = a / b;
        num.push(r);
    }

    int calculate(string s) {
        s = '0' + s;  // 对开头是负数的处理 
        unordered_map<char, int> pr; 
        pr['+'] = pr['-'] = 1, pr['*'] = pr['/'] = 2; //定义运算符的优先级
        for(int i = 0; i < s.size(); i++)
        {
            char c = s[i]; 
            if(c == ' ') continue;  //跳过空格
            if(isdigit(c))     //c是数字,读取一个连续的数字
            {
                int x = 0, j = i;
                while(j < s.size() && isdigit(s[j])) x = x * 10 + (s[j++] - '0');
                num.push(x);    //加入数字栈中
                i = j - 1;        
            }
            else  //c是操作符 
            {     //op栈非空并且栈顶操作符优先级大于等于当前操作符c的优先级，进行eval()计算
                while(op.size() && pr[op.top()] >= pr[c]) eval(); 
                op.push(c);
            }
        }
        while(op.size()) eval(); 
        return num.top();
    }
};

4、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
java复制代码class Solution {
    static Stack<Integer> num = new Stack<Integer>();
    static Stack<Character> op = new Stack<Character>();
    static HashMap<Character, Integer> map = new HashMap<Character, Integer>();
    static void eval()
    {
        int b = num.pop();
        int a = num.pop();
        char c = op.pop();
        int r = 0;
        if(c == '+') r = a + b;
        else if(c == '-') r = a - b;
        else if(c == '*') r = a * b;
        else r = a / b;
        num.add(r); 
    }
    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, j = i;
                while(j < s.length() && s.charAt(j) >= '0' && s.charAt(j) <= '9')
                {
                    x = x * 10 + s.charAt(j) - '0';
                    j ++;
                }
                i = j - 1;
                num.add(x);
            }
            else  //c是操作符 
            {     //op栈非空并且栈顶操作符优先级大于等于当前操作符c的优先级，进行eval()计算
                while(!op.isEmpty() && map.get(op.peek()) >= map.get(c)) eval();
                op.add(c); 
            }
        }
        while(!op.isEmpty()) eval();
        return num.pop();
    }
}

原题链接： 227. 基本计算器 II
在这里插入图片描述

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

0%