Welcome to Subscribe On Youtube

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

772. Basic Calculator III

Level

Hard

Description

Implement a basic calculator to evaluate a simple expression string.

The expression string contains only non-negative integers, '+', '-', '*', '/' operators, and open '(' and closing parentheses ')'. The integer division should truncate toward zero.

You may assume that the given expression is always valid. All intermediate results will be in the range of [-231, 231 - 1].

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 = "6-4/2"
Output: 4

Example 3:

Input: s = "2*(5+5*2)/3+(6/2+8)"
Output: 21

 

Constraints:

  • 1 <= s <= 104
  • s consists of digits, '+', '-', '*', '/', '(', and ')'.
  • s is a valid expression.

Solution

The expression may include integers, addition (+), subtraction (-), multiplication (*), division (/), and parentheses to dictate the order of operations. The approach uses Depth-First Search (DFS) recursion to handle the computation, particularly for expressions within parentheses. Here’s a breakdown of how the code operates:

Main Function: calculate

  • Variables Initialization: A stack to store intermediate results, num to accumulate numeric values, and op to hold the current operation (initialized to + for the first number).

  • Iteration: The function iterates through each character c in the input string s, using i as the index.

    • Number Parsing: If c is a digit, it updates num to include this digit (accounting for multi-digit numbers).

    • Handling Parentheses: If c is "(", it finds the corresponding closing parenthesis using findClosing and recursively calculates the value of the expression inside the parentheses. i is updated to the index of the closing parenthesis to skip the evaluated expression.

    • Applying Operations: When an operation character ("+-*/") is encountered or the end of the string is reached (i == len(s) - 1), the code applies the previous operation (op) to the current num and the top of the stack if necessary. The current operation c is stored in op, and num is reset to 0 for the next number.

  • Stack Summation: After processing all characters, the function sums up the values in the stack. This sum represents the final result since the stack accumulates all partial results adjusted by their respective operations.

Helper Function: findClosing

  • This function finds the index of the closing parenthesis corresponding to the opening parenthesis at index i. It uses a level variable to handle nested parentheses by incrementing level for each opening parenthesis and decrementing it for each closing parenthesis. When level returns to 0, it means the corresponding closing parenthesis is found.

Example

Given the expression s = "1 + (2 - (2 + 3) * 4 / (1 + 1)) * 2", the code correctly calculates its value by:

  • Parsing numbers and operations at the top level.
  • Recursively evaluating expressions inside parentheses.
  • Applying the operations to the accumulated numbers and using the stack to manage intermediate results.

Let’s walk through the evaluation step by step, focusing on the recursion invoked by the parentheses.

Initial Setup

  • Start with s, an empty stack, num = 0, and op = "+".

First Level of Calculation

  • Iterate through s. The first non-whitespace character is "1", which is a digit, so num = 1.
  • Encounter " + ". Since op is "+", push 1 onto the stack.
  • Next, encounter "(" which indicates the start of a sub-expression. Find the corresponding closing parenthesis and recursively calculate the expression inside "(2 - (2 + 3) * 4 / (1 + 1))".

First Recursion: "2 - (2 + 3) * 4 / (1 + 1)"

  • Reset: num = 0, op = "+", and a new stack.
  • Parse "2", encounter " - ", push 2 onto the stack.
  • Encounter another "(", indicating a nested sub-expression. Recursively calculate the expression inside "(2 + 3)".

Second Recursion: "2 + 3"

  • Reset: num = 0, op = "+", and a new stack.
  • Parse "2", then " + ", push 2 onto the stack.
  • Parse "3", and since we reach the end, use op to add 3 to the stack.
  • Sum the stack: 2 + 3 = 5. Return 5 to the first recursion.

Back to First Recursion with 5 from Second Recursion

  • After replacing "(2 + 3)" with 5, the expression becomes "2 - 5 * 4 / (1 + 1)".
  • Continue parsing: " - 5" results in pushing -5 onto the stack (because of the previous op = "-").
  • Parse " * 4", update op to "*", and keep num = 4.
  • Encounter "(" again, so calculate the expression inside "(1 + 1)".

