In this Leetcode Basic Calculator II problem solution, we have given a string s which represents an expression, evaluate this expression, and return its value. 

  1. The integer division should truncate toward zero.
  2. You may assume that the given expression is always valid. All intermediate results will be in the range of [-231, 231 - 1].

leetcode basic calculator II problem solution


Problem solution in Python.

def calculate(self, s):
    s = s.replace(" ", "")
    pn = [1 if c=="+" else -1 for c in s if c in "+-"]
    sList = [self.cal(c) for c in s.replace("-", "+").split("+")]

    return sList[0] + sum([sList[i+1]*pn[i] for i in xrange(len(pn))])

    
def cal(self, s): # calculate the values of substrings "WITHOUT +-"
    if "*" not in s and "/" not in s:
        return int(s)

    md = [1 if c=="*" else -1 for c in s if c in "*/"]
    sList = [int(i) for i in s.replace("/", "*").split("*")]
    
    res, i = sList[0], 0
    while res != 0 and i < len(md):
        if md[i] == 1:
            res *= sList[i+1]
        else:
            res //= sList[i+1]
        i += 1
    return res



Problem solution in Java.

class Solution {
    public int calculate(String s) {
        Stack<Integer> stack=new Stack<>();
        int len=s.length();
        int num=0;
        int sign=1;
        char dm=' ';
        for(int i=0;i<len;i++){
            char c=s.charAt(i);
            if(Character.isDigit(c)){
                int temp=0;
                while(i<len && Character.isDigit(s.charAt(i))){
                    temp=temp*10+s.charAt(i)-'0';
                    i++;
                }
                i--;
                if(dm=='*')num=num*temp;
                else if(dm=='/')num=num/temp;
                else num=temp;
                dm=' ';
            }
            else if(c=='*') dm='*';
            else if(c=='/')dm='/';
            else if(c=='+'){stack.push(sign*num);sign=1;}
            else if(c=='-'){stack.push(sign*num);sign=-1;}
        }
        num*=sign;
        while(!stack.isEmpty()){
            num+=stack.pop();
        }
        return num;
    }
}


Problem solution in C++.

class Solution {
public:
    int calculate(string s) {
        char sign = '+';
        int val = 0;
        int ans;
        vector<int> stack;
        for (int i=0; i<s.size(); i++) {
            auto c = s[i];
            if (isdigit(c)) {
                val = 10 * val + (c-'0');
            }
            if (c == '+' || c == '-' || c == '*' || c == '/' || i == s.size()-1) {
                if (sign == '+') { stack.push_back(val); }
                if (sign == '-') { stack.push_back(-1 * val); }
                if (sign == '*') {
                    auto last = stack.back();
                    stack.pop_back();
                    stack.push_back(last * val);
                }
                if (sign == '/') {
                    auto last = stack.back();
                    stack.pop_back();
                    stack.push_back(last / val);
                }
                sign = c;
                val = 0;
            }
        }
        int sum = 0;
        for (auto num: stack) sum += num;
        return sum;
    }
};


Problem solution in C.

static bool     ft_expect_token(char **p, int const c)
{
    while (0 != isspace(**p))
        ++(*p);
    if (**p != c)
        return (false);
    ++(*p);
    return (true);
}

static int      ft_parse_digit(char **p)
{
    return (*(*p)++ - '0');
}

static int      ft_parse_number(char **p)
{
    int total;
    
    while (0 != isspace(**p))
        ++(*p);
    total = 0;
    while (0 != isdigit(**p))
        total = total * 10 + ft_parse_digit(p);
    return (total);
}

static int      ft_parse_factor(char **p)
{
    return (ft_parse_number(p));
}

static int      ft_parse_term(char **p)
{
    int     result;
    
    result = ft_parse_factor(p);
    while (true)
    {
        if (true == ft_expect_token(p, '*'))
            result *= ft_parse_factor(p);
        else if (true == ft_expect_token(p, '/'))
            result /= ft_parse_factor(p);
        else
            break ;
    }
    return (result);
}

static int      ft_parse_expression(char **p)
{
    int     result;
    
    if (true == ft_expect_token(p, '-'))
        result = -ft_parse_term(p);
    else
        result = ft_parse_term(p);
    while (true)
    {
        if (true == ft_expect_token(p, '+'))
            result += ft_parse_term(p);
        else if (true == ft_expect_token(p, '-'))
            result -= ft_parse_term(p);
        else
            break ;
    }
    return (result);
}

int calculate(char *s)
{
    return (ft_parse_expression(&s));
}