227. Basic Calculator II
Problem Description
The problem requires us to evaluate a mathematical expression given as a string. The expression includes integers and the operators '+', '-', '*', and '/'. We need to process the expression and return the result as an integer. The division operation should truncate the result toward zero, meaning it should not result in any fractional part. We need to handle the expression correctly, keeping in mind the different precedence of the operators: multiplication and division have higher precedence over addition and subtraction.
All the numbers and the result of the computation are guaranteed to be within the range of a 32-bit signed integer. It is also worth noting that the given expression will be valid, so there is no need to handle any syntax errors.
Additionally, it is important to mention that we cannot use any built-in functions that can evaluate strings as mathematical expressions directly, such as the eval()
function in Python.
Intuition
To solve this problem, we need to implement an algorithm that can parse and evaluate the expression respecting the correct operator precedence. Since we can't use built-in evaluation functions, we have to simulate the calculation manually. One common approach to evaluating expressions is to use a stack.
Here’s the intuition behind using a stack in this solution:
- When we encounter a number, we store it for the next operation.
- When we encounter an operator, we decide what to do based on the previous operator.
- For '+' or '-', we need to add or subtract the number to/from our result. But since multiplication and division have higher precedence, we cannot directly add/subtract the number – we push it onto the stack.
- For '*' or '/', we immediately perform the operation with the previous number because they have higher precedence.
- Updating the current operator as we go allows us to know which operation to perform next.
To achieve the evaluation:
- We iterate over the string.
- We keep track of the current number and the last operator we have seen.
- When we see a new operator, we perform the necessary operation based on the last operator, which could mean pushing to the stack or popping from the stack, performing an operation, and then pushing back the result.
- At the end of the expression, we perform the operation for the last seen operator.
- Since all numbers and results are within the range of a signed 32-bit integer, we do not need to worry about overflow.
After traversing the entire string and performing all stack operations, the result of the expression will be the sum of all numbers present in the stack.
Solution Approach
The implementation follows these steps, making use of a stack and a variable to keep track of the current number (initially 0
) and another to remember the last operator (initially '+'
):
-
Initialize Variables: A stack
stk
is used to handle the numbers and the intermediate results. The variablev
is used to build the current number as we parse the string. Another variable,sign
, stores the last encountered operator, which is initially set to'+'
. -
Parse the String: The string
s
is parsed character by character using afor
loop. If the current characterc
is a digit, it's a part of the current numberv
. We updatev
by shifting the current value by one digit to the left (multiplying by 10) and adding the digit (v * 10 + int(c)
). -
Handle Operators and End of String: We need to perform an action whenever we encounter an operator or the end of the string (because the last number might not be followed by an operator). So we check if the character
c
is in '+-*/', or if it is the last character in the string (i == n - 1
). -
Perform Operations Based on Last Sign:
- If the last sign was
'+'
, push the current value ofv
onto the stack. - If it was
'-'
, push the negative ofv
onto the stack. - If it was
'*'
, pop the top value from the stack, multiply it byv
, and push the result back onto the stack. - If it was
'/'
, pop the top value from the stack, truncate divide it byv
, and push the result back onto the stack. This is achieved by usingint(stk.pop() / v)
which truncates towards zero in Python.
After processing the current number and operator,
sign
is updated to the current operatorc
, andv
is reset to0
to hold the next number. - If the last sign was
-
Evaluate the Stack: After the loop is finished, all values left in the stack are parts of the expression where addition and subtraction should be applied. As we pushed the results of multiplications and divisions and also considered the sign for addition and subtraction, simply summing all the values in the stack using
sum(stk)
gives us the final result.
The function finally returns the sum of all elements in the stack, which is the evaluated result of the given expression.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's walk through an example to illustrate the solution approach by evaluating the expression s = "3+5*2-4/2"
step by step.
-
Initialize Variables: We start by initializing our stack
stk
, our variablev
to0
, and our operator variablesign
to'+'
. -
Parse the String: We parse each character of our string
s
.- For the first character
'3'
, since it is a digit, we updatev
to bev * 10 + 3
, which is3
. - The next character is
'+'
. Since we encounter an operator, we perform the action for the last sign ('+'). We push3
onto the stack (as ourv
is3
and the sign is'+'
). We then updatesign
to'+'
, and resetv
to0
.
- For the first character
-
Continue parsing:
- Next, we encounter
'5'
, which we multiply by 10 and add to ourv
(0 at this moment), resulting in5
. - Similarly, we encounter the character
'2'
after'5'
and the'*'
operator, but we don't do anything yet because the number2
is not complete. After'2'
, our currentv
is52
. - Then we see the
'*'
operator. Now we need to act on the previous sign which was'+'
, so we push5
into our stack and resetv
to2
because2
is part of the next operation which involves multiplication. We updatesign
to be'*'
.
- Next, we encounter
-
Handle Operators and End of String:
- Continue parsing: next, we encounter
'-'
, and since our last operator was'*'
, we multiply the most recent number in the stack (5
) byv
(which is2
), and push the result10
back onto the stack. Updatesign
to'-'
andv
to0
. - Parsing the next number
'4'
, just incrementv
to4
. - We see the
'/'
operator, which means—since the last sign was'-'
—we push-4
onto the stack. Updatesign
to'/'
and resetv
to0
. - Lastly, the character
'2'
setsv
to2
.
- Continue parsing: next, we encounter
-
At this point, we've reached the end of the string. The last operator is
'/'
, so we must divide the top value of the stack-4
byv
, which is2
, truncate towards zero, and push the result back to the stack (-2
). -
Evaluate the Stack: We now evaluate the contents of the stack, which has
[3, 10, -2]
. By summing them up, we get the final result of3 + 10 - 2 = 11
.# Stack operations in detail: # stk = [] after initialization # stk = [3] after processing "3+" # stk = [3, 5] after processing "5" # stk = [10] after processing "5*2" # stk = [10, -4] after processing "-4" # stk = [10, -2] after processing "-4/2" (since the division truncates towards zero) # Final sum of stack = 3 + 10 - 2 = 11
The above step-by-step processing adheres to the operator precedence and accurately evaluates the mathematical expression without the use of any built-in evaluators. The final result for the expression s = "3+5*2-4/2"
is 11
.
Solution Implementation
1class Solution:
2 def calculate(self, s: str) -> int:
3 # Initialize the value to hold current number and stack to store values.
4 value, n = 0, len(s)
5 # Set the initial sign to '+' (plus).
6 sign = '+'
7 # Initialize an empty stack to keep numbers and intermediate results.
8 stack = []
9
10 # Iterate over each character in the input string.
11 for i, char in enumerate(s):
12 # If the character is a digit, update 'value' to be the current multi-digit number.
13 if char.isdigit():
14 value = value * 10 + int(char)
15
16 # If we reach the end of the string or encounter an operator.
17 if i == n - 1 or char in '+-*/':
18 # Perform an action depending on the last sign observed.
19 if sign == '+':
20 # If the sign is plus, push the current value onto the stack.
21 stack.append(value)
22 elif sign == '-':
23 # If the sign is minus, push the negative of the value onto the stack.
24 stack.append(-value)
25 elif sign == '*':
26 # If the sign is times, multiply the top of the stack by the current value and push it back.
27 stack.append(stack.pop() * value)
28 elif sign == '/':
29 # If the sign is divide, take the top of the stack, divide by current value and push the result back.
30 # Use integer division to round towards zero.
31 stack.append(int(stack.pop() / value))
32
33 # Update the sign to the current operator.
34 sign = char
35 # Reset 'value' for the next number.
36 value = 0
37
38 # The final result is the sum of the values in the stack.
39 return sum(stack)
40
1import java.util.Deque;
2import java.util.ArrayDeque;
3
4class Solution {
5 public int calculate(String s) {
6 Deque<Integer> stack = new ArrayDeque<>(); // Use a stack to manage intermediate results
7 char operation = '+'; // Initialize the operation as addition
8 int value = 0; // This will hold the current number
9
10 // Iterate through each character in the input string
11 for (int i = 0; i < s.length(); ++i) {
12 char currentChar = s.charAt(i);
13
14 // If the current character is a digit, accumulate into value
15 if (Character.isDigit(currentChar)) {
16 value = value * 10 + (currentChar - '0');
17 }
18
19 // If we've reached the end of the string or we encounter an operator
20 if (i == s.length() - 1 || currentChar == '+' || currentChar == '-'
21 || currentChar == '*' || currentChar == '/') {
22
23 // Perform the operation based on the previous sign
24 switch (operation) {
25 case '+':
26 stack.push(value); // Add the value to the stack
27 break;
28 case '-':
29 stack.push(-value); // Push the negated value for subtraction
30 break;
31 case '*':
32 stack.push(stack.pop() * value); // Multiply with the top value on the stack
33 break;
34 case '/':
35 stack.push(stack.pop() / value); // Divide the top value with current value
36 break;
37 }
38
39 operation = currentChar; // Update the operation for the next iteration
40 value = 0; // Reset value for the next number
41 }
42 }
43
44 int result = 0; // Initialize result to accumulate stack values
45 // Pop values from the stack and add them to calculate the result
46 while (!stack.isEmpty()) {
47 result += stack.pop();
48 }
49
50 return result; // Return the final calculated result
51 }
52}
53
1#include <cctype>
2#include <stack>
3#include <string>
4
5class Solution {
6public:
7 int calculate(std::string s) {
8 // Initialize the current value and the total size of the string
9 int currentValue = 0, stringSize = s.size();
10 // Set the initial sign to '+'
11 char operationSign = '+';
12 // Stack to hold intermediate results
13 std::stack<int> calculationStack;
14 for (int i = 0; i < stringSize; ++i) {
15 char currentChar = s[i];
16 // If character is a digit, build the number by multiplying the current value by 10 and adding the digit's integer value
17 if (std::isdigit(currentChar)) currentValue = currentValue * 10 + (currentChar - '0');
18 // If we reach the end of the string or encounter an operation
19 if (i == stringSize - 1 || currentChar == '+' || currentChar == '-' || currentChar == '*' || currentChar == '/') {
20 switch (operationSign) {
21 // If the sign is '+', push the current value to the stack
22 case '+':
23 calculationStack.push(currentValue);
24 break;
25 // If the sign is '-', push the negative of the current value to the stack
26 case '-':
27 calculationStack.push(-currentValue);
28 break;
29 // If the sign is '*', multiply the top element of the stack with the current value and push the result back to the stack
30 case '*':
31 {
32 int topValue = calculationStack.top();
33 calculationStack.pop();
34 calculationStack.push(topValue * currentValue);
35 }
36 break;
37 // If the sign is '/', divide the top element of the stack by the current value and push the result back to the stack
38 case '/':
39 {
40 int topValue = calculationStack.top();
41 calculationStack.pop();
42 calculationStack.push(topValue / currentValue);
43 }
44 break;
45 }
46 // Update the operation sign for the next operation
47 operationSign = currentChar;
48 // Reset the current value
49 currentValue = 0;
50 }
51 }
52 // Initialize the answer to 0
53 int result = 0;
54 // Add up all values in the stack to get the final result
55 while (!calculationStack.empty()) {
56 result += calculationStack.top();
57 calculationStack.pop();
58 }
59 // Return the result of expression evaluation
60 return result;
61 }
62};
63
1// Import Stack data structure for use in calculation
2import { Stack } from "typescript-collections";
3
4// Function to evaluate the arithmetic expression within a string
5function calculate(expression: string): number {
6 // Initialize currentValue to hold the numbers as they are parsed
7 let currentValue: number = 0;
8 // Determine the length of the expression string
9 let expressionSize: number = expression.length;
10 // Start with a default operationSign of '+'
11 let operationSign: string = '+';
12 // Use a stack to keep track of calculation results
13 let calculationStack = new Stack<number>();
14
15 for (let i = 0; i < expressionSize; ++i) {
16 let currentChar = expression[i];
17
18 // If the current character is a digit, construct the number
19 if (!isNaN(parseInt(currentChar))) {
20 currentValue = currentValue * 10 + (parseInt(currentChar));
21 }
22
23 // Perform operations at the end of the string or at an operator
24 if (i === expressionSize - 1 || currentChar === '+' || currentChar === '-' || currentChar === '*' || currentChar === '/') {
25 switch (operationSign) {
26 // Push current value to stack for a '+' operation
27 case '+':
28 calculationStack.push(currentValue);
29 break;
30 // Push the negative of current value for a '-' operation
31 case '-':
32 calculationStack.push(-currentValue);
33 break;
34 // Multiply the stack's top with current value for a '*' operation
35 case '*':
36 {
37 let topValue = calculationStack.pop();
38 if(topValue !== undefined) {
39 calculationStack.push(topValue * currentValue);
40 }
41 }
42 break;
43 // Divide the stack's top by current value for a '/' operation
44 case '/':
45 {
46 let topValue = calculationStack.pop();
47 if(topValue !== undefined) {
48 calculationStack.push(Math.trunc(topValue / currentValue));
49 }
50 }
51 break;
52 }
53 // Update the operationSign with current character
54 operationSign = currentChar;
55 // Reset currentValue for the next part of the string
56 currentValue = 0;
57 }
58 }
59
60 // Calculate the final result by summing up the values in the stack
61 let result: number = 0;
62 while (!calculationStack.isEmpty()) {
63 let value = calculationStack.pop();
64 if(value !== undefined) {
65 result += value;
66 }
67 }
68
69 // Return the result of the expression evaluation
70 return result;
71}
72
73// Note: Since this bit of code uses the 'Stack' implementation from the 'typescript-collections' library,
74// you would have to install that npm package to use this stack data structure.
75
Time and Space Complexity
Time Complexity
The time complexity of the given code is O(n)
where n
is the length of the input string. The algorithm iterates through each character of the string exactly once, and the operations within the loop are constant time operations, including digit extraction, basic arithmetic operations, and stack manipulation. The final summation of stack elements also takes O(n)
time in the worst case where all characters result in individual numbers pushed onto the stack.
Space Complexity
The space complexity is O(n)
for the stack that stores numbers based on the operations. In the worst case, where the string is composed of numbers separated by addition signs, each number is pushed onto the stack, reaching a maximum stack size proportional to the length of the input string.
Learn more about how to find time and space complexity quickly using problem constraints.
What is the best way of checking if an element exists in a sorted array once in terms of time complexity? Select the best that applies.
Recommended Readings
Stack Intro Imagine you have a pile of books on your desk If you want to add a new book you place it on top If you want to read a book you take it from the top And if you simply want to see which book is on the top you
Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Want a Structured Path to Master System Design Too? Don’t Miss This!