Leetcode227. 基本计算器 II

2021年8月14日 530点热度 0人点赞 0条评论

题目描述

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

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

示例 1:

输入:s = "3+2*2"
输出:7

示例 2:

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

示例 3:

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

提示:

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

解题思路

这道题可以运用栈来模拟运算。思路应该说没有什么难度,加减直接压入栈就好,乘除就得先和栈中的顶元素计算,然后压入栈中。最后,将栈中的元素顺序计算就好。关键的难度在于实现,要注意需要将字符串同步转化为整数。

如果用两个栈来实现,可以一个栈存储元素,一个栈来存储运算符。然后按照规则进行模拟。如果用一个栈来模拟,实现上就要麻烦一点。

以字符串"3+2*2"来举例:

首先,将字符串变为"+3+2*2",在前面加上运算符+。这样,在指针滑动到某个运算符的时候,就可以处理上一个运算符后面,也就是这个运算符前面的元素。但是同时的,当指针滑动到最后的时候,也需要处理最后的一个元素。所以进入这些操作的条件是:

if((!isdigit(s[i]) && s[i] != ' ') || i == s.size() - 1)

而对每一个运算符所做的处理为:

switch (op)
{
    case '+':
        stokens.push(num);
        break;

    case '-':
        stokens.push(-num);
        break;

    case '*':
        pre = stokens.top();
        stokens.pop();
        stokens.push(pre * num);
        break;

    case '/':
        pre = stokens.top();
        stokens.pop();
        stokens.push(pre / num);
        break;
}

也就是加法直接压入元素,减法压入这个 元素的负值,乘除法进行处理后再压入。具体细节见参考代码。

参考代码

int calculate(string s){
    if(s.empty()) return 0;

    stack<int>stokens;
    int num = 0;
    char op = '+';
    int pre = 0;
    for(int i = 0;i < s.size();++i){
        if(isdigit(s[i])){
            num = num * 10 + (s[i] - '0');
        }

        if((!isdigit(s[i]) && s[i] != ' ') || i == s.size() - 1){
            switch (op)
            {
            case '+':
                stokens.push(num);
                break;

            case '-':
                stokens.push(-num);
                break;

            case '*':
                pre = stokens.top();
                stokens.pop();
                stokens.push(pre * num);
                break;

            case '/':
                pre = stokens.top();
                stokens.pop();
                stokens.push(pre / num);
                break;
            }
            op = s[i];
            num = 0;
        }
    }

    int ans = 0;
    while(!stokens.empty()){
        ans += stokens.top();
        stokens.pop();
    }

    return ans;
}

复杂度分析

时间复杂度:$O(n)$,其中 $n$为字符串 $s$​的长度

空间复杂度:$O(n)$,其中 $n$为字符串 $s$的长度

agedcat_xuanzai

这个人很懒,什么都没留下

文章评论

您需要 登录 之后才可以评论