Description
Given a string s which represents an expression, evaluate this expression and return its value.
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().
Examples:
Example 1:
Input: s = "3+2*2"
Output: 7
Example 2:
Input: s = " 3/2 "
Output: 1
Example 3:
Input: s = " 3+5 / 2 "
Output: 5Solution in Python
Python
class Solution:
def calculate(self, s: str) -> int:
# Initialize a stack to keep track of numbers and intermediate results
stack = []
# Initialize variables to keep track of the current number and operator
current_number = 0
# The previous operator starts as '+', assuming the first number is positive
previous_operator = '+'
# We iterate through each character in the expression
for i, char in enumerate(s):
# If the current character is a digit, we build the current number
if char.isdigit():
current_number = current_number * 10 + int(char)
# If the current character is an operator or the last character in the string
if char in "+-*/" or i == len(s) - 1:
# Process the previous operator:
if previous_operator == '+':
# Add the current number to the stack for addition
stack.append(current_number)
elif previous_operator == '-':
# Subtract by adding the negative of the current number
stack.append(-current_number)
elif previous_operator == '*':
# Multiply the top of the stack with the current number
stack.append(stack.pop() * current_number)
elif previous_operator == '/':
# Perform integer division (truncated toward zero)
# We need to handle both positive and negative division results
stack.append(int(stack.pop() / current_number))
# Update the operator to the current one and reset the current number
previous_operator = char
current_number = 0
# Sum all the numbers in the stack to get the final result
return sum(stack)Explanation
- Stack-based approach: We use a stack to store numbers and handle the intermediate results of multiplication and division. This helps us prioritize operations correctly.
- Iteration over the string: We loop through the string character by character. If we encounter digits, we construct the number, and if we encounter an operator or reach the end of the string, we apply the last operator to the current number.
- Operators:
- For
+, the current number is added to the stack. - For
-, the negative of the current number is added to the stack. - For
*, we pop the last number from the stack, multiply it with the current number, and push the result back. - For
/, we pop the last number, divide it by the current number (truncated towards zero), and push the result back.
- For
- Final result: Once the iteration is complete, we sum all the numbers in the stack, which gives the final result.
Edge Handling
- The function handles spaces between numbers and operators.
- It also ensures that division is correctly truncated towards zero, which is important for Python’s behavior with integer division.
This approach runs efficiently within the constraints, ensuring it processes the expression in linear time O(n).
Solution in Javascript
JavaScript
var calculate = function(s) {
// Initialize a stack to store numbers and intermediate results
let stack = [];
// Initialize a variable to track the current number being formed
let currentNumber = 0;
// The previous operator starts as '+', assuming the first number is positive
let previousOperator = '+';
// Iterate through each character in the string
for (let i = 0; i < s.length; i++) {
let char = s[i];
// If the current character is a digit, build the current number
if (!isNaN(char) && char !== ' ') {
currentNumber = currentNumber * 10 + parseInt(char);
}
// If the current character is an operator or we reached the end of the string
if (isNaN(char) && char !== ' ' || i === s.length - 1) {
// Process the previous operator:
if (previousOperator === '+') {
// Add the current number to the stack for addition
stack.push(currentNumber);
} else if (previousOperator === '-') {
// Subtract by adding the negative of the current number
stack.push(-currentNumber);
} else if (previousOperator === '*') {
// Multiply the top of the stack with the current number
stack.push(stack.pop() * currentNumber);
} else if (previousOperator === '/') {
// Perform integer division (truncated towards zero)
// Handle both positive and negative division
stack.push(Math.trunc(stack.pop() / currentNumber));
}
// Update the operator to the current one and reset the current number
previousOperator = char;
currentNumber = 0;
}
}
// Sum all the numbers in the stack to get the final result
return stack.reduce((a, b) => a + b, 0);
};Solution in Java
Java
class Solution {
public int calculate(String s) {
// Stack to store numbers and intermediate results
Stack<Integer> stack = new Stack<>();
// Variable to hold the current number being formed
int currentNumber = 0;
// Variable to hold the previous operator, initialized to '+' for the first number
char previousOperator = '+';
// Iterate over each character in the input string
for (int i = 0; i < s.length(); i++) {
char currentChar = s.charAt(i);
// If the current character is a digit, form the number
if (Character.isDigit(currentChar)) {
currentNumber = currentNumber * 10 + (currentChar - '0');
}
// If the current character is an operator or we reach the end of the string
if (!Character.isDigit(currentChar) && currentChar != ' ' || i == s.length() - 1) {
// Process the previous operator:
if (previousOperator == '+') {
// Add the current number to the stack
stack.push(currentNumber);
} else if (previousOperator == '-') {
// Subtract by pushing the negative of the current number
stack.push(-currentNumber);
} else if (previousOperator == '*') {
// Multiply the top of the stack by the current number
stack.push(stack.pop() * currentNumber);
} else if (previousOperator == '/') {
// Divide the top of the stack by the current number (integer division truncated toward zero)
stack.push(stack.pop() / currentNumber);
}
// Update the previous operator to the current character
previousOperator = currentChar;
// Reset the current number for the next part of the expression
currentNumber = 0;
}
}
// Sum up all the values in the stack to get the final result
int result = 0;
while (!stack.isEmpty()) {
result += stack.pop();
}
return result;
}
}Solution in C#
C#
public class Solution {
public int Calculate(string s) {
// Stack to store numbers and intermediate results
Stack<int> stack = new Stack<int>();
// Variable to store the current number being formed
int currentNumber = 0;
// Variable to store the previous operator, initialized to '+' for the first number
char previousOperator = '+';
// Iterate through each character in the string
for (int i = 0; i < s.Length; i++) {
char currentChar = s[i];
// If the current character is a digit, build the current number
if (char.IsDigit(currentChar)) {
currentNumber = currentNumber * 10 + (currentChar - '0');
}
// If the current character is an operator or it's the last character
if (!char.IsDigit(currentChar) && currentChar != ' ' || i == s.Length - 1) {
// Process the previous operator:
if (previousOperator == '+') {
// Add the current number to the stack
stack.Push(currentNumber);
} else if (previousOperator == '-') {
// Subtract by pushing the negative of the current number
stack.Push(-currentNumber);
} else if (previousOperator == '*') {
// Multiply the top of the stack with the current number
stack.Push(stack.Pop() * currentNumber);
} else if (previousOperator == '/') {
// Divide the top of the stack by the current number (integer division truncated towards zero)
stack.Push(stack.Pop() / currentNumber);
}
// Update the previous operator to the current character
previousOperator = currentChar;
// Reset the current number for the next part of the expression
currentNumber = 0;
}
}
// Sum up all the values in the stack to get the final result
int result = 0;
while (stack.Count > 0) {
result += stack.Pop();
}
return result;
}
}