224. Basic Calculator

Basic Calculator

Problem Description

Given a string s representing a valid expression, implement a basic calculator to evaluate it, and return the result of the evaluation.

Note: You are not allowed to use any built-in function which evaluates strings as mathematical expressions, such as eval().

 

Example 1:

Input: s = "1 + 1"
Output: 2

Example 2:

Input: s = " 2-1 + 2 "
Output: 3

Example 3:

Input: s = "(1+(4+5+2)-3)+(6+8)"
Output: 23

 

Constraints:

• 1 <= s.length <= 3 * 105
• s consists of digits, '+', '-', '(', ')', and ' '.
• s represents a valid expression.
• '+' is not used as a unary operation (i.e., "+1" and "+(2 + 3)" is invalid).
• '-' could be used as a unary operation (i.e., "-1" and "-(2 + 3)" is valid).
• There will be no two consecutive operators in the input.
• Every number and running calculation will fit in a signed 32-bit integer.

Approach) Recursion

/**
 * @param {string} s
 * @return {number}
 */
var calculate = function(s, i = 0, j = s.length) {
    if (!s) return 0;

    let total = 0;
    let sign = '+';

    while (i < j) {
        let number = null;

        switch (s[i]) {
            case ' ':
                i++;
                break;
            case '+':
            case '-':
                sign = s[i++];
                break;
            case '(':
                let open = 1;
                let k = i;

                while (open) {
                    k++;
                    if (s[k] === '(') open++;
                    if (s[k] === ')') open--;
                }
                
                number = calculate(s, i + 1, k);

                i = k + 1;

                break;
            default:
                number = 0;

                while (i < s.length && s[i].match(/[0-9]/)) number = (number * 10) + +s[i++];
        }
        
        if (number !== null) {
            total += sign === '-' ? -1 * number : number;
        }
    }

    return total;
};

Approach) Stack

Until ")" of stringS appears, always push s[i] into stack, when ")" appears, pop stack into temp until the last index of stack is "("
and reverse temp and then start counting.
some of cases like "-1+2" or "5+(+1+2)", will additional push zero into stack, like "0-1+2", "5+(0+1+2)"

var calculate = function(s) {
    s = "("+s+")"
    let stack = [];
    let temp = [];
    for(let i = 0; i < s.length; i++){
        if(s[i]===" ") continue;
        if(s[i]===")"){     
            while(stack[stack.length-1]!=="(") temp.push(stack.pop());                   
            stack.pop();
            stack.push(count(temp));
            continue;
        }
         if(isNum(stack[stack.length-1])&&isNum(s[i])){
            stack[stack.length-1]+=s[i];   
            continue;             
        } 
        if(s[i]==="-"||s[i]==="+"){
             if(stack.length===0||stack[stack.length-1]==="(") stack.push("0");    
        }
        stack.push(s[i]);
    }
    return stack[0];
};
    
function count(temp) {
 let res = Number(temp.pop());
 while(temp.length > 0) {
   let sign = temp.pop();
        if (sign === '+') {
            res  +=  Number(temp.pop());
        } else {
            res  -=  Number(temp.pop());
        }
  }  
    return res;
}
function isNum(str) {
  return /[0-9]+/.test(str);
}

Approach) RegExp

var calculate = function(s) {
    s = s.replace(/\s+/g, '');
    var reg = /\(([^\(\)]+)\)/g; 
    while( ~s.indexOf('(') ) {
        // extract the expression in parentheses as long as there is parentheses
        // then calculate the expression in parentheses and replace it
        s = s.replace(reg, function($0, $1) {
            return cal($1);
        })
    }
    return cal(s);
};

// pass an expression without parentheses
function cal(s) {
    var i = 0, l = s.length, c, cc, res = 0, tmp = '';
    while(i < l) {
        c = s.charAt(i);
        switch(c) {
            case '+':
                cc = s.charAt(i+1);
                res += +tmp;
                tmp = cc === '+' ? '' : cc;
                i += 2;
                break;
            case '-':
                cc = s.charAt(i+1);
                res += +tmp;
                tmp = cc === '+' ? '-' : cc === '-' ? '' : -cc;
                i += 2;
                break;
            default:
                tmp += c;
                i++;
        }
    }
    return res += +tmp;
}

Conclusion

That’s all folks! In this post, we solved LeetCode problem 224. Basic Calculator

I hope you have enjoyed this post. Feel free to share your thoughts on this.

You can find the complete source code on my GitHub repository. If you like what you learn. feel free to fork 🔪 and star ⭐ it.

In this blog, I have tried to collect & present the most important points to consider when improving Data structure and logic, feel free to add, edit, comment, or ask. For more information please reach me here
Happy coding!