In this Leetcode Basic Calculator problem solution, we have given a string s representing a valid expression, implement a basic calculator to evaluate it and return the result of the evaluation.

Leetcode Basic Calculator problem solution


Problem solution in Python.

class Solution:
    def calculate(self, s: str) -> int:
        res, num, stack, sign = 0, 0, [], '+'
        
        for i in range(len(s)):
            if '0'<=s[i]<='9':
                num = num*10 + ord(s[i]) - ord('0')
            if s[i] in '+-)' or i == len(s)-1:
                if sign == '+':
                    res += num
                else:
                    res += -num
                num = 0
                sign = s[i]
            if s[i] == '(':
                stack.append(res)
                stack.append(sign)
                sign = '+'
                res = 0
            elif s[i] == ')':
                sign = stack.pop()
                res1 = stack.pop()
                res = res+res1 if sign == '+' else res1-res
                num = 0
                sign = '+'
            # print(s[i],'---',num,'---',res, stack)
        return res



Problem solution in Java.

public int calculate(String s) {
        return helper(0, s, new int[1]);
    }
    private int helper(int start, String s, int[] nextPos){
        int pt = start, cur = 0, val = 0;
        int sign = 1;
        while(pt < s.length()){
            if(s.charAt(pt) == ' ') pt++;
            else if(s.charAt(pt) >= '0' && s.charAt(pt) <= '9')
                cur = cur * 10 + (s.charAt(pt++) - '0');
            else{
                val += sign * cur;
                cur = 0;
                if(s.charAt(pt) == '+'){
                    sign = 1;
                    pt++;
                }else if(s.charAt(pt) == '-'){
                    sign = -1;
                    pt++;
                }else if(s.charAt(pt) == '('){
                    val += sign * helper(pt+1, s, nextPos);
                    pt = nextPos[0];
                }else if(s.charAt(pt) == ')'){
                    nextPos[0] = pt+1;
                    return val;
                }
            }
        }
        val += sign * cur;
        return val;
    }


Problem solution in C++.

class Solution {
public:
    int calculate(string s) {
        stack<int> operand;
        stack<pair<int, bool>> stackSize;
        bool sign = true;
        int retVal = 0;
        int startIdx = 0;
        for (int i = 0; i <= s.length(); ++i) {
            if (i == s.length() || s[i] == ')') {
                int remainingSize = 0;
                bool localSign = true;
                if (!stackSize.empty()) {
                    remainingSize = stackSize.top().first;
                    localSign = stackSize.top().second;
                }
                int temp = 0;
                while (operand.size() != remainingSize) {
                    temp += operand.top();
                    operand.pop();
                }
                if (localSign == false) {
                    temp *= -1;
                }
                if (i != s.length()) operand.push(temp);
                else retVal = temp;
                stackSize.pop();
            } else if (s[i] == '(') {
                stackSize.push({operand.size(), sign});
                sign = true;
            } else if (s[i] >= '0' && s[i] <= '9') {
                if (i > 0 && !(s[i - 1] >= '0' && s[i - 1] <= '9')) {
                    startIdx = i;
                }  
                if (i == s.length() - 1 || !(s[i + 1] >= '0' && s[i + 1] <= '9')) {
                    int num = stoi(s.substr(startIdx, i - startIdx + 1));
                    if (!sign) num *= -1;
                    operand.push(num);
                }
            } else if (s[i] == '+') {
                sign = true;
            } else if (s[i] == '-') {
                sign = false;
            }
        }
        return retVal;
    }
};


Problem solution in C.

char*s;calculate(char*x){s=x;return e();}
void b(){while(*s==' ')s++;}
c(char*t){b();return strchr(t,*s)?*s++:0;}
i(){b();char*p=s;while(isdigit(*s)){s++;}char h=*s;*s=0;int r=atoi(p);*s=h;return r;}
p(){int r;if(c("(")){r=e();c(")");}else r=i();return r;}
u(){return c("-")?-p():p();}
e(){int o,r=u();while(o=c("+-")){if(o=='+')r+=u();else r-=u();}return r;}