[Leetcode 2021 刷题计划] 227. 基本计算器 II

每日一题时间: 2020-03-11 题目链接: 227. 基本计算器 II 官方题解链接: 基本计算器 II

题目

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

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

代码语言：txt复制

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

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

示例 3：
输入：s = " 3 5 / 2 "
输出：5

提示：

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

解题方法

相较于224. 基本计算器变化在于剔除括号，新增乘除法,此时需要考虑的是算法优先级的问题，即如何将乘除相关的先进行合并

栈

将整个算式以加减和空格进行分割，从而转化为多个数字相加

代码语言：txt复制

A - B   C * D - E / F
A   (-B)   (C * D)   (-E / F)

因此栈仅需保存各个部分的数字, 对于乘除法需要拉取栈顶进行计算。

代码语言：txt复制

class Solution {
public:
    int calculate(string s) {
        vector<int> stk;
        char preSign = ' ';
        int num = 0;
        int n = s.length();
        for (int i = 0; i < n;   i) {
            if (isdigit(s[i])) {
                num = num * 10   int(s[i] - '0');
            }
            if (!isdigit(s[i]) && s[i] != ' ' || i == n - 1) {
                switch (preSign) {
                    case ' ':
                        stk.push_back(num);
                        break;
                    case '-':
                        stk.push_back(-num);
                        break;
                    case '*':
                        stk.back() *= num;
                        break;
                    default:
                        stk.back() /= num;
                }
                preSign = s[i];
                num = 0;
            }
        }
        return accumulate(stk.begin(), stk.end(), 0);
    }
};

• 复杂度分析
  • 时间复杂度: O(N)
  • 空间复杂度: O(N)

参考资料

1. 227. 基本计算器 II
2. 基本计算器 II

bit

0 人点赞