Third Recursion: "1 + 1"

  • Reset: num = 0, op = "+", and a new stack.
  • Parse "1", encounter " + ", push 1 onto the stack.
  • Parse "1", and since we reach the end, use op to add 1 to the stack.
  • Sum the stack: 1 + 1 = 2. Return 2 to the first recursion.

Continue First Recursion with 2 from Third Recursion

  • After replacing "(1 + 1)" with 2, the expression becomes "2 - 5 * 4 / 2".
  • Continue parsing: "/ 2" updates op to "/" and sets num = 2.
  • Perform the multiplication and division with the stack: 2 - (5 * 4) / 2 = 2 - 10 = -8.
  • Return -8 to the initial level of calculation.

Final Steps

  • Replace the original sub-expression with -8, making the initial expression "1 + -8 * 2".
  • Calculate the final result: 1 + (-8 * 2) = 1 - 16 = -15.
  • public class Basic_Calculator_III {


    // ref: http://buttercola.blogspot.com/2019/03/leetcode-772-basic-calculator-iii.html
    class Solution {
        public int calculate(String s) {
            if (s == null || s.length() == 0) {
                return 0;
            }

            // remove leading and trailing spaces and white spaces.
            //
            s = s.trim().replaceAll("[ ]+", "");

            if (s == null || s.length() == 0) {
                return 0;
            }

            Stack<Character> opStack = new Stack<>();
            Stack<Integer> numStack = new Stack<>();

            int i = 0;
            while (i < s.length()) {
                if (Character.isDigit(s.charAt(i))) {
                    int num = 0;
                    while (i < s.length() && Character.isDigit(s.charAt(i))) {
                        num = num * 10 + Character.getNumericValue(s.charAt(i));
                        i++;
                    }
                    numStack.push(num);
                } else {
                    char op = s.charAt(i);
                    if (opStack.isEmpty()) {
                        opStack.push(op);
                        i++;
                    } else if (op == '+' || op == '-') {
                        char top = opStack.peek();
                        if (top == '(') {
                            opStack.push(op);
                            i++;
                        } else {
                            calculate(numStack, opStack);
                        }
                    } else if (op == '*' || op == '/') {
                        char top = opStack.peek();
                        if (top == '(') {
                            opStack.push(op);
                            i++;
                        } else if (top == '*' || top == '/') {
                            calculate(numStack, opStack);
                        } else if (top == '+' || top == '-') {
                            opStack.push(op);
                            i++;
                        }
                    } else if (op == '(') {
                        opStack.push(op);
                        i++;
                    } else if (op == ')') {
                        while (opStack.peek() != '(') {
                            calculate(numStack, opStack);
                        }
                        opStack.pop();
                        i++;
                    }
                }
            }

            while (!opStack.isEmpty()) {
                calculate(numStack, opStack);
            }

            return numStack.peek();
        }

        private void calculate(Stack<Integer> numStack, Stack<Character> opStack) {
            int num2 = numStack.pop();
            int num1 = numStack.pop();

            char op = opStack.pop();

            int ans = 0;

            switch(op) {
                case '+':
                    ans = num1 + num2;
                    break;
                case '-':
                    ans = num1 - num2;
                    break;
                case '*':
                    ans = num1 * num2;
                    break;
                case '/':
                    ans = num1 / num2;
                    break;
            }

            numStack.push(ans);
        }
    }
}

  • // OJ: https://leetcode.com/problems/basic-calculator-iii/
// Time: O(N)
// Space: O(N)
class Solution {
    stack<long> num;
    stack<char> op;
    unordered_map<char, int> priority{ {'+', 1}, {'-', 1}, {'*', 2}, {'/', 2} };
    void eval() {
        long b = num.top(); num.pop();
        char c = op.top(); op.pop();
        switch (c) {
            case '+': num.top() += b; break;
            case '-': num.top() -= b; break;
            case '*': num.top() *= b; break;
            case '/': num.top() /= b; break;
        }
    }
public:
    int calculate(string s) {
        for (int i = 0, N = s.size(); i < N; ++i) {
            if (s[i] == ' ') continue;
            if (isdigit(s[i])) {
                long n = 0;
                while (i < N && isdigit(s[i])) n = n * 10 + s[i++] - '0';
                --i;
                num.push(n);
            } else if (s[i] == '(') op.push(s[i]);
            else if (s[i] == ')') {
                while (op.top() != '(') eval();
                op.pop();
            } else {
                while (op.size() && op.top() != '(' && priority[op.top()] >= priority[s[i]]) eval();
                op.push(s[i]);
            }
        }
        while (op.size()) eval();
        return num.top();
    }
};

  • # good one, based on solution of Basic Calculator II
