Question

Formatted question description: https://leetcode.ca/all/224.html

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 * 10⁵
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.

Algorithm

The title restricts the expressions with only plus and minus signs, numbers, parentheses and spaces, and there is no multiplication and division, so there is no priority of calculation.

A stack is needed to assist the calculation, and a variable sign is used to represent the current symbol.

We traverse the given string s,

If you encounter a number, because it may be a multi-digit number, we need to use a while loop to read all the subsequent numbers in, and then use sign*num to update the result res;
If a plus sign is encountered, sign is assigned to 1, and if a minus sign is encountered, it is assigned to -1;
If a left parenthesis is encountered, push the current result res and sign onto the stack, reset res to 0 and reset to 1;
If the closing parenthesis is encountered, the result res is multiplied by the symbol on the top of the stack, the top element of the stack is popped, and the result is res plus the number on the top of the stack, and the top element of the stack is popped.

Code

import java.util.Stack;

public class Basic_Calculator {

    class Solution {
        public int calculate(String s) {
            int res = 0;
            int num = 0;
            int sign = 1;
            int n = s.length();

            Stack<Integer> sk = new Stack<>();

            for (int i = 0; i < n; ++i) {
                char c = s.charAt(i);
                if (c >= '0') {
                    num = 10 * num + (c - '0');
                } else if (c == '+' || c == '-') {
                    res += sign * num; // possible overflow, eg. -1 * Integer.MIN_VALUE
                    num = 0;
                    sign = (c == '+') ? 1 : -1;
                } else if (c == '(') {
                    sk.push(res); // not c-'0'
                    sk.push(sign);
                    res = 0;
                    sign = 1;
                    num = 0; // this line can be removed, here for clarity, since it's set to 0 when hitting operator +/-
                } else if (c == ')') {
                    res += sign * num;
                    num = 0;
                    res *= sk.peek(); sk.pop(); // sign @note: can be replaced by just `-1*val`
                    res += sk.peek(); sk.pop(); // then previous result
                }
            }
            res += sign * num; // @note: final check, if no ')' to trigger stack pop stuff
            return res;
        }

    }
}

############

class Solution {
    public int calculate(String s) {
        char[] cs = s.toCharArray();
        Deque<Character> op = new ArrayDeque<>();
        Deque<Integer> num = new ArrayDeque<>();
        for (int i = 0; i < cs.length; ++i) {
            if (cs[i] == '(' || cs[i] == '+' || cs[i] == '-') {
                op.push(cs[i]);
            } else if (cs[i] == ')') {
                op.pop();
                if (!op.isEmpty() && op.peek() != '(') {
                    calc(op, num);
                }
            } else if (Character.isDigit(cs[i])) {
                int j = i;
                int k = 0;
                while (j < cs.length && Character.isDigit(cs[j])) {
                    k = k * 10 + cs[j] - '0';
                    ++j;
                }
                num.push(k);
                i = j - 1;
                if (!op.isEmpty() && op.peek() != '(') {
                    calc(op, num);
                }
            }
        }
        return num.peek();
    }

    private void calc(Deque<Character> op, Deque<Integer> num) {
        int y = num.pop();
        int x = num.pop();
        if (op.pop() == '+') {
            num.push(x + y);
        } else {
            num.push(x - y);
        }
    }
}

// OJ: https://leetcode.com/problems/basic-calculator/
// Time: O(N)
// Space: O(N)
class Solution {
    vector<string> tokenize(string &s) {
        vector<string> ans;
        for (int i = 0, N = s.size(); i < N; ) {
            while (i < N && s[i] == ' ') ++i;
            if (i >= N) break;
            if (isdigit(s[i])) {
                int j = i;
                while (i < N && isdigit(s[i])) ++i;
                ans.push_back(s.substr(j, i - j));
            } else ans.push_back(s.substr(i++, 1));
        }
        return ans;
    }
    vector<string> toRpn(vector<string> tokens) {
        vector<string> ans;
        stack<string> ops;
        for (auto &s : tokens) {
            switch (s[0]) {
                case '(': ops.push(s); break;
                case ')':
                    while (ops.top() != "(") {
                        ans.push_back(ops.top());
                        ops.pop();
                    }
                    ops.pop();
                    break;
                case '+': 
                case '-':
                    if (ops.size() && (ops.top() == "+" || ops.top() == "-")) {
                        ans.push_back(ops.top());
                        ops.pop();
                    }
                    ops.push(s);
                    break;
                default: ans.push_back(s); break;
            }
        }
        while (ops.size()) {
            ans.push_back(ops.top());
            ops.pop();
        }
        return ans;
    }
    int calc(vector<string> rpn) {
        stack<int> s;
        for (auto &t : rpn) {
            switch (t[0]) {
                case '+':
                case '-': {
                    int b = s.top();
                    s.pop();
                    s.top() += t == "+" ? b : -b;
                    break;
                }
                default: s.push(stoi(t)); break;
            }
        }
        return s.top();
    }
public:
    int calculate(string s) {
        return calc(toRpn(tokenize(s)));
    }
};

