LeetCode 224. Basic Calculator

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

LeetCode 224. Basic Calculator 原题链接困难

作者：

yxc , 2018-06-23 15:45:17 , 所有人可见 , 阅读 3263

8

5

题目描述

请实现一个简易计算器，计算一个算数表达式的值。

表达式中仅包含左括号(、右括号)、加号+、减号-、非负整数 和空格。

注意:

所有表达式都是合法的；
不能使用内建函数 eval 来计算表达式的值；

样例1

输入："1 + 1"
输出：2

样例2

输入：" 2-1 + 2 "
输出：3

样例3

输入；"(1+(4+5+2)-3)+(6+8)"
输出：23

算法

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

开两个栈，一个记录数字，一个记录操作符。
然后从前往后扫描整个表达式：

如果遇到 (、+、-，直接入栈；
如果遇到数字，则判断操作符栈的栈顶元素，如果不是 (，则弹出操作符的栈顶元素，并用相应操作更新数字栈的栈顶元素。从而保证操作符栈的栈顶最多有一个连续的+或-；
如果遇到 )，此时操作符栈顶一定是 (，将其弹出。然后根据新栈顶的操作符，对数字栈顶的两个元素进行相应操作；

时间复杂度分析：每个数字和操作进栈出栈一次，所以总时间复杂度是 $O(n)$。

C++ 代码

class Solution {
public:

    void calc(stack<char> &op, stack<int> &num) {
        int y = num.top();
        num.pop();
        int x = num.top();
        num.pop();
        if (op.top() == '+') num.push(x + y);
        else num.push(x - y);
        op.pop();
    }

    int calculate(string s) {
        stack<char> op;
        stack<int> num;
        for (int i = 0; i < s.size(); i ++ ) {
            char c = s[i];
            if (c == ' ') continue;
            if (c == '+' || c == '-' || c == '(') op.push(c);
            else if (c == ')') {
                op.pop();
                if (op.size() && op.top() != '(') {
                    calc(op, num);
                }
            }
            else {
                int j = i;
                while (j < s.size() && isdigit(s[j])) j ++ ;
                num.push(atoi(s.substr(i, j - i).c_str()));
                i = j - 1;
                if (op.size() && op.top() != '(') {
                    calc(op, num);
                }
            }
        }
        return num.top();
    }
};

19 评论

Vodka编程菜菜 2022-09-22 07:52

可以 ac的版本.加了一个小的改动.就是判定是否需要zero. 都是在特定位置才需要补零的.

class Solution {
public:

void calc(stack<char> &op, stack<int> &num) {
    int y = num.top();
    num.pop();
    int x = num.top();
    num.pop();
    if (op.top() == '+') num.push(x + y);
    else num.push(x - y);
    op.pop();
}

int calculate(string s) {
    stack<char> op;
    stack<int> num;
    bool need_zero = true;
    for (int i = 0; i < s.size(); i ++ ) {
        char c = s[i];
        if (c == ' ') continue;
        if (c == '+' || c == '-'){
            if (need_zero) num.push(0);
            op.push(c);
            need_zero = false;
        } 
        else if (c == '('){
            need_zero = true;
            op.push(c);
        } 
        else if (c == ')') {
            op.pop();
            if (op.size() && op.top() != '(') {
                calc(op, num);
            }
            need_zero = false;
        }
        else {
            int j = i;
            while (j < s.size() && isdigit(s[j])) j ++ ;
            num.push(atoi(s.substr(i, j - i).c_str()));
            i = j - 1;
            if (op.size() && op.top() != '(') {
                calc(op, num);
            }
            need_zero = false;
        }
    }
    return num.top();
}

};

chtld 2022-05-08 09:53

2022-05-08可通过的代码：

class Solution {
public:
    unordered_map<char, int> pr{{'+', 1}, {'-', 1}, {'*', 2}, {'/', 2}};
    stack<int> nums;
    stack<char> op;

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

    void replace(string &s, string a, string b) {
        int pos = s.find(a), m = a.size();
        while (pos != -1) {
            s.replace(pos, m, b);
            pos = s.find(a);
        }
    }

    int calculate(string s) {
        // 处理 s 使之合法
        // 去空格
        replace(s, " ", "");
        // (- 替换为 (0-
        replace(s, "(-", "(0-");
        // (+ 替换为 (0+
        replace(s, "(+", "(0+");
        // 在 nums 中先放个 0 预防开始的符号
        nums.push(0);

        for (int i = 0; i < s.size(); ++ i) {
            char c = s[i];
            if (isdigit(c)) {
                int j = i; int num = 0;
                while (j < s.size() && isdigit(s[j]))
                    num = num * 10 + (s[j++] - '0');
                i = j - 1;
                nums.push(num);
            } else if (c == '(') {
                op.push('(');
            }
            else if (c == ')') {
                while (op.top() != '(') eval();
                op.pop();
            } else {
                while (op.size() && op.top() != '(' && pr[op.top()] >= pr[c]) eval();
                op.push(c);
            }
        }
        while (op.size()) eval();
        return nums.top();
    }
};

梦忆师 8个月前

class Solution {
public:
    void eval(stack<int>&num,stack<char>&op)
    {
        auto b=num.top();num.pop();
        auto a=num.top();num.pop();
        auto c=op.top();op.pop();
        int r;
        if(c=='+') r=a+b;
        else r=a-b;
        num.push(r);
    }
    int calculate(string s) {
        stack<int>num;
        stack<char>op;
        bool need_zero=true;
        for(int i=0;i<s.size();i++)
        {
            auto c=s[i];
            if(c==' ') continue;
            if(c=='+'||c=='-')
            {
                while(op.size()&&op.top()!='(') eval(num,op);
                if(need_zero) num.push(0);

                op.push(c);
                need_zero=false;
            }
            else if(c=='(') 
            {
                need_zero=true;
                op.push(c);
            }
            else if(c==')')         
            {
                while(op.top()!='(') eval(num,op);
                op.pop();
                need_zero=false;
            }
            else
            {
                int x=0,j=i;
                while(j<s.size()&&isdigit(s[j]))
                {
                    x=x*10+(s[j++]-'0');
                }
                i=j-1;
                num.push(x);
                if(op.size()&&op.top()!='(')
                {
                    eval(num,op);
                }
                need_zero=false;
            }
        }

        while(op.size()) eval(num,op);
        return num.top();
    }
};

这波是肉蛋葱鸡 2022-02-08 17:10

用is_neg标示一下接下来读到的-是否表示负号的含义，取负操作只可能出现在表达式开头或紧挨着(，每次读入一个字符后根据是否为(更新一下is_neg即可

class Solution {
public:

    void calc(stack<char> &op, stack<int> &num) {
        int y = num.top();
        num.pop();
        int x = num.top();
        num.pop();
        if (op.top() == '+') num.push(x + y);
        else num.push(x - y);
        op.pop();
    }

    int calculate(string s) {
        bool is_neg = true;
        stack<char> op;
        stack<int> num;
        for (int i = 0; i < s.size(); i ++ ) {
            char c = s[i];
            if (c == ' ') continue;
            if (c == '+' || c == '(') op.push(c);
            else if(c == '-')
            {
                if(is_neg) num.push(0);
                op.push(c);
            }
            else if (c == ')') {
                op.pop();
                if (op.size() && op.top() != '(') {
                    calc(op, num);
                }
            }
            else {
                int j = i;
                while (j < s.size() && isdigit(s[j])) j ++ ;
                num.push(atoi(s.substr(i, j - i).c_str()));
                i = j - 1;
                if (op.size() && op.top() != '(') {
                    calc(op, num);
                }
            }
            if(c=='(') is_neg = true;
            else is_neg = false;
        }
        return num.top();
    }
};

这波是肉蛋葱鸡 2022-02-08 17:11

如果读到了负号含义的-，补一个0在操作数中即可，其余时候不需要额外操作

jiashenz 2021-07-08 09:40

leetcode加测试了，y总的代码现在过不了

哈哈哈哈_0 2021-07-05 21:09

目前我没看到一个能完整过的，

哈哈哈哈_0 2021-07-05 21:04

现在最新的模版是什么

BlueLobster 2021-06-02 00:33

感觉新加的test case有捣乱之嫌，就是在正数前面加+

jiashenz 2021-12-22 13:07

在正数前面加‘-’吧

小松鼠1996 2021-04-03 16:11

LeetCode上增加了测试样例，对y总的代码稍微改动一下就可以通过了。

class Solution {
public:
    stack<int> op;
    stack<int> nums;

    int calculate(string s) {
        if (s[0] == '+' || s[0] == '-') s = "0" + s;
        int n = s.length();
        for (int i = 0; i < n; i++) {
            if (isdigit(s[i])) {
                int x = 0, j = i;
                while (j < n && isdigit(s[j])) {
                    x = x * 10 + (s[j++] - '0');
                }
                nums.push(x);
                i = j - 1;
            } else if (s[i] == '(') {
                op.push(s[i]);
            } else if (s[i] == ')') {
                while (op.top() != '(') {
                    eval();
                }
                op.pop();
            } else if (is_operator(s[i]) && s[i - 1] != '(' && s[i - 1] != '+' && s[i - 1] != '-') {
                while (!op.empty() && op.top() != '(') {
                    eval();
                }
                op.push(s[i]);
            } else if (is_operator(s[i]) && (is_operator(s[i - 1]) || s[i - 1] == '(')) {
                int x = 0, j = i + 1;
                while (j < n && isdigit(s[j])) {
                    x = x * 10 + (s[j++] - '0');
                }
                i = j - 1;
                if (s[i - 1] == '-') {
                    x = -x;
                }
                nums.push(x);
            }
        }
        while (!op.empty()) eval();
        return nums.top();
    }

    bool is_operator(char c) {
        return c == '+' || c == '-';
    }

    void eval() {
        int b = nums.top();
        nums.pop();
        int a = nums.top();
        nums.pop();
        int c = op.top();
        op.pop();
        switch (c) {
            case '+':
                nums.push(a + b);
                break;
            case '-':
                nums.push(a - b);
                break;
            default:
                break;
        }
    }
};

Gianni 2021-03-10 12:00

leetcode上的测试数据加强了，需要在压入运算符前判断有没有操作数，如果没有，要压入0
比如有一个测试数据是"-2+ 1"

class Solution {
public:
    int calculate(string s) {
        stack<int> nums;
        stack<char> ops;
        for (int i = 0; i < s.size(); ++i) {
            char c = s[i];
            if (c == ' ')
                continue;
            else if (isdigit(c)) {
                int x = 0, j = i;
                while (j < s.size() && isdigit(s[j]))
                    x = x * 10 + (s[j++] - '0');
                nums.push(x);
                i = j - 1;
            }
            else if (c == '(')
                ops.push(c);
            else if (c == ')') {
                while (ops.top() != '(')
                    eval(nums, ops);
                ops.pop();
            } else {
                while (!ops.empty() && ops.top() != '(')
                    eval(nums, ops);
                if (nums.empty())
                    nums.push(0);
                ops.push(c);
            }
        }
        while (!ops.empty())
            eval(nums, ops);
        return nums.top();
    }

    void eval(stack<int>& nums, stack<char>& ops) {
        int a = nums.top();
        nums.pop();
        int b = nums.top();
        nums.pop();
        char op = ops.top();
        ops.pop();
        if (op == '+')
            nums.push(a + b);
        else if (op == '-')
            nums.push(b - a);
    }
};

Gianni 2021-03-10 12:04

或者不用判断，上来初始化数值栈的时候先压入一个0，反正这道题只有加减运算，0不影响

skye_zou 2021-03-20 10:57 回复了 Gianni 的评论

有如下例子
$1-(+1+1)$

BlueLobster 2021-06-02 00:32 回复了 skye_zou 的评论

else if(c == '(') {
                op.push(c);
                if(!Character.isDigit(s.charAt(i + 1))) {
                    num.push(0);
                }
            }

如果( 后面不是数字的话，那么有几个运算符就要加上几个0。
但是目前的case只有多一个运算符，最多加一个0