class Solution: # dfs recursion
    def calculate(self, s: str) -> int:
        stack = []
        num = 0
        op = "+"
        i = 0
        while i < len(s):
            c = s[i]
            if c.isdigit():
                num = num * 10 + int(c)
            elif c == "(":
                j = self.findClosing(s, i)
                num = self.calculate(s[i+1:j]) # j is ')'
                i = j # out if, i will +1 below
            if c in "+-*/" or i == len(s) - 1:
                if op == "+":
                    stack.append(num)
                elif op == "-":
                    stack.append(-num)
                elif op == "*":
                    stack[-1] *= num
                else:
                    stack[-1] = int(stack[-1] / num)
                op = c
                num = 0
            i += 1
        return sum(stack)

    def findClosing(self, s: str, i: int) -> int:
        level = 0
        while i < len(s):
            if s[i] == "(":
                level += 1
            elif s[i] == ")":
                level -= 1
                if level == 0:
                    return i
            i += 1
        return i


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


class Solution: # iterative
    def calculate(self, s: str) -> int:
        def evaluate_expression(stack):
            res = stack.pop() if stack else 0
            # Evaluate the expression till we get '(' or empty stack
            while stack and stack[-1] != '(':
                sign = stack.pop()
                if sign == '+':
                    res += stack.pop()
                elif sign == '-':
                    res -= stack.pop()
                elif sign == '*':
                    res *= stack.pop()
                elif sign == '/':
                    res //= stack.pop()
            return res

        stack = [] # mix of num and operator
        n = len(s)
        i = 0
        while i < n:
            if s[i].isdigit():
                # Get the complete number and push it to the stack
                j = i
                while j < n and s[j].isdigit():
                    j += 1
                stack.append(int(s[i:j]))
                i = j - 1
            elif s[i] in '+-*/(':
                stack.append(s[i])
            elif s[i] == ')':
                # Evaluate the expression within the parentheses
                res = evaluate_expression(stack)
                stack.pop()  # Remove the opening '('
                stack.append(res)
            i += 1

        return evaluate_expression(stack)


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

class Solution:
    def calculate(self, s: str) -> int:
        if not s:
            return 0

        # remove leading and trailing spaces and white spaces.
        s = s.strip().replace(" ", "")

        if not s:
            return 0

        op_stack = []
        num_stack = []

        i = 0
        while i < len(s):
            if s[i].isdigit():
                num = 0
                while i < len(s) and s[i].isdigit():
                    num = num * 10 + int(s[i])
                    i += 1
                num_stack.append(num)
            else:
                op = s[i]
                if not op_stack:
                    op_stack.append(op)
                    i += 1
                elif op == '+' or op == '-':
                    top = op_stack[-1]
                    if top == '(':
                        op_stack.append(op)
                        i += 1
                    else:
                        self.calculate_helper(num_stack, op_stack)
                elif op == '*' or op == '/':
                    top = op_stack[-1]
                    if top == '(' or top == '+' or top == '-':
                        op_stack.append(op)
                        i += 1
                    else:
                        self.calculate_helper(num_stack, op_stack)
                elif op == '(':
                    op_stack.append(op)
                    i += 1
                elif op == ')':
                    while op_stack[-1] != '(':
                        self.calculate_helper(num_stack, op_stack)
                    op_stack.pop()
                    i += 1

        while op_stack:
            self.calculate_helper(num_stack, op_stack)

        return num_stack[-1]

    def calculate_helper(self, num_stack, op_stack):
        num2 = num_stack.pop()
        num1 = num_stack.pop()

        op = op_stack.pop()

        if op == '+':
            ans = num1 + num2
        elif op == '-':
            ans = num1 - num2
        elif op == '*':
            ans = num1 * num2
        else:
            ans = int(num1 / num2)

        num_stack.append(ans)

All Problems

All Solutions