227 Basic Calculator II 基本计算器 II

Description:
Implement a basic calculator to evaluate a simple expression string.

The expression string contains only non-negative integers, +, -, *, / operators and empty spaces . The integer division should truncate toward zero.

Example:

Example 1:

Input: "3+2*2"
Output: 7

Example 2:

Input: " 3/2 "
Output: 1

Example 3:

Input: " 3+5 / 2 "
Output: 5

Note:

You may assume that the given expression is always valid.
Do not use the eval built-in library function.

题目描述:
实现一个基本的计算器来计算一个简单的字符串表达式的值。

字符串表达式仅包含非负整数，+， - ，*，/ 四种运算符和空格 。 整数除法仅保留整数部分。

示例 :

示例 1:

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

示例 2:

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

示例 3:

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

说明：

你可以假设所给定的表达式都是有效的。
请不要使用内置的库函数 eval。

思路:

用栈记录运算结果
可以给运算式最开始添加一个 '+'号
遇到 '+'就将数加入到栈, 遇到 ‘-’就加入相反数
遇到 '*'或 '/'就将栈顶拿出来进行运算
时间复杂度O(n), 空间复杂度O(n)

代码:
C++:

class Solution 
{
public:
    int calculate(string s) 
    {
        int cur = 0, sign = (int)'+';
        vector<int> nums;
        for (int i = 0; i < s.length(); i++)
        {
            if (s[i] >= '0') cur = 10 * cur - '0' + s[i];
            if ((s[i] < '0' and s[i] != ' ') or i == s.size() - 1)
            {
                if (sign == '+') nums.push_back(cur);
                else if (sign == '-') nums.push_back(-cur);
                else if (sign == '/' or sign == '*') nums[nums.size() - 1] = sign == '*' ? nums[nums.size() - 1] * cur : nums[nums.size() - 1] / cur;
                sign = s[i];
                cur = 0;
            }
        }
        return accumulate(nums.begin(), nums.end(), 0);
    }
};

Java:

class Solution {
    public int calculate(String s) {
        int result = 0, cur = 0, sign = '+';
        List<Integer> nums = new ArrayList<>();
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) >= '0') cur = 10 * cur - '0' + s.charAt(i);
            if ((s.charAt(i) < '0' && s.charAt(i) != ' ') || i == s.length() - 1) {
                if (sign == '+') nums.add(cur);
                else if (sign == '-') nums.add(-cur);
                else if (sign == '/' || sign == '*') nums.set(nums.size() - 1, sign == '*' ? nums.get(nums.size() - 1) * cur : nums.get(nums.size() - 1) / cur);
                sign = s.charAt(i);
                cur = 0;
            }
        }
        for (int num : nums) result += num;
        return result;
    }
}

Python:

class Solution:
    def calculate(self, s: str) -> int:
        return eval(s.replace('/', '//'))