HomeLeetcode224. Basic Calculator - Leetcode Solutions
Leetcode

224. Basic Calculator – Leetcode Solutions

Declan Clarke

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().

Examples:

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

Solution in Python

Approach:

  1. Use a Stack for Parentheses:
    • We use a stack to handle sub-expressions within parentheses. Whenever we encounter a closing parenthesis, we calculate the value of the current expression and pop from the stack to continue calculating the outer expression.
  2. Sign Management:
    • We track the current sign (+ or -) to determine whether to add or subtract the current number from the total.
  3. Iterate Through the String:
    • As we iterate through the string:
      • If we encounter a digit, we build the number.
      • If we encounter a + or -, we update the total based on the current number and reset for the next number.
      • If we encounter a (, we push the current total and sign onto the stack and reset them for the sub-expression.
      • If we encounter a ), we compute the current sub-expression, then pop from the stack to resume the outer expression.
  4. Whitespace:
    • We skip over any whitespace characters.

Plan:

  1. Stack: To keep track of the total and the sign before encountering parentheses.
  2. Sign: This will be either +1 or -1, representing whether to add or subtract.
  3. Total: This will accumulate the result of the expression.

Time Complexity:

  • O(n) where n is the length of the input string. We go through each character exactly once.
Python
class Solution:
    def calculate(self, s: str) -> int:
        # Stack to keep track of the total and sign before parentheses
        stack = []
        
        # Initialize variables to keep track of current result and sign
        total = 0
        current_num = 0
        sign = 1  # 1 for positive, -1 for negative
        
        for char in s:
            if char.isdigit():
                # If the character is a digit, we build the current number
                current_num = current_num * 10 + int(char)
            elif char == '+':
                # Add the current number to the total, with the current sign
                total += sign * current_num
                # Update sign to positive for the next number
                sign = 1
                # Reset current number
                current_num = 0
            elif char == '-':
                # Add the current number to the total, with the current sign
                total += sign * current_num
                # Update sign to negative for the next number
                sign = -1
                # Reset current number
                current_num = 0
            elif char == '(':
                # Push the current total and sign onto the stack
                stack.append(total)
                stack.append(sign)
                # Reset total and sign for the new sub-expression
                total = 0
                sign = 1
            elif char == ')':
                # Add the current number to the total, with the current sign
                total += sign * current_num
                # Reset current number
                current_num = 0
                # Multiply the total inside the parentheses by the sign before the parentheses
                total *= stack.pop()  # The sign before '('
                # Add the total before the parentheses
                total += stack.pop()  # The total before '('
        
        # After the loop ends, add the last accumulated number
        total += sign * current_num
        return total