# only + and - , no * , no / 
class Solution:
  def calculate(self, s: str) -> int:
    ans = 0
    num = 0
    sign = 1
    stack = [sign]  # stack[-1]: current env's sign

    for c in s:
      if c.isdigit():
        num = num * 10 + int(c)
        # num = num * 10 + (ord(c) - ord('0')) => also works
      elif c == '(':
        stack.append(sign)
      elif c == ')':
        stack.pop() # pop pairing sign for this () pair
      elif c == '+' or c == '-':
        ans += sign * num
        sign = (1 if c == '+' else -1) * stack[-1] # after all + or -, the sign for current num
        num = 0

    return ans + sign * num # final calculation

#############

class Solution(object):
  def calculate(self, s):
    """
    :type s: str
    :rtype: int
    """
    s = "(" + s + ")"
    stack = []
    _stack = []
    i = 0
    while i < len(s):
      if s[i] == " ":
        i += 1
      elif s[i] == "(":
        _stack.append(len(stack))
        i += 1
      elif s[i] == ")":
        start = _stack.pop()
        j = start
        a = stack[j]
        while j + 2 < len(stack):
          ops = stack[j + 1]
          if ops == "+":
            a = a + stack[j + 2]
          elif ops == "-":
            a = a - stack[j + 2]
          else:
            return "invalid"
          j += 2
        k = len(stack) - start
        while k > 0:
          stack.pop()
          k -= 1
        stack.append(a)
        i += 1
      elif s[i] in "+-":
        stack.append(s[i])
        i += 1
      else:
        start = i
        while i < len(s) and s[i] not in "-+() ":
          i += 1
        num = int(s[start:i])
        stack.append(num)
    return stack[0]

using System.Collections.Generic;

public class Solution {
    public int Calculate(string s) {
        var numbers = new Stack<int>();
        var symbols = new Stack<char>();
        int number = -1;
        for (var i = 0; i <= s.Length; ++i)
        {
            var ch = i < s.Length ? s[i] : ' ';
            if (char.IsDigit(ch))
            {
                if (number == -1) number = 0;
                number = number * 10 + ch - '0';
            }
            else
            {
                if (number != -1)
                {
                    numbers.Push(number);
                    while (symbols.Count > 0 && symbols.Peek() != '(')
                    {
                        var symbol = symbols.Pop();
                        if (symbol == '+')
                        {
                            numbers.Push(numbers.Pop() + numbers.Pop());
                        }
                        else
                        {
                            numbers.Push(-(numbers.Pop() - numbers.Pop()));
                        }
                    }
                    number = -1;
                }
                if (char.IsWhiteSpace(ch)) continue;

                if (ch == ')')
                {
                    symbols.Pop();
                    while (symbols.Count > 0 && symbols.Peek() != '(')
                    {
                        var symbol = symbols.Pop();
                        if (symbol == '+')
                        {
                            numbers.Push(numbers.Pop() + numbers.Pop());
                        }
                        else
                        {
                            numbers.Push(-(numbers.Pop() - numbers.Pop()));
                        }
                    }
                }
                else
                {
                    symbols.Push(ch);
                }
            }
        }

        return numbers.Pop();
    }
}

func calculate(s string) (ans int) {
	stk := []int{}
	sign := 1
	n := len(s)
	for i := 0; i < n; i++ {
		switch s[i] {
		case ' ':
		case '+':
			sign = 1
		case '-':
			sign = -1
		case '(':
			stk = append(stk, ans)
			stk = append(stk, sign)
			ans, sign = 0, 1
		case ')':
			ans *= stk[len(stk)-1]
			stk = stk[:len(stk)-1]
			ans += stk[len(stk)-1]
			stk = stk[:len(stk)-1]
		default:
			x := 0
			j := i
			for ; j < n && '0' <= s[j] && s[j] <= '9'; j++ {
				x = x*10 + int(s[j]-'0')
			}
			ans += sign * x
			i = j - 1
		}
	}
	return
}

function calculate(s: string): number {
    const stk: number[] = [];
    let sign = 1;
    let ans = 0;
    const n = s.length;
    for (let i = 0; i < n; ++i) {
        if (s[i] === ' ') {
            continue;
        }
        if (s[i] === '+') {
            sign = 1;
        } else if (s[i] === '-') {
            sign = -1;
        } else if (s[i] === '(') {
            stk.push(ans);
            stk.push(sign);
            ans = 0;
            sign = 1;
        } else if (s[i] === ')') {
            ans *= stk.pop() as number;
            ans += stk.pop() as number;
        } else {
            let x = 0;
            let j = i;
            for (; j < n && !isNaN(Number(s[j])) && s[j] !== ' '; ++j) {
                x = x * 10 + (s[j].charCodeAt(0) - '0'.charCodeAt(0));
            }
            ans += sign * x;
            i = j - 1;
        }
    }
    return ans;
}

224 - Basic Calculator

Question

Algorithm

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

Code

All Problems

All Solutions