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: 23Solution in Python
Approach:
- 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.
- Sign Management:
- We track the current sign (
+or-) to determine whether to add or subtract the current number from the total.
- We track the current sign (
- 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.
- As we iterate through the string:
- Whitespace:
- We skip over any whitespace characters.
Plan:
- Stack: To keep track of the total and the sign before encountering parentheses.
- Sign: This will be either
+1or-1, representing whether to add or subtract. - Total: This will accumulate the result of the expression.
Time Complexity:
- O(n) where
nis 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 totalDetailed Explanation:
- 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(.
- 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.
- If the character is a digit, we append it to
- Handling
+and-:- When encountering
+or-, we update thetotalby adding thecurrent_nummultiplied by thesign, resetcurrent_numto 0, and update thesignfor the next number.
- When encountering
- Handling Parentheses:
- On encountering
(, we push the currenttotalandsignonto the stack, and resettotalandsignto handle the sub-expression. - When
)is encountered, we calculate the sub-expression’s result, then pop thesignand previoustotalfrom the stack to resume the outer expression.
- On encountering
- Final Calculation:
- After the loop, we add the last number to
total.
- After the loop, we add the last number to
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;
}
}