Detailed Explanation:

  1. Variables:
    • total: Keeps track of the running total.
    • current_num: The current number being formed by consecutive digits.
    • sign: Keeps track of the current sign (+ is 1, - is -1).
    • stack: Used to store the previous total and sign when encountering (.
  2. Handling Digits:
    • If the character is a digit, we append it to current_num. For multi-digit numbers, we multiply the existing number by 10 and add the new digit.
  3. Handling + and -:
    • When encountering + or -, we update the total by adding the current_num multiplied by the sign, reset current_num to 0, and update the sign for the next number.
  4. Handling Parentheses:
    • On encountering (, we push the current total and sign onto the stack, and reset total and sign to handle the sub-expression.
    • When ) is encountered, we calculate the sub-expression’s result, then pop the sign and previous total from the stack to resume the outer expression.
  5. Final Calculation:
    • After the loop, we add the last number to total.

Solution in Javascript

JavaScript
/**
 * @param {string} s
 * @return {number}
 */
var calculate = function(s) {
    // Stack to store the result and sign before encountering parentheses
    let stack = [];
    
    // Initialize variables for the current result, sign, and number
    let total = 0;
    let currentNum = 0;
    let sign = 1;  // 1 represents '+' and -1 represents '-'
    
    // Iterate over each character in the string
    for (let i = 0; i < s.length; i++) {
        let char = s[i];
        
        if (char >= '0' && char <= '9') {
            // If it's a digit, build the current number
            currentNum = currentNum * 10 + parseInt(char);
        } else if (char === '+') {
            // Add the current number to the total using the current sign
            total += sign * currentNum;
            // Reset currentNum for the next number and set sign to positive
            currentNum = 0;
            sign = 1;
        } else if (char === '-') {
            // Add the current number to the total using the current sign
            total += sign * currentNum;
            // Reset currentNum for the next number and set sign to negative
            currentNum = 0;
            sign = -1;
        } else if (char === '(') {
            // Push the current total and sign onto the stack
            stack.push(total);
            stack.push(sign);
            // Reset total and sign for the new sub-expression
            total = 0;
            sign = 1;
        } else if (char === ')') {
            // Add the current number to the total with the current sign
            total += sign * currentNum;
            // Reset currentNum
            currentNum = 0;
            // Pop the sign from the stack and multiply the total inside parentheses
            total *= stack.pop();  // The sign before '('
            // Add the total before parentheses
            total += stack.pop();  // The total before '('
        }
    }
    
    // At the end, add any remaining number to the total
    total += sign * currentNum;
    
    return total;
};

Solution in Java

Java
import java.util.Stack;

class Solution {
    public int calculate(String s) {
        // Stack to store the result and sign before parentheses
        Stack<Integer> stack = new Stack<>();
        
        // Initialize the variables for current result, number, and sign
        int total = 0;
        int currentNum = 0;
        int sign = 1; // 1 represents '+', -1 represents '-'
        
        // Iterate over each character in the string
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            
            if (Character.isDigit(c)) {
                // Build the current number (handle multiple digits)
                currentNum = currentNum * 10 + (c - '0');
            } else if (c == '+') {
                // Add the current number to the total, based on the sign
                total += sign * currentNum;
                // Update the sign to positive for the next number
                sign = 1;
                // Reset currentNum for the next number
                currentNum = 0;
            } else if (c == '-') {
                // Add the current number to the total, based on the sign
                total += sign * currentNum;
                // Update the sign to negative for the next number
                sign = -1;
                // Reset currentNum for the next number
                currentNum = 0;
            } else if (c == '(') {
                // Push the current total and sign onto the stack
                stack.push(total);
                stack.push(sign);
                // Reset total and sign for the new sub-expression
                total = 0;
                sign = 1;
            } else if (c == ')') {
                // Add the current number to the total
                total += sign * currentNum;
                // Reset currentNum
                currentNum = 0;
                // Pop the sign from the stack and multiply the total inside parentheses
                total *= stack.pop();  // The sign before '('
                // Add the total before parentheses
                total += stack.pop();  // The total before '('
            }
        }
        
        // Add the last number in case it was not added before
        total += sign * currentNum;
        
        return total;
    }
}

Solution in C#

C#
using System.Collections.Generic;

public class Solution {
    public int Calculate(string s) {
        // Stack to store the result and the sign before encountering parentheses
        Stack<int> stack = new Stack<int>();

        // Initialize variables for the current result, sign, and current number
        int total = 0;
        int currentNum = 0;
        int sign = 1; // 1 for '+', -1 for '-'

        // Iterate over each character in the string
        for (int i = 0; i < s.Length; i++) {
            char c = s[i];

            if (char.IsDigit(c)) {
                // Build the current number (for handling multiple digits)
                currentNum = currentNum * 10 + (c - '0');
            } 
            else if (c == '+') {
                // Add the current number to the total with the current sign
                total += sign * currentNum;
                // Set the sign for the next number
                sign = 1;
                // Reset currentNum for the next number
                currentNum = 0;
            } 
            else if (c == '-') {
                // Add the current number to the total with the current sign
                total += sign * currentNum;
                // Set the sign for the next number to negative
                sign = -1;
                // Reset currentNum for the next number
                currentNum = 0;
            } 
            else if (c == '(') {
                // Push the current total and sign onto the stack
                stack.Push(total);
                stack.Push(sign);
                // Reset total and sign for the new sub-expression
                total = 0;
                sign = 1;
            } 
            else if (c == ')') {
                // Add the current number to the total
                total += sign * currentNum;
                // Reset currentNum
                currentNum = 0;
                // Pop the sign and the total before parentheses
                total *= stack.Pop();  // Multiply the result by the sign before '('
                total += stack.Pop();  // Add the result before '('
            }
        }

        // Add the last number that may not have been added
        total += sign * currentNum;

        return total;
    }
}

Related Post

Subscribe
Notify of

0 Comments
Oldest
Newest Most Voted
Inline Feedbacks
View all comments

Popular

© 2024 Devexplain.com